다항계수

틀:학술

다항계수(multinomial coefficient)는 이항계수의 일반화이다.

모티브

다항계수의 정의는 사실 다항정리에서 시작된 것이다. 먼저 이항정리를 보자:

[math]\displaystyle{ (x_1 + x_2 )^n = \sum_{r=0}^n \binom n r {x_1}^r {x_2}^{n-r}. }[/math]

이제 자연스럽게 이것을 확장할 수 있을 것이다. 즉 우리는

[math]\displaystyle{ (x_1 + x_2 + \cdots + x_m )^n = \sum_{n_1 + \cdots + n_m = n} C(n_1, n_2, \cdots, n_m) {x_1}^{n_1} {x_2}^{n_2}\cdots {x_m}^{n_m} }[/math]

으로 나타내고 싶다(?). 이항정리에서, [math]\displaystyle{ x^r y^{n-r} }[/math]의 계수는 [math]\displaystyle{ n }[/math] 개의 대상(object)을 [math]\displaystyle{ r }[/math] 개와 [math]\displaystyle{ n-r }[/math] 개로 양분(서로 다른 둘로 분할)하는 경우의 수이다. 따라서 다음과 같이 정의해볼 수 있다.

다항계수는 [math]\displaystyle{ n }[/math] 개의 대상을 [math]\displaystyle{ m }[/math] 개로 나누는 경우의 수이다. 더 명시적으로, 다항계수 [math]\displaystyle{ \binom{n}{n_1, \cdots, n_m} }[/math]는 [math]\displaystyle{ n }[/math] 개의 대상을 [math]\displaystyle{ n_1, \; n_2, \; \cdots , \; n_m }[/math] 개씩 분할하는 경우의 수이다.

자, 이제 이 경우의 수를 구해보자. 먼저 [math]\displaystyle{ n }[/math] 개의 대상에서 [math]\displaystyle{ n_1 }[/math] 개를 골라내고, 남은 것에서 [math]\displaystyle{ n_2 }[/math] 개를 골라내고, 이런 식으로 반복하면 다항계수는 다음과 같음을 알 수 있다:

[math]\displaystyle{ \binom{n}{n_1, \cdots, n_m} = \binom{n}{n_1} \binom {n-n_1}{n_2} \cdots \binom{n-n_1 - \cdots - n_{m-1}}{n_m} = \prod_{j=1}^n \binom{n-\sum_{k=1}^{j-1} n_k}{n_j}. }[/math]

이항계수의 정의를 이용하여 전개해보면:

[math]\displaystyle{ \binom{n}{n_1, \cdots, n_m} = \frac{n!}{n_1 ! (n-n_1 )! } \frac{(n- n_1)!}{n_2 ! (n-n_1 -n_2)! } \cdots \frac{(n- n_1 - \cdots - n_{m-2})!}{n_{m-1} ! (n- n_1 - \cdots - n_{m-1})! } \frac{(n- n_1 - \cdots - n_{m-1})!}{n_m ! 0! } = \frac{n!}{n_1 ! n_2 ! \cdots n_m !} . }[/math]

어...? 어디서 많이 본 것 같다? 정의에서도 알 수 있듯, 이것은 같은 것이 있는 순열과 같다. 같은 것이 있는 순열은 미리 종류를 정해주고 섞는 것이라면, 다항계수는 무작위로 종류를 정해주는 것이라고 생각할 수 있기 때문이다.

정의

다항계수 [math]\displaystyle{ \binom{n}{n_1, \cdots, n_m} }[/math]는 다음의 동치인 진술 중 하나로 정의된다:

• [math]\displaystyle{ \binom{n}{n_1, \cdots, n_m} =\frac{n!}{\prod_{j=1}^m n_j !} = \frac{n!}{n_1 ! n_2 ! \cdots n_m !} }[/math]
• [math]\displaystyle{ (x_1 + x_2 + \cdots + x_m )^n }[/math]의 [math]\displaystyle{ {x_1}^{n_1} {x_2}^{n_2}\cdots {x_m}^{n_m} }[/math]-항의 계수
• [math]\displaystyle{ j }[/math]라고 이름 붙여진 대상이 [math]\displaystyle{ n_j }[/math] 개씩 있을 때, 그것을 나열하는 경우의 수(순열) ([math]\displaystyle{ j=1, \cdots, m }[/math])

성질

• 이항계수 [math]\displaystyle{ \binom{n}{r} = \binom{n}{r, n-r} }[/math]이다.
• [math]\displaystyle{ \sigma }[/math]를 치환이라고 하면, [math]\displaystyle{ \binom{n}{n_1, \cdots, n_m} = \binom{n}{\sigma(n_1), \cdots, \sigma(n_m)} }[/math]이다.
• (다항계수 항등식) [math]\displaystyle{ \binom{n}{n_1, \cdots, n_m} = \sum_{j=1}^{m} \binom{n - 1}{n_1, \cdots, n_{j-1} , n_j - 1 , n_{j+1}, \cdots, n_m} }[/math]
• 다항정리에서 [math]\displaystyle{ x_j = 1 }[/math]일 때 [math]\displaystyle{ \sum_{\sum n_j = n}\binom{n}{n_1, \cdots, n_m} = m^n }[/math]이다.
• 나눗셈 정리에 의해 [math]\displaystyle{ n=mr+k \; \; (0\le k \lt m) }[/math]이라 하면, 다항계수 중에서 최댓값을 가지는 것은 [math]\displaystyle{ \binom{n}{\underbrace{r, \cdots, r}_{m-k}, \underbrace{r+1, \cdots, r+1}_{k}} = \frac{n!}{r!^{m-k}(r+1)!^k}= \frac{n!}{r!^{m}(r+1)^k} }[/math]이다. 다항식 [math]\displaystyle{ (x_1 + \cdots + x_m)^n }[/math]에서 이 최댓값을 계수로 갖는 항의 수는 [math]\displaystyle{ \binom{m}{k} }[/math] 개이다.

참고문헌

• Chuan Chong Chen, Khee Meng Koh, Principles and Techniques in Combinatorics, World Scientific (1992).