중복조합과 분할

같은 종류를 여러 번 고를 수 있는 선택(중복조합)과, 자연수를 더 작은 자연수의 합으로 나누는 방법(분할)을 다룬다. 사탕 나누기, 방정식의 정수해 세기가 모두 중복조합이다.

핵심 개념

  • 중복조합: 서로 다른 $n$종류에서 중복을 허락하여 $r$개를 고르는 방법 ${}_nH_r={}_{n+r-1}C_r$
  • 방정식의 해: $x_1+\cdots+x_n=r$의 음이 아닌 정수해의 개수 ${}_nH_r$, 자연수해의 개수 ${}_nH_{r-n}={}_{r-1}C_{n-1}$
  • 자연수의 분할 $p(n)$: $n$을 순서를 생각하지 않고 자연수의 합으로 나타내는 방법의 수. $p(4)=5$: $4$, $3+1$, $2+2$, $2+1+1$, $1+1+1+1$
  • 집합의 분할: 원소가 $n$개인 집합을 공집합이 아닌 $k$개의 부분집합으로 나누는 방법 $S(n,k)$ (제2종 스털링 수)
별 6개와 막대 3개를 늘어놓아 네 묶음으로 나눈 그림
별과 막대: 별 $r$개, 막대 $n-1$개의 배열 = $n$명에게 $r$개를 나누는 방법

핵심 정리

${}_nH_r={}_{n+r-1}C_r$

증명 보기 (별과 막대)

$x_1+x_2+\cdots+x_n=r$ ($x_i\ge0$)의 해를 센다. $r$개의 별을 일렬로 놓고 그 사이에 $n-1$개의 막대를 끼워 $n$개의 묶음으로 나누면, 각 묶음의 별의 수가 $x_1,\dots,x_n$이 된다. 예: ★★|★|★★★| $\to(2,1,3,0)$. 거꾸로 모든 해는 이런 배열 하나에 대응하므로 일대일대응이다. 배열은 별과 막대 $n+r-1$개의 자리 중 별의 자리 $r$개를 고르는 것이므로 ${}_{n+r-1}C_r$가지이다.

자연수해는 각 $x_i$에 먼저 $1$씩 주고 남은 $r-n$개를 나누는 것과 같으므로 ${}_nH_{r-n}$이다. $\blacksquare$

예제

  • 사과, 배, 감 중에서 $5$개를 사는 방법: ${}_3H_5={}_7C_5=21$
  • $x+y+z=10$의 자연수해: ${}_3H_7={}_9C_7=36$
  • $(a+b+c)^4$의 전개식의 서로 다른 항의 수: ${}_3H_4={}_6C_4=15$

확인 문제

$x+y+z\le5$를 만족하는 음이 아닌 정수 $(x,y,z)$의 개수를 구하시오.

풀이 보기

남는 양 $w=5-(x+y+z)\ge0$을 새 변수로 두면 $x+y+z+w=5$의 음이 아닌 정수해와 같다. ${}_4H_5={}_8C_5=56$이다.

정리

  • 중복조합 ${}_nH_r={}_{n+r-1}C_r$ (별과 막대)
  • 부등식은 여분 변수를 더해 등식으로 바꾼다.
알림: 보호된 콘텐츠입니다.