주 메뉴 열기

바뀜

3,359 바이트 추가됨 ,  2년 전
편집 요약 없음
[[수학]]에서, '''다항 정리계수'''(多項定理係數, {{llang|en|multinomial theoremcoefficient}})는 [[다항식]]의주어진 거듭제곱을개수의 전개하는원소들을 정리이다.주어진 전개식의크기의 계수를상자들에 넣는 방법의 가짓수이다. '''다항 계수정리'''(多項係數定理, {{llang|en|multinomial coefficienttheorem}})라고는 [[다항식]]의 거듭제곱을 전개하는 정리이며, 전개식의 계수는 다항 한다계수이다.
 
== 정의 ==
음이 아닌 정수들의 합 <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_m}</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>(\{1,2,\dots,n\},i\mapsto k_i)</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}})의 개수
 
== 응용 ==
=== 다항 정리 ===
'''다항 정리'''에 따르면, 다음과 같은 다항식의 전개가 성립한다.
:<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>\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}</math>
이며, 이를 '''다항 계수'''라고 한다. [[다중지표]] 표기법
:<math>x=(x_1,x_2,\dots,x_m)</math>
:<math>K=(k_1,k_2,\cdots,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>xx_1^n=(x_1,x_2,\dots,x_m)^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}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>에 대하여 다항 정리가 성립한다.
{{증명 끝}}
 
=== 증명다항 분포 ===
* [[{{본문|다항 분포]]}}
[[이항 정리]]와 [[수학적 귀납법]]을 사용하여 증명할 수 있다.
 
== 같이참고 보기문헌 ==
* {{서적 인용|이름=Stanley|성=Richard P.|제목=Enumerative Combinatorics|언어=en|권=1|판=2|출판사=Cambridge University Press|연도=2011|url=http://math.mit.edu/~rstan/ec/ec1/}}
* [[다항 분포]]
 
== 바깥 고리 ==