다항 계수

수학에서, 다항 계수(多項係數, 영어: multinomial coefficient)는 주어진 개수의 원소들을 주어진 크기의 상자들에 넣는 방법의 가짓수이다. 다항 정리(多項定理, 영어: multinomial theorem)는 다항식의 거듭제곱을 전개하는 정리이며, 전개식의 계수는 다항 계수이다. 다항 계수와 다항 정리는 이항 계수와 이항 정리의 일반화이다.

정의

음이 아닌 정수들의 합 $n=k_{1}+k_{2}+\cdots +k_{m}$이 주어졌을 때, 다항 계수 $\textstyle {\binom {n}{k_{1},k_{2},\dots ,k_{m}}}$는 다음과 같다.

${\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}}}$

다항 계수를 단체에 나열한 표를 파스칼의 단체(Pascal의單體, 영어: Pascal's simplex)라고 한다.

성질

항등식

다음과 같은 점화식이 성립한다.

${\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}}}$

다음과 같은 합 공식이 성립한다. 이는 다항 정리의 따름정리이다.

$\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}$

수론적 성질

다항 계수의 소인수의 중복도를 쿠머 정리를 통해 계산할 수 있다.

조합론적 성질

다항 계수 $\textstyle {\binom {n}{k_{1},k_{2},\dots ,k_{m}}}$은 조합론적으로 다음과 같이 해석할 수 있다.

• $|P^{-1}(i)|=k_{i}$ ($i=1,2,\dots ,m$)을 만족시키는 함수 $P\colon \{1,2,\dots ,n\}\to \{1,2,\dots ,m\}$의 수
  • 즉, $n$개의 공을 크기가 각각 $k_{i}$인 $m$개의 상자에 넣는 방법의 수
• 중복집합 $k_{1}\{1\}+k_{2}\{2\}+\cdots +k_{n}\{n\}$의 순열의 수
  • 즉, $n$글자 단어가 각각 $k_{i}$번 나오는 $m$가지 글자로 이루어졌을 때, 그 단어의 어구전철의 수
• $\mathbb {Z} ^{m}$ 위의, 시작점이 0, 끝점이 $(k_{1},k_{2},\dots ,k_{m})$, 보폭이 표준 기저인 격자 경로(영어: lattice path)의 개수
• 다항 전개의 계수

응용

다항 정리

다항 정리에 따르면, 다음과 같은 다항식의 전개가 성립한다.

$(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}}$

다중지표 표기법을 사용하여 다항 정리를 다음과 같이 적을 수 있다.

$(x_{1}+x_{2}+\cdots +x_{m})^{n}=\sum _{K\in \mathbb {N} ^{m}}^{|K|=n}{\binom {n}{K}}x^{K}$

전개식의 항의 개수는 다음과 같이 이항 계수로 나타낼 수 있다.

${\binom {n+m-1}{m-1}}$

증명:

이항 정리와 수학적 귀납법을 사용하여 증명할 수 있다. 우선, $m=0,1$의 경우는 자명하게 성립하며, $m=2$의 경우는 이항 정리에 따라 성립한다.

$0^{n}={\begin{cases}0&n>0\\1&n=0\end{cases}}$

$x_{1}^{n}=x_{1}^{n}$

$(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}}$

이제, $m$에 대하여 성립한다고 가정하자. 그렇다면, 다음이 성립한다.

${\begin{aligned}(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{aligned}}$

즉, $m+1$에 대하여 성립한다. 수학적 귀납법에 따라, 임의의 $m\in \mathbb {N}$에 대하여 다항 정리가 성립한다.

다항 분포

 이 부분의 본문은 다항 분포입니다.

외부 링크

• 이철희. “다항정리”. 《수학노트》. 
• “Multinomial coefficient”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Multinomial coefficient”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Multinomial series”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Multinomial theorem”. 《PlanetMath》 (영어). 
• “Multinomial theorem (proof)”. 《PlanetMath》 (영어). 
• “Definition:Multinomial coefficient”. 《ProofWiki》 (영어). 
• “Multinomial theorem”. 《ProofWiki》 (영어). 
• “Multinomial coefficient expressed as product of binomial coefficients”. 《ProofWiki》 (영어).