이항 계수

조합론에서 이항 계수(二項係數, 틀:Llang)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. 틀:목차숨김

정의

자연수 $n$ 및 정수 $k$ 가 주어졌을 때, 이항 계수 $(\binom{n}{k})$ 는 다음과 같다.

(\binom{n}{k}) = {\begin{matrix} n! / (k! (n - k)!) & 0 \leq k \leq n \\ 0 & k < 0 \\ 0 & k > n \end{matrix}

여기서 $!$ 는 계승 (수학)이다. 이항 계수를 $(\binom{n}{k})$ 대신 $_{n} C_{k}$ 나 $C (n, k)$ 로 쓰기도 한다. 이항 계수의 값을 삼각형 모양으로 나열한 표를 파스칼의 삼각형이라고 한다.

$n = 2 k$ 인 경우의 이항 계수를 중심 이항 계수(中心二項係數, 틀:Llang)라고 한다. 이는 다음과 같다 ( $k = 0, 1, 2, \dots$ ).

1, 2, 6, 20, 70, 252, 924, 432, 12870, 48620, … 틀:OEIS

성질

항등식

이항 계수는 다음과 같은 항등식을 만족시킨다. 이는 이항 계수의 정의로부터 쉽게 증명할 수 있다.

(\binom{n}{k}) = (\binom{n}{n - k})

다음과 같은 점화식이 성립하며, 이는 파스칼의 법칙(Pascal-法則, 틀:Llang)이라고 한다.

(\binom{n}{k}) + (\binom{n}{k + 1}) = (\binom{n + 1}{k + 1})

급수 공식

이항 계수는 다음과 같은 급수 공식들을 만족시킨다. 이들은 대부분 생성 함수(의 도함수)의 특수한 값으로 얻어진다.

이항 계수의 합

이 공식들은 생성함수 $(1 + x)^{n}$ (의 도함수)의 $x = 1$ 값으로부터 유도할 수 있다.

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

\sum_{k = 0}^{n} k (\binom{n}{k}) = n 2^{n - 1}

또한, 피보나치 수를 다음과 같이 나타낼 수 있다.

\sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) = F (n + 1)

여기서 $F (n)$ 은 $n$ 번째 피보나치 수이다.

이항 계수의 곱의 합

다음 항등식은 주세걸-방데르몽드 항등식(朱世傑-Vandermonde恒等式, 틀:Llang)이라고 한다.

\sum_{j = 0}^{k} (\binom{m}{j}) (\binom{n}{k - j}) = (\binom{m + n}{k})

이항계수의 제곱의 합은 다음과 같이 중심 이항 계수로 주어진다.

\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n})

이는 조합론적으로 증명할 수 있다. $(\binom{2 n}{n})$ 은 크기가 $2 n$ 집합 속에서 $n$ 개의 조합의 가짓수인데, 이는 크기 $2 n$ 의 집합의 처음 절반에서 $k$ 개를 고르고, 나머지 절반에서 $n - k$ 개를 고르는 가짓수의 $k$ 에 대한 합 $\sum_{k = 0}^{n} (\binom{n}{k}) (\binom{n}{n - k}) = \sum_{k = 0}^{n} {(\binom{n}{k})}^{2}$ 과 같다.

생성 함수

이항 계수는 다음과 같은 생성 함수를 갖는다.

\sum_{k = 0}^{n} (\binom{n}{k}) x^{k} = (1 + x)^{n}

\sum_{n = k}^{\infty} (\binom{n}{k}) x^{n} = \frac{x^{k}}{(1 - x)^{k + 1}}

\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n} = \frac{1}{1 - y - x y}

\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} \frac{1}{(n + k)!} (\binom{n + k}{k}) x^{k} y^{n} = \exp (x + y)

중심 이항 계수의 생성 함수는 다음과 같다.

\sum_{n = 0}^{\infty} (\binom{2 n}{n}) x^{n} = \frac{1}{\sqrt{1 - 4 x}}

점근 공식

일반적으로, 모든 $n \in ℕ$ 및 $k \in {1, \dots, n}$ 에 대하여, 다음과 같은 부등식이 성립한다.

(n / k)^{k} \leq (\binom{n}{k}) \leq n^{k} / k! \leq (e n / k)^{k}

중심 이항 계수의 경우 다음 부등식이 성립한다.

\frac{4^{n}}{\sqrt{4 n}} \leq (\binom{2 n}{n}) \leq \frac{4^{n}}{\sqrt{3 n + 1}} \forall n \geq 1

$n ≫ 1$ 및 $| 1 / 2 - k / n | ≪ 1$ 에 대하여, 스털링 근사를 사용하여 이항계수를 다음과 같이 근사할 수 있다.

(\binom{n}{k}) \approx \frac{2^{n + 1}}{\sqrt{2 π n}} \exp (- (2 k - n)^{2} / 2 n)

이에 따라, 이항분포를 정규분포로 근사할 수 있다. 특히, $k = n / 2$ 일 경우 중심 이항 계수의 스털링 근사는 다음과 같다.

(\binom{n}{n / 2}) \approx \frac{2^{n + 1}}{\sqrt{2 π n}}

이다.

만약 $n ≫ 1$ 이며 $n ≫ k$ 라면, 스털링 근사를 사용하여 이항 계수를 다음과 같이 근사할 수 있다.

(\binom{n}{k}) \sim \frac{(n / k - 1 / 2)^{k} \exp (k)}{\sqrt{2 π k}}

수론적 성질

쿠머 정리(Kummer定理, 틀:Llang)에 따르면, 음이 아닌 정수 $n \geq k$ 및 소수 $p$ 에 대하여,

