나뭇잎 교과서

조합

대표 3명을 뽑을 때는 누가 먼저 뽑혔는지가 중요하지 않습니다. 이렇게 순서를 따지지 않고 뽑는 경우의 수가 조합입니다. 이 절에서는 순열 목록에서 같은 사람들로 이루어진 나열을 한데 묶어, 조합의 수가 순열의 수를 \(r!\)로 나눈 값인 까닭을 확인합니다. 이어서 \(r\)를 바꿀 때 조합의 수가 어떻게 변하는지 보고, 대칭과 '특정한 하나를 넣느냐 빼느냐'로 나누는 관계를 찾습니다.

먼저 알면 좋은 것 순열의 수 \(_nP_r\)계승 \(n!\)합의 법칙곱의 법칙
본문

조합

본문

학생 5명 가운데 3명을 뽑아 반장, 부반장, 총무를 맡기는 방법은 60가지였다. 그런데 직책 없이 청소 당번 3명만 뽑는다면 몇 가지일까? 순서를 따질 때의 수에서 어떻게 순서를 지울 수 있을까?

그림 1. 순서 있게 뽑은 60가지는 같은 세 사람으로 이루어진 것끼리 6개씩 묶여, 묶음이 \(60 \div 6 = 10\)개가 된다.
먼저 알아야 할 것순열과 계승(순열), 곱의 법칙(합의 법칙과 곱의 법칙).

3.3.1순열을 묶어서 센다

5명을 A, B, C, D, E라 하자. 청소 당번으로 A, B, C를 뽑는 것은 한 가지 경우이다. 그런데 직책을 맡길 때는 ABC, ACB, BAC, BCA, CAB, CBA가 모두 다른 경우였다. 같은 세 사람을 늘어놓는 방법이 \(3! = 6\)가지이기 때문이다.

그림 1의 슬라이더로 묶음을 바꾸어 보면, 순서 있게 뽑은 60가지는 세 사람이 같은 것끼리 6개씩 정확히 묶인다. 어느 묶음이든 크기가 6이므로 묶음의 수는 \(60 \div 6 = 10\)이다. 따라서 청소 당번을 뽑는 방법은 10가지이다.

정의 3.3.1 조합

서로 다른 \(n\)개에서 순서를 생각하지 않고 \(r\)개\((0 \le r \le n)\)를 택하는 것을 \(n\)개에서 \(r\)개를 택하는 조합이라 하고, 그 수를 \({}_n\mathrm{C}_r\)로 나타낸다. \[{}_n\mathrm{C}_r = \frac{{}_n\mathrm{P}_r}{r!} = \frac{n!}{r!\,(n - r)!}\]

정의의 식은 1에서 한 일을 그대로 적은 것이다. 조합 하나마다 그 \(r\)개를 늘어놓는 순열이 \(r!\)개씩 있으므로 \({}_n\mathrm{C}_r \times r! = {}_n\mathrm{P}_r\)이다. 다시 말해 조합은 순열을 '같은 것을 골랐는가'로 묶은 묶음의 수이다.

3.3.2고르는 것과 남기는 것

5명 가운데 당번 3명을 고르는 일은, 당번이 아닌 2명을 고르는 일과 같다. 당번 3명이 정해지면 나머지 2명이 저절로 정해지고, 거꾸로도 그렇다. 그래서 \({}_5\mathrm{C}_3 = {}_5\mathrm{C}_2 = 10\)이다.

정리 3.3.2 조합의 성질

\({}_n\mathrm{C}_r = {}_n\mathrm{C}_{n - r}\ (0 \le r \le n)\), \({}_n\mathrm{C}_r = {}_{n-1}\mathrm{C}_{r-1} + {}_{n-1}\mathrm{C}_r\ (1 \le r \le n - 1)\)

두 번째 성질도 세는 방법으로 읽힌다. 5명 가운데 3명을 고를 때, A를 꼭 넣는 경우는 나머지 4명에서 2명을 더 고르므로 \({}_4\mathrm{C}_2 = 6\)가지이다. A를 빼는 경우는 4명에서 3명을 모두 고르므로 \({}_4\mathrm{C}_3 = 4\)가지이다. 두 경우는 겹치지 않으니 합의 법칙에 따라 \(6 + 4 = 10\)이다.1

