중복조합의 공식 H(n,r)=C(n+r-1,r)

수학노트
이동: 둘러보기, 검색

개요

  • 중복조합
    • 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
    • 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음.
  • n개 중에서 r개를 선택하는 중복조합의 개수를 \(_n H_r=\textstyle\left\langle{n\atop r}\right\rangle\) 로 나타낸다.
  • 변수의 개수가 $n$이고, 차수가 $d$인 동차다항식(Homogeneous polynomial)이 이루는 벡터공간의 차원은 $_n H_d$이며, 중복조합의 H는 homogeneous에서 온 것이다
  • $n$차원 벡터공간 $V$에 대하여 대칭곱 $\operatorname{Sym}^d V$의 차원은 $_n H_d$로 주어진다

조합과의 비교

  • 조합은 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 것
  • 가령 1,2,3,4 네 개의 수 가운데서 세 개씩 뽑아 모은 조합은 123, 124, 134, 234 의 네 가지
  • n개 중에서 r개를 선택하는 조합의 개수를 \(_n C_r = {n\choose r} \)로 표현함
  • 즉, \(_4 C_3 = {4\choose 3} =4\) 가 됨.
  • 일반적으로 \(_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}\) 공식을 통해 구할수 있음.



중복조합의 공식 증명 1

  • 중복조합의 공식\[_n H_r=_{n+r-1}C_{r}\]
  • 증명의 아이디어를 이해하기 위해, $_4 H_2$의 예를 들어보자
  • 1,2,3,4 중에서 뽑는 것으로 하면, 중복해서 두 개를 뽑는 방법은 다음과 같이 열 가지가 있음.
    • 11,12,13,14,22,23,24,33,34,44
  • 이제 이 중복조합에서 첫번째 것은 내버려 두고, 두번째 수에 1을 더하면 다음과 같은 결과를 얻음.
    • 12,13,14,15,23,24,25,34,35,45
    • 이것은 1부터 5까지 중에서 2개를 선택하는 방법과 같아짐.
  • 그러므로, $_4 H_2=_5 H_2$
  • 또다른 예. $2 H_3$의 계산.
  • 1,2 중에서 세 가지를 택하는 중복조합은 다음과 같음.
    • 111,112,122,222
  • 위에서 한 것처럼 첫번째 것은 내버려 두고, 두번째 것에 1, 세번째 것에 2를 더해 보면, 다음을 얻게 됨
    • 123,124,134,234
    • 이 경우는 1,2,3,4 중에서 세 개를 뽑는 조합과 일치함.
  • 그러므로, $_2 H_3=_4 C_3$
  • 특정한 조합과 특정한 중복조합 사이에 일대일대응이 존재하는 것을 보이는 것임.



중복조합의 공식 증명 2

  • n=4, r=18 인 경우
  • 집합을 \(\{a,b,c,d\}\) 로 두자.
  • a가 6개, b가 2개, c가 3개, d가 7개 있는 경우를 아래처럼 나타내자.\[\{a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d \}\]\[\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet \]
  • 그림에서 점과 막대를 다 합하여 총 4+18-1=21 개가 있는데, 이 21개의 위치에서 18개를 선택하여 a,b,c,d를 배열하는 중복조합과 일대일대응된다.



생성함수

  • 생성함수
  • 한 개의 원소에서 얻어지는 중복조합 $\{ \{\}, \{x\}, \{x,x\}, \{x,x,x\}, ... \}$ 의 생성함수는 $S = 1 + x + x^2 + x^3 + \cdots = 1 + xS$로부터 $S=1/(1-x)$
  • 두 개의 경우는

$$ (1-x)^{-1}(1-y)^{-1}=1+(x+y)+(x^2+xy+y^2)+(x^3+x^2y+xy^2+y^3)+\cdots $$

  • 따라서

$$ \frac{1}{(1-x)^2}=\sum_{r=0}^{\infty} \textstyle\left\langle{2\atop r}\right\rangle x^r $$

  • n개의 원소에서 r개를 뽑는 중복조합의 생성함수는 다음과 같이 주어진다

\[ \begin{aligned} \frac{1}{(1-x)^n}&=\sum_{r=0}^{\infty} \textstyle\left\langle{n\atop r}\right\rangle x^r \\ {}&=1+nx+\frac{n(n+1)}{2!}x^2+\frac{n(n+1)(n+2)}{3!}x^3+\cdots \end{aligned} \]

부정방정식에의 응용

  • 자연수 r에 대하여, 다음 부정방정식의 \(x_i \geq 0\)인 정수해의 개수를 구해보자\[x_0+x_1+x_2+\cdots+x_n=r\]
  • 해의 개수는 n+1개의 원소를 가지고 r개를 뽑는 중복조합의 수와 같다. 즉, 해의 개수는 다음과 같다\[_{n+1} H_r=_{n+r}C_{r}=_{n+r}C_{n}\]
  • 프로베니우스 디오판투스 방정식


메모

\(\sum_{k}\left\langle \begin{matrix} 3 \\ 4 \end{matrix} \right\rangle x^k\)

\(\sum_{k} \textstyle\left\langle{n\atop k}\right\rangle x^k\)


관련된 항목들


매스매티카 파일 및 계산 리소스


사전 형태의 자료