다항 계수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

다항 계수는 음이 아닌 정수들의 합이 주어졌을 때 정의되는 계수이며, 이항 계수를 일반화한 개념이다. 다항 계수는 조합론적으로 특정 함수의 개수, 중복 집합의 순열 개수, 격자 경로의 개수 등과 관련되며, 다항 정리 및 다항 분포와 같은 수학적 개념에 활용된다. 다항 정리에서는 다항식의 전개를 나타내며, 다항 분포는 여러 범주에 대한 확률 분포를 표현하는 데 사용된다.

다항 계수

📚 더 읽어볼만한 페이지

대수학 정리 - 힐베르트 기저 정리
힐베르트 기저 정리는 가환환 R이 뇌터 환일 때 R을 계수로 하는 다항식환 R[x_1,...,x_n] 역시 뇌터 환임을 명시하는 정리이며, 대수기하학에서 대수적 집합을 유한 개의 다항식의 공통근으로 해석할 수 있게 한다.
대수학 정리 - 힐베르트 영점 정리
힐베르트 영점정리는 대수기하학에서 다항식환의 아이디얼과 대수적 집합 사이의 관계를 나타내는 중요한 정리로, 체 <math>k</math>와 그의 대수적 폐포 <math>K</math>에 대해, 다항식환 <math>k[x_1,x_2,\dots,x_n]</math>의 아이디얼 <math>J</math>의 영점들의 집합 <math>\mathcal V(J)</math>에 대하여, <math>\mathcal I(\mathcal V(J))=\sqrt J</math>가 성립한다는 것을 명시하며, 특히 <math>k</math>가 대수적으로 닫힌 체인 경우, 반소 아이디얼과 대수 집합 사이에 순서를 뒤집는 전단사 대응이 존재함을 의미한다.
계승과 이항식 주제 - 이항 정리
이항 정리는 이변수 다항식 (x + y)ⁿ을 전개하는 공식으로, 이항 계수를 사용하며, 조합론적 증명과 수학적 귀납법을 통해 증명할 수 있고, 다양한 분야에 응용되며, 이항 급수, 다항 정리 등 일반화된 형태가 존재한다.
계승과 이항식 주제 - 감마 분포
감마 분포는 형상 모수와 척도 모수로 정의되는 연속 확률 분포로, 확률 밀도 함수가 감마 함수로 표현되며, 베이즈 통계학에서 켤레 사전 분포로 활용되고, 형상 모수가 양의 정수일 때는 얼랑 분포를 나타낸다.

1. 개요
2. 정의
3. 성질
4. 응용
- 4.1. 다항 정리
- 4.2. 다항 분포

2. 정의

음이 아닌 정수들의 합 $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^영어)라고 한다.

3. 성질

다항 계수는 다음과 같은 성질을 갖는다.

* $|P^{-1}(i)|=k_i$ ( $i=1,2,\dots,m$ )을 만족시키는 함수 $P\colon\{1,2,\dots,n\}\to\{1,2,\dots,m\}$ 의 수.
* 중복집합 $k_1\{1\}+k_2\{2\}+\cdots+k_n\{n\}$ 의 순열의 수
* $\mathbb Z^m$ 위의, 시작점이 0, 끝점이 $(k_1,k_2,\dots,k_m)$ , 보폭이 표준 기저인 격자 경로(lattice path^영어)의 개수

3.1. 항등식

다음과 같은 점화식이 성립한다.
: $\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$
다항 정리라고 불리는 다음 등식이 성립한다.
: $(x_1+\dotsb+x_r)^n = \textstyle\sum\limits_{k_1+\dotsb+k_r=n} \dbinom{n}{k_1,\dotsc,k_r} \cdot {x_1}^{k_1} \dotsm {x_r}^{k_r}$
특히 $x_1 = x_2 = \dots = x_r = 1$ 로 놓으면 다음을 얻을 수 있다.
: $r^n = \textstyle\sum\limits_{k_1+\dotsb+k_r=n} \dbinom{n}{k_1,\dotsc,k_r}$

3.2. 수론적 성질

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

3.3. 조합론적 성질

* $|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^영어)의 개수
* 다항 전개의 계수
다항 계수 $\binom n{k_1,k_2,\dots,k_r}$ 는 $n$ 개의 대상을 $r$ 개의 구별되는 상자에 분할하여 넣을 때, 각 $i$ 번째 상자에 $k_i$ 개만의 대상이 포함되도록 넣는 방법의 총수이다.
다항 계수 $\binom n{k_1,k_2,\dots,k_r}$ 는 $1 \le i \le r$ 에 대해 각각 정확히 $k_i$ 개의 구별 불가능한 대상이 포함된 $n$ 개의 대상의 순열의 총 개수와 같다.

예시로, "MISSISSIPPI"의 아나그램 문자를 재배열하여 얻을 수 있는 서로 다른 "단어"의 개수를 생각해보자.

이 11개의 문자의 순열의 총 개수를 세어야 하는데, 문자 M은 1개, 문자 I는 4개, 문자 S는 4개, 문자 P는 2개이므로 다항 계수는 다음과 같다.
: $\binom{11}{1,4,4,2}=\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!}=34650$
이와 대조적으로, 만약 11개의 문자가 모두 구별 가능하다면, 그 총 개수는 $11! = 39,916,800$ 으로 훨씬 많아진다.

4. 응용

다항 계수는 다항 정리와 다항 분포에 응용된다. 다항 정리는 다항식의 전개를 나타내는 공식이며, 다항 분포는 여러 범주에 대한 확률 분포를 나타내는 데 사용된다. (하위 섹션 내용과 중복되어 최대한 간결하게 작성됨)

4.1. 다항 정리

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

: $(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 nKx^K$

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

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

4.2. 다항 분포

다항 분포는 여러 범주에 대한 확률 분포를 나타내는 데 사용된다. 다항 분포의 확률 질량 함수는 다음과 같다.

: $P(X_1=k_1, X_2=k_2, \dotsc, X_r=k_r) = \binom{n}{k_1, \dotsc, k_r} \cdot p_1^{k_1} \cdot {p_2}^{k_2} \dotsm {p_r}^{k_r}$

이는 이산 확률 변수에 관한 확률 분포이다.