순열과 조합

순열과 조합 - 경우의 수

• 경우의 수
  • 어떤 사건이 일어나는 방법이 전부 $m$가지일 때, 그 사건이 일어나는 ‘경우의 수’는 $m$ 가지라고 한다
• 합의 법칙
  • 두 사건 $A,B$의 경우의 수가 각각 $m,n$이라고 하자. 두 사건 간에 공통점이 없으면(상호 배제, 배반 사건, OR) 사건 $A,B$가 일어나는 경우의 수는 $m+n$
    • 카드 한장 뽑기 (표본 공간 - $\Omega =\{26\}$)
      • 표본 공간 : 어떤 확률 실험에서 일어날 수 있는 모든 가능한 결과들의 집합
      • $A$ : 하트 카드의 경우의 수 $13$
      • $B$ : 클로버 카드의 경우의 수 $13$
      • 카드를 한 장 뽑는 경우의 수 : $|A\cup B|=13+13=26$
        • $\cup$ - OR라는 의미로 사용
• 곱의 법칙
  • 두 사건 $A,B$의 경우의 수가 각각 $m,n$이라고 하자. 두 사건 $A,B$가 동시에(순차적, AND) 일어나는 경우의 수는 $m\times n$
    • 카드 두장 뽑기 (표본 공간 - $\Omega =\{(\text{카드},\text{카드})\}$)
      • $A$ : 하트 카드의 경우의 수 $13$
      • $B$ : 클로버 카드의 경우의 수 $13$
      • 하트에서 한장, 클로버에서 한장 뽑는 경우의 수 : $|A\cap B|=13\times 13=169$
        • $\cap$ - AND라는 의미로 사용

순열과 조합 - 순열(Permutation)

• 팩토리얼
  • $1$부터 $n$까지의 자연수의 곱을 $n$의 계승 또는 $n$ 팩토리얼이라 칭함 - $n!$
    • $n!=n\times (n-1)\times ...\times 2\times 1$
    • $0!=1,1!=1$

순열(Permutation)이란

• 서로 다른 $n$개의 원소 중 $r$개를 선택하여, 중복되지 않고 순서대로 나열한 것
  • 세 문자 $a,b,c$ 중 2개의 문자를 선택하여, 중복되지 않고 순서대로 나열할 수 있는 경우의 수
    • $ab,ac,ba,bc,ca,cb$ → 6가지
  • 순서가 중요
• 순열 공식
  • ${}_n{P}_r=\frac{n!}{(n-r!)}$
  • ${}_n{P}_n=n!$
  • ${}_n{P}_0=1$
• Q. 소문자 알파벳 2개를 뽑아, 2글자 문자를 만드는 경우의 수 (같은 알파벳은 제외)

중복 순열

• 중복 순열은 서로 다른 $n$개의 원소 중 $r$개를 중복을 허용하여 순서대로 나열한 것
• 세 문자 $a,b,c$ 중 2개의 문자를 선택하여, 중복을 허용하고 순서대로 나열할 수 있는 경우의 수
  • $aa,ab,ac,ba,bb,bc,ca,cb,cc$ → 9가지
• 중복 순열 공식
  • ${}_n{\Pi }_r=n^r$
• Q. $1,2,3,4$ 네 개의 수 중 3개의 숫자를 선택하여 3자리 숫자를 만들 수 있는 경우의 수는

순열과 조합 - 조합(Combination)

조합(Combination)이란

• 서로 다른 $n$개의 원소 중 $r$개를 중복되지 않고, 순서에 의미를 두지 않고 나열할 것
  • (순열에서 순서에 의한 중복을 제거한 것)
  • 세 문자 $a,b,c$ 중 2개의 문자를 중복하지 않고, 선택하여 순서에 상관없이 나열할 수 있는 경우의 수
    • $ab,ac,bc$ → 3개
• 조합 공식
  • ${}_n{C}_r=\frac{{}_n{P}_r}{r!}=\frac{n!}{r!(n-r)!}$
  • 순열 공식에서 $r!$ 나누는 이유
    • 같은 $r$개가 만들어내는 ‘순서만 다른 경우들’을 하나로 처리하기 위해
• 중복 조합 공식
  • ${}_n{H}_r={}_{n+r-1}{C}_r$
• Q. 색이 다른 포켓볼 4개가 있다. 3개씩 묶는 경우의 수는?

순열과 조합 - 정리 (경우의 수)

• 순열
  • 순서를 생각하고, 중복을 허락하지 않은 경우의 수 세기
  • ${}_n{P}_r=\frac{n!}{(n-r!)}$
  • ${}_n{P}_n=n!$
  • ${}_n{P}_0=1$
• 중복순열
  • 순서를 생각하고, 중복을 허락하여 경우의 수 세기
  • ${}_n{\Pi }_r=n^r$
• 조합
  • 순서를 생각하지 않고, 중복을 허락하지 않은 경우의 수 세기
  • ${}_n{C}_r=\frac{{}_n{P}_r}{r!}=\frac{n!}{r!(n-r)!}$
• 중복조합
  • 순서를 생각하지 않고 중복을 허락하여 경우의 수 세기
  • ${}_n{H}_r={}_{n+r-1}Cr$
• Q. 2023 중등부 1차 1교시 4번. 교수와 학생
• Q. $A,B,C,D,E$를 줄 세운다. $A$와 $B$는 이웃하지 않고, $C$는 $D$와 $E$사이에 앉는다. 가능한 배열 수는?