다항 계수

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

정의

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

${\displaystyle {\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)라고 한다.

성질

항등식

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

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

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

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

수론적 성질

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

조합론적 성질

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

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

응용

다항 정리

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

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

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

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

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

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

증명:

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

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

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

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

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

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

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

다항 분포

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