순열과 조합, 세는 방법의 두 갈래

두 법칙의 구분 (복습)

두 사건 A, B가 동시에 일어나지 않을 때, A 또는 B가 일어나는 경우의 수는 m + n 입니다(합의 법칙). 사건 A에 이어서 사건 B가 일어날 때, A와 B가 잇달아 일어나는 경우의 수는 $m \times n$ 입니다(곱의 법칙). '또는'은 더하고 '그리고'는 곱한다고 기억하면 됩니다.

1. 1
   $72 = 2^{3} \times 3^{2}$. 약수는 2의 지수 0~3 (4가지)와 3의 지수 0~2 (3가지)를 하나씩 골라 만들므로 $4 \times 3 = 12$개
2. 2
   A→B 3가지, 그리고 이어서 B→C 2가지 $\to 3 \times 2 = 6$가지

순열 nPr

서로 다른 n개에서 r개를 택해 순서를 생각하여 일렬로 나열하는 것을 순열이라 하고, 그 경우의 수를 nPr 로 씁니다. 첫 자리에 n가지, 둘째 자리에 (n − 1)가지, … r번째 자리에 (n − r + 1)가지이므로 곱의 법칙으로 계산합니다.

1. 1
   회장 5가지, 부회장은 남은 4명 중 4가지
2. 2
   $5P2 = 5 \times 4 = 20$

계승 n! 과 nPr = n! / (n − r)!

1부터 n까지의 자연수를 모두 곱한 것을 n의 계승이라 하고 n! 으로 씁니다. n개를 모두 나열하는 nPn = n! 입니다. 또 0! = 1, nP0 = 1 로 정합니다. 그러면 nPr 은 n! 에서 뒤쪽 (n − r)! 만큼을 나눈 것과 같습니다.

순열의 활용

이웃하는 배열은 이웃할 것들을 한 덩어리로 묶어 나열한 뒤, 덩어리 안의 순서(k!)를 곱합니다. 이웃하지 않는 배열은 나머지를 먼저 나열하고 그 사이와 양 끝 자리에 끼워 넣습니다. 특정 자리가 정해진 것은 먼저 놓고 나머지를 나열합니다. 숫자 카드로 자연수를 만들 때는 맨 앞자리에 0이 올 수 없다는 점에 주의합니다.

1. 1
   백의 자리: 0을 뺀 4가지
2. 2
   십의 자리: 남은 4장(0 포함) → 4가지
3. 3
   일의 자리: 남은 3장 → 3가지. 곱의 법칙으로 $4 \times 4 \times 3 = 48$개

조합 nCr 과 r! 로 나누는 이유

서로 다른 n개에서 순서를 생각하지 않고 r개를 택하는 것을 조합이라 하고 nCr 로 씁니다. 순열 nPr 에서는 같은 r개를 뽑아 순서만 바꾼 r! 가지가 모두 다른 경우로 세어지지만, 조합에서는 이들이 하나입니다. 그래서 nPr 을 r! 로 나눕니다.

1. 1
   순서를 생각하면 5P2 = 20 (회장·부회장을 정하는 경우)
2. 2
   대표 2명은 순서가 없으므로 2! = 2 로 나눔 $\to 5C2 = \dfrac{20}{2} = 10$

조합의 성질

r개를 뽑는 것과 남길 (n − r)개를 고르는 것은 같은 일이므로 nCr = nC(n−r) 입니다. 또 특정한 한 원소를 기준으로, 그것을 포함하여 뽑는 경우 (n−1)C(r−1) 과 포함하지 않고 뽑는 경우 (n−1)Cr 을 더하면 전체 nCr 이 됩니다.

특정 원소를 포함하거나 제외하기

특정한 사람을 반드시 포함해서 뽑을 때는 그 사람을 미리 뽑아 두고 나머지에서 남은 수만큼 뽑습니다. 반드시 제외할 때는 그 사람을 빼고 뽑습니다.

1. 1
   (1) A는 이미 뽑혔으므로 나머지 6명 중 2명 → 6C2 = 15
2. 2
   (2) A를 뺀 6명 중 3명 → 6C3 = 20
3. 3
   확인: 15 + 20 = 35 = 7C3

직선과 삼각형의 개수

어느 세 점도 한 직선 위에 있지 않은 n개의 점이 있을 때, 두 점을 고르면 직선 하나, 세 점을 고르면 삼각형 하나가 정해집니다. 고르는 순서는 상관없으므로 직선의 개수는 nC2, 삼각형의 개수는 nC3 입니다.

조 나누기

사람들을 몇 개의 조로 나눌 때는 조합을 차례로 곱합니다. 이때 인원이 같은 조가 k개 있으면 그 조들끼리 순서를 바꾼 것은 같은 나눔이므로 k! 로 나눕니다.

1. 1
   $(1) 6C2 \times 4C4 = 15 \times 1 = 15 ($인원이 다르므로 나누지 않음)
2. 2
   $(2) 6C2 \times 4C2 \times 2C2 = 15 \times 6 \times 1 = 90$ 인데, 인원이 같은 세 조의 순서 3! = 6 으로 나눔 → 15