A를 넣는다나머지 4명에서 2명₄C₂ = 6 A를 뺀다나머지 4명에서 3명₄C₃ = 4 ₅C₃ = 6 + 4 = 10
그림 2. 한 사람을 넣는지 빼는지로 나누면 조합의 수는 더 작은 두 조합의 수의 합이 된다.

3.3.3예제 풀이

예제 3.3.3

남학생 6명, 여학생 4명 가운데 대표 4명을 뽑을 때, 여학생이 적어도 1명 포함되는 방법의 수를 구하여라. 또 남학생 2명, 여학생 2명을 뽑아 일렬로 세우는 방법의 수를 구하여라.

'적어도 1명'은 1명, 2명, 3명, 4명인 경우를 모두 더해야 해서 번거롭다. 그 대신 전체에서 여학생이 한 명도 없는 경우를 뺀다. 10명 가운데 4명을 뽑는 방법은 \({}_{10}\mathrm{C}_4 = \dfrac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210\)가지이고, 남학생만 4명을 뽑는 방법은 \({}_6\mathrm{C}_4 = {}_6\mathrm{C}_2 = 15\)가지이다. 따라서 \(210 - 15 = 195\)가지이다.

두 번째 질문은 뽑는 일과 세우는 일이 잇달아 일어난다. 남학생 2명을 뽑는 방법은 \({}_6\mathrm{C}_2 = 15\), 여학생 2명을 뽑는 방법은 \({}_4\mathrm{C}_2 = 6\)이다. 뽑힌 4명을 일렬로 세우는 방법은 \(4! = 24\)이다. 그러면 곱의 법칙에 따라 \(15 \times 6 \times 24 = 2160\)가지이다.

첫 번째 답을 더해서 확인해 보자. 여학생이 1, 2, 3, 4명인 경우는 각각 \({}_4\mathrm{C}_1 \cdot {}_6\mathrm{C}_3 = 80\), \({}_4\mathrm{C}_2 \cdot {}_6\mathrm{C}_2 = 90\), \({}_4\mathrm{C}_3 \cdot {}_6\mathrm{C}_1 = 24\), \({}_4\mathrm{C}_4 = 1\)이고, 합은 195로 같다. 순서가 필요한 단계에서만 순열을 쓰고 고르는 단계에서는 조합을 쓰면 된다. 아래 탐구 카드에서 고르는 과정과 묶는 과정을 직접 조작해 보자.

  1. 이 성질을 줄줄이 늘어놓으면 파스칼의 삼각형이 된다. 각 수는 바로 위 두 수의 합이다.
마무리

조합은 순열을 같은 것을 고른 것끼리 묶어 센 것이므로, 묶음 하나의 크기 \(r!\)로 나누어 \({}_n\mathrm{C}_r = \tfrac{{}_n\mathrm{P}_r}{r!}\)이다. 처음 질문에서 직책 없이 당번 3명을 뽑는 방법은 \(\tfrac{60}{3!} = 10\)가지이다.

탐구 1

순서 없이 뽑는 수는 왜 순열의 수를 \(r!\)로 나눌까?

조합 · 순열 묶기
nPr
—
\(r!\)
—
nCr
—

칸 하나를 눌러 보세요.

  1. 질문A, B, C, D, E 다섯 명 가운데 대표 3명을 뽑는 방법은 몇 가지일까? 세 명을 뽑아 한 줄로 세우는 방법 60가지와는 무엇이 다를까?
  2. 복원5명 가운데 3명을 뽑아 한 줄로 세우는 방법은 \({}_{5}\mathrm{P}_{3} = 5 \times 4 \times 3 = 60\)가지이다. 또 3명을 한 줄로 세우는 방법은 \(3! = 6\)가지이다.
  3. 설명서로 다른 \(n\)개에서 순서를 생각하지 않고 \(r\)개를 택하는 것을 \(n\)개에서 \(r\)개를 택하는 조합이라 하고, 그 수를 \(_nC_r\)로 나타낸다. 그런데 같은 \(r\)명으로 이루어진 조합 하나는 줄 세우는 방법이 \(r!\)가지이므로 순열 목록에 정확히 \(r!\)번 나타난다. 그래서 \(_nP_r = _nC_r \times r!\)이고 \(_nC_r = _nP_r/r! = n!/(r!(n - r)!)\) (단, \(0 \le r \le n\))이다. \(0! = 1\)로 정했으므로 \(_nC_0 = _nC_n = 1\)이다.
  4. 연결식 \(_nP_r = _nC_r \times r!\)은 곱의 법칙 그대로이다. 순서대로 세우는 일은 '누구를 뽑을지 정하기'(\(_nC_r\)가지)와 '뽑은 사람을 줄 세우기'(\(r!\)가지)를 잇달아 하는 일이기 때문이다.
  5. 적용\(n = 5\), \(r = 3\)에서 ACE 칸을 누르면 같은 세 사람으로 된 칸이 모두 표시되는데, 그 수가 \(3! = 6\)칸인지 세어 보자. 이어서 '같은 모임끼리 묶기'를 눌러 묶음의 수를 \({}_{5}\mathrm{P}_{3} \div 3!\)과 비교해 보자. \(r\)를 바꾸어도 묶음 하나의 크기는 늘 \(r!\)이다.
  6. 판단대표 3명을 뽑는 것과 회장, 부회장, 총무를 뽑는 것은 다르다. 역할이 정해지면 순서가 생기므로 순열이 된다. 그래서 뽑힌 것끼리 자리를 바꾸어도 같은 결과인지를 물어보면 순열과 조합을 가를 수 있다.