p^{c} ∣ (\binom{n}{k})

인 최대 $c$ 는 다음과 같다.

c = | {b \in ℤ^{+} : k / p^{b} - ⌊ k / p^{b} ⌋ > n / p^{b} - ⌊ n / p^{b} ⌋} |

즉, 이는 $k + (n - k)$ 를 $p$ 진법에서 계산할 때 받아올림의 수와 같다.

뤼카의 정리는 이항계수의 소수에 대한 나머지의 값을 제시한다.

중심 이항 계수 $(\binom{2 n}{n})$ 은 $n > 4$ 에 대하여 항상 제곱 인수가 없는 정수이다. 이를 에르되시 추측(Erdős推測, 틀:Llang)라고 한다. 에르되시 팔이 1980년에 추측하였고,^[1] 앤드루 그랜빌(틀:Llang)과 올리비에 라마레(틀:Llang)가 1996년에 증명하였다.^[2]

임의의 양의 정수 $d \in ℤ^{+}$ 에 대하여, 다음이 성립한다.

\lim_{N \to \infty} \frac{| {n < N : d ∣ (\binom{n}{k})} |}{N (N + 1) / 2} = 1

$N (N + 1) / 2 = \sum_{n = 0}^{N - 1} \sum_{k = 0}^{n} 1$ 은 $n < N$ 인 이항계수 $(\binom{n}{k})$ 의 수이므로, 임의의 양의 정수는 거의 모든 이항계수를 약수로 가진다. 이는 데이비드 싱매스터(틀:Llang)가 1974년에 증명하였다.^[3]

초한 이항 계수

이항 계수의 정의는 임의의 기수에 대하여 확장할 수 있다. 임의의 기수 $κ, λ$ 에 대하여, 초한 이항 계수(超限二項係數, 틀:Llang)

(\binom{κ}{λ})

는 크기가 $κ$ 인 집합의, 크기가 $λ$ 인 부분 집합들의 수이다. 만약 $κ$ 와 $λ$ 가 둘 다 유한 기수라면 이는 자연수의 이항 계수의 정의와 일치한다.

초한 이항 계수의 값은 다음과 같다.

(\binom{κ}{λ}) = {\begin{matrix} κ^{λ} & λ \leq κ \geq ℵ_{0} \\ 0 & λ > κ \\ (\binom{n}{k}) & k = λ < ℵ_{0}, n = κ < ℵ_{0} \end{matrix}

첫 번째 경우는

κ^{λ} \leq (\binom{κ λ}{λ}) = (\binom{κ}{λ}) \leq κ^{λ}

이기 때문이다. (여기서 첫 부등식은 $λ$ 개의, 크기가 $κ$ 인 집합들에서 각각 하나의 원소를 뽑는 것이다.)

특히, 중심 이항 계수는 다음과 같다.

(\binom{2 κ}{κ}) = (\binom{κ}{κ}) = 2^{κ}

초한 이항 계수의 경우, 유한 이항 계수에 대하여 성립하는 대칭성이 일반적으로 성립하지 않는다.

(\binom{κ + λ}{λ}) \neq (\binom{κ + λ}{κ})

예를 들어

(\binom{1 + ℵ_{0}}{1}) = ℵ_{0}

(\binom{1 + ℵ_{0}}{ℵ_{0}}) = 2^{ℵ_{0}}

이다.

응용

조합론

조합론에서, 이항 계수는 크기가 $n$ 인 유한 집합의 크기가 $k$ 인 부분집합의 수이다. 즉, $n$ 개의 원소의 $k$ 개의 조합의 수이다. 이 밖에도, 이항계수는 다음과 같은 다양한 조합론적 문제에 등장한다.

카탈랑 수 $C_{n} = (\binom{2 n}{n}) / (n + 1) = (\binom{2 n}{n}) - (\binom{2 n}{n + 1})$ 는 다양한 조합론적 문제의 해이다.
크기가 $n$ 인 집합에서, 크기가 $k$ 인 중복집합을 고를 수 있는 가짓수는 $(\binom{n + k - 1}{k})$ 이다.
$k$ 개의 기호 $∙$ 및 $n$ 개의 기호 $\circ$ 를 포함하는 문자열의 수는 $(\binom{n + k}{k})$ 이다. 또한, $∙ ∙$ 을 부분 문자열로 포함하지 않는 문자열의 수는 $(\binom{n + 1}{k})$ 이다.

대수학

틀:본문 이항 계수는 대수학에서 다음과 같이 이항급수의 전개에 사용되며, "이항계수"라는 이름은 이로부터 유래한다.

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k}

통계학

틀:본문 통계학에서, 이항 계수는 이항분포를 정의하는 데 사용된다.

정수론

베르트랑의 공준을 증명할 때, 중심 이항 계수의 성질로부터 시작한다. 또한, 중심 이항 계수는 아페리 상수 $ζ (3)$ 가 무리수임을 증명할 때 쓰이는 급수

ζ (3) = \frac{5}{2} \sum_{n = 1}^{\infty} \frac{(- 1)^{n + 1}}{n^{3} (\binom{2 n}{n})}

에 등장한다.

역사

이항 계수는 파스칼의 삼각형의 형태로 이미 중세 동서양 수학에 알려져 있었다. 오늘날 쓰이는 표기법 $(\binom{n}{k})$ 은 안드레아스 프라이헤르 폰 에팅스하우젠(틀:Llang)이 1826년에 도입하였다.

같이 보기

각주

틀:각주

외부 링크

틀:전거 통제

[1] 틀:서적 인용

[2] 틀:저널 인용

[3] 틀:저널 인용

[1]

[2]

[3]