다항 계수 문서 원본 보기

{{위키데이터 속성 추적}}
[[수학]]에서 '''다항 계수'''(多項係數, {{llang|en|multinomial coefficient}})는 주어진 개수의 원소들을 주어진 크기의 상자들에 넣는 방법의 가짓수이다. '''다항 정리'''(多項定理, {{llang|en|multinomial theorem}})는 [[다항식]]의 거듭제곱을 전개하는 정리이며, 전개식의 계수는 다항 계수이다. 다항 계수와 다항 정리는 [[이항 계수]]와 [[이항 정리]]의 일반화이다.

== 정의 ==
음이 아닌 정수들의 합 <math>n=k_1+k_2+\cdots+k_m</math>이 주어졌을 때, '''다항 계수''' <math>\textstyle\binom n{k_1,k_2,\dots,k_m}</math>는 다음과 같다.
:<math>\binom n{k_1,k_2,\dots,k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}=\prod_{i=1}^m\binom{k_1+k_2+\cdots+k_i}{k_i}=\prod_{i=1}^m\binom{k_i+k_{i+1}+\cdots+k_m}{k_i}</math>
다항 계수를 [[단체 (수학)|단체]]에 나열한 표를 '''[[파스칼의 단체]]'''(Pascal의單體, {{llang|en|Pascal's simplex}})라고 한다.

== 성질 ==
=== 항등식 ===
다음과 같은 점화식이 성립한다.
:<math>\binom n{k_1,k_2,\dots,k_m}=\binom n{k_1+\cdots+k_i,k_{i+1},k_{i+2},\dots,k_m}\binom{k_1+k_2+\cdots+k_i}{k_1,k_2,\dots,k_i}</math>
다음과 같은 합 공식이 성립한다. 이는 다항 정리의 따름정리이다.
:<math>\sum_{k_1,k_2,\dots,k_m\in\mathbb N}^{k_1+k_2+\cdots+k_m=n}\binom n{k_1,k_2,\dots,k_m}=m^n</math>

=== 수론적 성질 ===
다항 계수의 [[소인수]]의 중복도를 [[쿠머 정리]]를 통해 계산할 수 있다.

=== 조합론적 성질 ===
다항 계수 <math>\textstyle\binom n{k_1,k_2,\dots,k_m}</math>은 조합론적으로 다음과 같이 해석할 수 있다.
* <math>|P^{-1}(i)|=k_i</math> (<math>i=1,2,\dots,m</math>)을 만족시키는 함수 <math>P\colon\{1,2,\dots,n\}\to\{1,2,\dots,m\}</math>의 수
** 즉, <math>n</math>개의 공을 크기가 각각 <math>k_i</math>인 <math>m</math>개의 상자에 넣는 방법의 수
* [[중복집합]] <math>k_1\{1\}+k_2\{2\}+\cdots+k_n\{n\}</math>의 [[순열]]의 수
** 즉, <math>n</math>글자 단어가 각각 <math>k_i</math>번 나오는 <math>m</math>가지 글자로 이루어졌을 때, 그 단어의 [[어구전철]]의 수
* <math>\mathbb Z^m</math> 위의, 시작점이 0, 끝점이 <math>(k_1,k_2,\dots,k_m)</math>, 보폭이 표준 기저인 격자 경로({{llang|en|lattice path}})의 개수<ref name="Stanley">{{서적 인용
|url=http://math.mit.edu/~rstan/ec/ec1/
|성=Stanley
|이름=Richard P.
|제목=Enumerative Combinatorics. Volume 1
|언어=en
|판=2
|출판사=Cambridge University Press
|날짜=2012
}}</ref>
* 다항 전개의 계수

== 응용 ==
=== 다항 정리 ===
'''다항 정리'''에 따르면, 다음과 같은 다항식의 전개가 성립한다.
:<math>(x_1+x_2+\cdots+x_m)^n=\sum_{k_1,k_2,\dots,k_m\in\mathbb N}^{k_1+k_2+\cdots+k_m=n}\binom n{k_1,k_2,\dots,k_m}x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}</math>
[[다중지표]] 표기법을 사용하여 다항 정리를 다음과 같이 적을 수 있다.
:<math>(x_1+x_2+\cdots+x_m)^n=\sum_{K\in\mathbb N^m}^{|K|=n}\binom nKx^K</math>
전개식의 항의 개수는 다음과 같이 [[이항 계수]]로 나타낼 수 있다.
:<math>\binom{n+m-1}{m-1}</math>
{{증명}}
[[이항 정리]]와 [[수학적 귀납법]]을 사용하여 증명할 수 있다. 우선, <math>m=0,1</math>의 경우는 자명하게 성립하며, <math>m=2</math>의 경우는 이항 정리에 따라 성립한다.
:<math>0^n=\begin{cases}0&n>0\\1&n=0\end{cases}</math>
:<math>x_1^n=x_1^n</math>
:<math>(x_1+x_2)^n=\sum_{k_1,k_2\in\mathbb N}^{k_1+k_2=n}\binom n{k_1,k_2}x_1^{k_1}x_2^{k_2}</math>
이제, <math>m</math>에 대하여 성립한다고 가정하자. 그렇다면, 다음이 성립한다.
:<math>\begin{align}(x_1+x_2+\cdots+x_{m+1})^n
&=\sum_{k_1,k_2,\dots,k_{m-1},\ell\in\mathbb N}^{k_1+k_2+\cdots+k_{m-1}+\ell=n}\frac{n!}{k_1!k_2!\cdots k_{m-1}!\ell!}x_1^{k_1}x_2^{k_2}\cdots x_{m-1}^{k_{m-1}}(x_m+x_{m+1})^\ell\\
&=\sum_{k_1,k_2,\dots,k_{m-1},\ell\in\mathbb N}^{k_1+k_2+\cdots+k_{m-1}+\ell=n}\frac{n!}{k_1!k_2!\cdots k_{m-1}!\ell!}x_1^{k_1}x_2^{k_2}\cdots x_{m-1}^{k_{m-1}}\sum_{k_m,k_{m+1}\in\mathbb N}^{k_m+k_{m+1}=\ell}\frac{\ell!}{k_m!k_{m+1}!}x_m^{k_m}x_{m+1}^{k_{m+1}}\\
&=\sum_{k_1,k_2,\dots,k_{m+1}\in\mathbb N}^{k_1+k_2+\cdots+k_{m+1}=n}\frac{n!}{k_1!k_2!\cdots k_{m+1}!}x_1^{k_1}x_2^{k_2}\cdots x_{m+1}^{k_{m+1}}
\end{align}</math>
즉, <math>m+1</math>에 대하여 성립한다. 수학적 귀납법에 따라, 임의의 <math>m\in\mathbb N</math>에 대하여 다항 정리가 성립한다.
{{증명 끝}}

=== 다항 분포 ===
{{본문|다항 분포}}

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{수학노트|title=다항정리}}
* {{eom|title=Multinomial coefficient}}
* {{매스월드|id=MultinomialCoefficient|title=Multinomial coefficient}}
* {{매스월드|id=MultinomialSeries|title=Multinomial series}}
* {{플래닛매스|urlname=multinomialtheorem|title=Multinomial theorem}}
* {{플래닛매스|urlname=multinomialtheoremproof|title=Multinomial theorem (proof)}}
* {{proofwiki|id=Definition:Multinomial Coefficient|제목=Definition:Multinomial coefficient}}
* {{proofwiki|id=Multinomial Theorem|제목=Multinomial theorem}}
* {{proofwiki|id=Multinomial Coefficient expressed as Product of Binomial Coefficients|제목=Multinomial coefficient expressed as product of binomial coefficients}}

[[분류:계승과 이항식 주제]]
[[분류:대수학 정리]]