잔글 (→모티브) |
잔글 (오류 수정 (빈칸)) |
||
(사용자 4명의 중간 판 5개는 보이지 않습니다) | |||
1번째 줄: | 1번째 줄: | ||
'''다항계수'''(multinomial coefficient)는 [[이항계수]]의 일반화이다. | '''다항계수'''(multinomial coefficient)는 [[이항계수]]의 일반화이다. | ||
24번째 줄: | 22번째 줄: | ||
== 성질 == | == 성질 == | ||
* 이항계수 <math>\binom{n}{r} = \binom{n}{r, n-r}</math>이다. | * 이항계수 <math>\binom{n}{r} = \binom{n}{r, n-r}</math>이다. | ||
* <math>\sigma</math>를 [[치환 (선형대수학)|치환]]이라고 하면, <math>\binom{n}{n_1, \cdots, n_m} = \binom{n}{\sigma(n_1), \cdots, \sigma(n_m)}</math>이다. | * <math>\sigma</math>를 [[치환 (선형대수학)|치환]]이라고 하면, <math>\binom{n}{n_1, \cdots, n_m} = \binom{n}{\sigma(n_1), \cdots, \sigma(n_m)}</math>이다. | ||
* (다항계수 항등식) <math>\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>\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>x_j = 1</math>일 때 <math>\sum_{\sum n_j = n}\binom{n}{n_1, \cdots, n_m} = m^n </math>이다. | * 다항정리에서 <math>x_j = 1</math>일 때 <math>\sum_{\sum n_j = n}\binom{n}{n_1, \cdots, n_m} = m^n </math>이다. | ||
32번째 줄: | 30번째 줄: | ||
* Chuan Chong Chen, Khee Meng Koh, ''Principles and Techniques in Combinatorics'', World Scientific (1992). | * Chuan Chong Chen, Khee Meng Koh, ''Principles and Techniques in Combinatorics'', World Scientific (1992). | ||
{{각주}} | |||
[[분류:조합론]] |
2021년 6월 19일 (토) 23:31 기준 최신판
다항계수(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