다항 계수

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

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

1. 개요

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

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. 성질

다항 계수는 다음과 같은 성질을 갖는다.^[1]

$|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^영어)의 개수^[1]
다항 전개의 계수

다항 계수

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

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}

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

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com