다항계수(multinomial coefficient)는 이항계수의 일반화이다.
모티브[편집 | 원본 편집]
다항계수의 정의는 사실 다항정리에서 시작된 것이다. 먼저 이항정리를 보자:
이제 자연스럽게 이것을 확장할 수 있을 것이다. 즉 우리는
으로 나타내고 싶다(?). 이항정리에서, [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} }[/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] 개이다.[1]
참고문헌[편집 | 원본 편집]
- Chuan Chong Chen, Khee Meng Koh, Principles and Techniques in Combinatorics, World Scientific (1992).
각주
- ↑ Q. Wu, Maximal Coefficient of the Multinomial [math]\displaystyle{ (x_1 + x_2 + \cdots + x_k)^n }[/math], Southeast Asian Bulletin of Maths. 15 (1991), 77-82