다항 계수

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

정의

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

(\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = \frac{n!}{k_{1}! k_{2}! \dots k_{m}!} = \prod_{i = 1}^{m} (\binom{k_{1} + k_{2} + \dots + k_{i}}{k_{i}}) = \prod_{i = 1}^{m} (\binom{k_{i} + k_{i + 1} + \dots + k_{m}}{k_{i}})

다항 계수를 단체에 나열한 표를 파스칼의 단체(Pascal의單體, 틀:Llang)라고 한다.

성질

항등식

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

(\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = (\binom{n}{k_{1} + \dots + k_{i}, k_{i + 1}, k_{i + 2}, \dots, k_{m}}) (\binom{k_{1} + k_{2} + \dots + k_{i}}{k_{1}, k_{2}, \dots, k_{i}})

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

\sum_{k_{1}, k_{2}, \dots, k_{m} \in ℕ}^{k_{1} + k_{2} + \dots + k_{m} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = m^{n}

수론적 성질

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

조합론적 성질

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

|P−1(i)|=ki (i=1,2,…,m)을 만족시키는 함수 P:{1,2,…,n}→{1,2,…,m}의 수
- 즉, $n$ 개의 공을 크기가 각각 $k_{i}$ 인 $m$ 개의 상자에 넣는 방법의 수
중복집합 k1{1}+k2{2}+⋯+kn{n}의 순열의 수
- 즉, $n$ 글자 단어가 각각 $k_{i}$ 번 나오는 $m$ 가지 글자로 이루어졌을 때, 그 단어의 어구전철의 수
$ℤ^{m}$ 위의, 시작점이 0, 끝점이 $(k_{1}, k_{2}, \dots, k_{m})$ , 보폭이 표준 기저인 격자 경로(틀:Llang)의 개수^[1]
다항 전개의 계수

응용

다항 정리

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

(x_{1} + x_{2} + \dots + x_{m})^{n} = \sum_{k_{1}, k_{2}, \dots, k_{m} \in ℕ}^{k_{1} + k_{2} + \dots + k_{m} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m}^{k_{m}}

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

(x_{1} + x_{2} + \dots + x_{m})^{n} = \sum_{K \in ℕ^{m}}^{| K | = n} (\binom{n}{K}) x^{K}

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

(\binom{n + m - 1}{m - 1})

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

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

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

(x_{1} + x_{2})^{n} = \sum_{k_{1}, k_{2} \in ℕ}^{k_{1} + k_{2} = n} (\binom{n}{k_{1}, k_{2}}) x_{1}^{k_{1}} x_{2}^{k_{2}}

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

\begin{matrix} (x_{1} + x_{2} + \dots + x_{m + 1})^{n} & = \sum_{k_{1}, k_{2}, \dots, k_{m - 1}, ℓ \in ℕ}^{k_{1} + k_{2} + \dots + k_{m - 1} + ℓ = n} \frac{n!}{k_{1}! k_{2}! \dots k_{m - 1}! ℓ!} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m - 1}^{k_{m - 1}} (x_{m} + x_{m + 1})^{ℓ} \\ = \sum_{k_{1}, k_{2}, \dots, k_{m - 1}, ℓ \in ℕ}^{k_{1} + k_{2} + \dots + k_{m - 1} + ℓ = n} \frac{n!}{k_{1}! k_{2}! \dots k_{m - 1}! ℓ!} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m - 1}^{k_{m - 1}} \sum_{k_{m}, k_{m + 1} \in ℕ}^{k_{m} + k_{m + 1} = ℓ} \frac{ℓ!}{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 ℕ}^{k_{1} + k_{2} + \dots + k_{m + 1} = n} \frac{n!}{k_{1}! k_{2}! \dots k_{m + 1}!} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m + 1}^{k_{m + 1}} \end{matrix}

즉, $m + 1$ 에 대하여 성립한다. 수학적 귀납법에 따라, 임의의 $m \in ℕ$ 에 대하여 다항 정리가 성립한다. 틀:증명 끝

다항 분포

틀:본문

각주

틀:각주

외부 링크

↑ 틀:서적 인용

[Stanley-1] 틀:서적 인용

[1]

다항 계수

목차

정의

성질

항등식

수론적 성질

조합론적 성질

응용

다항 정리

다항 분포

각주

외부 링크

둘러보기 메뉴

다항 계수

정의

성질

항등식

수론적 성질

조합론적 성질

응용

다항 정리

다항 분포

각주

외부 링크

둘러보기 메뉴

검색