확인조건이 달라지면

8명 가운데 청소 당번 3명을 뽑는 방법은 몇 가지일까? (당번끼리는 역할 구분이 없다.)

탐구 2

뽑는 수 r가 바뀌면 조합의 수는 어떻게 변할까?

조합 · 대칭과 나누어 세기
nCr
—
nCn−r
—
막대 높이의 합
—

—

  1. 질문10명 가운데 2명을 뽑는 방법과 8명을 뽑는 방법은 어느 쪽이 더 많을까? 많이 뽑을수록 방법도 많아질까?
  2. 복원\(_nC_r = n!/(r!(n - r)!)\)이다. 또 서로 겹치지 않는 경우로 나누어 세면 합의 법칙으로 더할 수 있다.
  3. 설명먼저 \(r\)명을 뽑는 일은 뽑히지 않을 \(n - r\)명을 정하는 일과 같으므로 \(_nC_r = _nC_{n-r}\)이다. 공식에서도 \(r!\)과 \((n - r)!\)이 자리만 바꾼다. 다음으로 특정한 한 사람 A를 기준으로 나누어 보자. A가 뽑히는 경우는 나머지 \(n - 1\)명에서 \(r - 1\)명을 더 뽑는 \(_{n-1}C_{r-1}\)가지이고, A가 빠지는 경우는 \(_{n-1}C_r\)가지이다. 두 경우는 겹치지 않으므로 \(_nC_r = _{n-1}C_{r-1} + _{n-1}C_r (1 \le r \le n - 1)\)이다. 끝으로 막대를 모두 더하면 몇 명을 뽑든 상관없이 뽑는 방법 전체가 된다. 사람마다 '뽑힘'과 '빠짐' 2가지를 고르므로 곱의 법칙에 따라 그 합은 \(2^n\)이다.
  4. 연결A를 넣느냐 빼느냐로 얻은 관계로 수를 한 줄씩 쌓은 표가 파스칼의 삼각형이다. 이 수들은 다음 과목에서 \((a + b)^n\)을 전개할 때의 계수, 곧 이항정리로 다시 나온다.
  5. 적용\(n\)을 바꾸며 막대 모양이 좌우 대칭인지 보고, \(r\)와 \(n - r\)의 막대 높이를 비교해 보자. 이어서 'A를 넣느냐 빼느냐로 나누기'를 켜고 두 조각의 값을 적은 뒤, \(n\)을 1 줄여 그 값이 어느 막대에 있는지 찾아보자. \(n\)이 1 늘 때마다 막대 높이의 합이 두 배가 되는지도 확인할 수 있다.
  6. 판단\(_nC_r\)는 \(r\)가 \(n/2\)에 가까울 때 가장 크다. 그래서 '많이 뽑을수록 방법이 많다'는 생각은 \(r \le n/2\)인 범위에서만 맞는다. 한편 \(_nC_r = _nC_{n-r}\)를 쓰면 \({}_{20}\mathrm{C}_{18}\) 같은 계산을 \({}_{20}\mathrm{C}_{2} = 190\)으로 줄일 수 있다.

확인조건이 달라지면

\({}_{15}\mathrm{C}_{13}\)의 값은?

AI 출제 문항연습문제 풀어보기13문항 수능·모의평가·학력평가기출문제 풀어보기56문항
Esc

↑↓ 고르기Enter 열기