맨위로가기

이항 계수

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

1. 개요

이항 계수는 주어진 개수의 원소에서 특정 개수를 선택하는 조합의 가짓수를 나타내는 수이며, 수학 및 조합론에서 중요한 개념으로 사용된다. 자연수 n과 정수 k에 대해 정의되며, 팩토리얼을 사용하여 계산하거나 파스칼의 삼각형을 통해 값을 구할 수 있다. 이항 계수는 다양한 항등식과 급수 공식을 만족하며, 생성 함수를 통해 표현할 수 있다. 또한, 점근 공식을 통해 근사값을 계산할 수 있으며, 수론적 성질과 다항식으로서의 성질을 갖는다. 이항 계수는 조합론, 이항 급수, 통계학 등 다양한 분야에 응용되며, 다항 계수, 다중집합 계수, 실수 및 복소수, 가우스 이항 계수, 무한 기수 등으로 일반화될 수 있다.

2. 정의

자연수 n 및 정수 k가 주어졌을 때, 이항 계수 \tbinom nk는 다음과 같이 정의된다.

:\binom nk=\begin{cases} \frac{n!}{k!(n-k)!} & 0\le k\le n\\ 0 & k<0 \text{ 또는 } k>n \end{cases}

여기서 !는 계승을 나타낸다. 이항 계수는 \tbinom nk 대신 {}_nC_k나 C(n, k)로 표기하기도 한다. 이항 계수의 값을 삼각형 모양으로 배열한 것을 파스칼의 삼각형이라고 부른다.

n / k01234⋯
010000⋯
111000⋯
212100⋯
313310⋯
414641⋯
⋮⋮⋮⋮⋮⋮⋱
처음 몇 개의 이항 계수 (왼쪽 정렬된 파스칼의 삼각형)



특히 n=2k인 경우의 이항 계수 \tbinom{2k}{k}를 중심 이항 계수(central binomial coefficient영어)라고 한다. 중심 이항 계수의 처음 몇 항은 다음과 같다 (k=0,1,2,\dots).

:1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, …

이항 계수는 이항 정리와 밀접한 관련이 있다. 0을 포함하는 자연수 ''n''과 ''k''에 대해, 이항 계수 \tbinom nk는 다항식 (1 + X)^n을 전개했을 때 단항식 X^k의 계수와 같다. 더 일반적으로, 가환환의 임의의 원소 ''x'', ''y''에 대해 다음 이항 정리가 성립하며, 이 때문에 "이항 계수"라는 이름이 붙었다.

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

조합론에서 이항 계수 \tbinom nk는 ''n''개의 서로 다른 원소로 이루어진 집합에서 순서를 고려하지 않고 ''k''개의 원소를 선택하는 방법의 수, 즉 크기가 ''k''인 부분집합의 개수와 같다. 이는 ''k''-조합의 수라고도 한다. 이 조합론적 정의가 앞서 제시된 대수적 정의와 일치함은 다음과 같이 설명할 수 있다. (1+X)^n = (1+X)(1+X)\cdots(1+X) (''n''개의 인수)를 전개할 때, 각 인수에서 1 또는 X를 선택하여 곱하게 된다. X^k 항은 ''n''개의 인수 중 ''k''개의 인수에서 X를 선택하고 나머지 ''n-k''개의 인수에서 1을 선택하여 곱할 때 만들어진다. 따라서 X^k의 계수는 ''n''개의 인수 중 X를 선택할 ''k''개의 인수를 고르는 조합의 수, 즉 \tbinom nk와 같다. 이 설명은 이항 계수 \tbinom nk가 항상 자연수임을 보여준다.

이항 계수는 다양한 조합론적 문제의 해답으로 등장한다. 예를 들어,


  • ''n''개의 비트(0 또는 1)로 이루어진 문자열 중 1의 개수가 정확히 ''k''개인 문자열의 수는 \tbinom nk이다.
  • 음이 아닌 정수 a_1, a_2, \dots, a_n에 대해 방정식 a_1 + a_2 + \cdots + a_n = k를 만족하는 해의 개수는 \tbinom{n+k-1}{n-1}이다. (이는 중복조합에 해당한다.)


이항 계수에 대한 가장 오래된 기록 중 하나는 10세기경 할라유다(Halayudha)가 고대 산스크리트어로 쓴 핀갈라(Pingala)의 Chandaḥśāstra에 대한 주석이다. 1150년경 인도의 수학자 바스카라 2세(Bhāskara II)는 그의 저서 लीलावती|릴라바티sa에서 이항 계수에 대해 상세히 설명했다.[21]

기호 \tbinom nk는 1826년 안드레아스 폰 에팅스하우젠(Andreas von Ettingshausen)에 의해 도입되었다.[22] 이 외에도 C(n, k), {}_nC_k, {}^nC_k, C^k_n, C^n_k[23] 등 다양한 표기법이 사용되며, 여기서 문자 C는 조합(combination) 또는 선택(choice)을 의미한다.

3. 역사

이항 계수는 파스칼의 삼각형 형태로 이미 중세 동서양 수학에 알려져 있었다. 이항 계수에 대해 자세히 알려진 가장 초기의 논의는 10세기경 할라유다(Halayudha)가 고대 산스크리트어로 쓴 핀갈라(Pingala)의 Chandaḥśāstra에 있다. 이후 1150년경, 인도 수학자 바스카라 2세(Bhāskara II)는 그의 저서 ''릴라바티''(Līlāvatī)에서 이항 계수에 대한 설명을 제시했다.[2][21]

오늘날 흔히 쓰이는 이항 계수 표기법 \tbinom nk는 1826년 안드레아스 폰 에팅스하우젠(Andreas von Ettingshausen)이 도입하였다.[1][22]

4. 성질

왼쪽 정렬된 파스칼의 삼각형



0을 포함하는 자연수 ''n''과 ''k''에 대해 이항 계수 \binom nk는 다항식 (1 + X)^n을 전개했을 때 단항식 X^k의 계수로 정의할 수 있다. 같은 계수는 k \le n일 때 이항 정리

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

(임의의 가환환의 원소 ''x'', ''y''에 대해 성립)에서도 나타나는데, 이것이 "이항 계수"라는 이름이 붙은 이유다.

이항 계수는 조합론에서도 중요한 의미를 가진다. 이는 순서를 고려하지 않고 ''n''개의 원소를 가진 집합에서 ''k''개의 원소를 선택하는 방법의 수, 즉 크기가 ''k''인 부분집합(또는 ''k''-조합)의 개수와 같다. 이 조합론적 정의는 앞서 언급한 대수적 정의와 동일한 값을 가진다. 예를 들어, (1 + X)^n을 (1+X)를 ''n''번 곱한 것으로 생각하면, X^k 항은 ''n''개의 (1+X) 중에서 ''k''개를 선택하여 ''X''를 곱하고 나머지 ''n-k''개에서는 1을 곱하여 만들어진다. 따라서 X^k의 계수는 ''n''개 중 ''k''개를 선택하는 조합의 수 \binom nk와 같아진다. 이 조합론적 해석을 통해 이항 계수 \binom nk가 항상 자연수임을 알 수 있다. 이항 계수는 다른 여러 조합 문제의 해답으로도 등장한다. 예를 들어, 0과 1로 이루어진 길이 ''n''의 비트 문자열 중 1의 개수가 ''k''인 문자열의 수는 \binom nk이고, 음이 아닌 정수 해 a_1 + a_2 + \cdots + a_n = k의 개수는 \binom{n+k-1}{n-1}이다.

이항 계수 사이에는 파스칼의 법칙으로 알려진 중요한 점화식 관계가 성립하며, 이는 파스칼 삼각형을 구성하는 기본 원리가 된다. 파스칼의 법칙은 이항 계수가 항상 자연수임을 수학적 귀납법으로 증명하는 데 사용될 수도 있다.

파스칼 삼각형은 이항 계수를 시각적으로 배열한 것이다. ''n''번째 행에는 ''k'' = 0, 1, ..., ''n''에 대한 이항 계수 \binom nk가 순서대로 나열된다. 각 행의 양 끝 값은 1이며, 삼각형 내부의 각 값은 바로 위 행의 인접한 두 값의 합과 같다. 이 방법을 사용하면 분수나 곱셈 없이 이항 계수를 빠르게 계산할 수 있다.

0:1
1:11
2:121
3:1331
4:14641
5:15101051
6:1615201561
7:172135352171
8:18285670562881



예를 들어, 삼각형의 5번째 행을 보면 (x + y)^5 = \mathbf{1}x^5 + \mathbf{5}x^4y + \mathbf{10}x^3y^2 + \mathbf{10}x^2y^3 + \mathbf{5}xy^4 + \mathbf{1}y^5 와 같이 계수를 바로 알 수 있다.

4. 1. 항등식

이항 계수는 다양한 항등식을 만족시킨다. 이들은 이항 계수의 정의, 조합적 해석, 또는 수학적 귀납법 등을 통해 증명될 수 있다.

'''대칭성'''

가장 기본적인 항등식 중 하나는 대칭성이다.

:\binom nk = \binom n{n-k} \quad (0 \le k \le n)

이는 크기 ''n''인 집합에서 ''k''개의 원소를 선택하는 것이 나머지 ''n''-''k''개의 원소를 선택하는 것과 같다는 조합적 의미를 가진다. 팩토리얼 공식을 사용하면 \frac{n!}{k!(n-k)!} 로 양변이 같음을 쉽게 확인할 수 있다. 이 대칭성은 계산 시 ''k''와 ''n''-''k'' 중 작은 값을 선택하여 효율성을 높이는 데 사용될 수 있다.

'''파스칼의 법칙 (점화식)'''

다음의 점화식은 '''파스칼의 법칙'''(Pascal's rule영어)으로 알려져 있으며, 파스칼의 삼각형을 구성하는 기본 원리가 된다.[1]

:\binom nk + \binom n{k+1} = \binom{n+1}{k+1}

이는 다음과 같은 형태로도 자주 사용된다.

:\binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad (1 \le k < n)

이 식은 크기 ''n''인 집합 {1, 2, ..., ''n''}에서 ''k''개의 원소를 선택하는 경우를 특정 원소(예: ''n'')를 포함하는 경우(\binom{n-1}{k-1})와 포함하지 않는 경우(\binom{n-1}{k})로 나누어 생각함으로써 조합적으로 유도할 수 있다. 파스칼의 법칙과 경계값 \binom n0 = \binom nn = 1 (모든 정수 ''n'' ≥ 0)을 이용하면 모든 이항 계수를 재귀적으로 계산할 수 있다. 파스칼의 법칙은 또한 이항 계수가 항상 자연수임을 수학적 귀납법으로 증명하는 데 사용될 수 있다.

파스칼의 삼각형은 파스칼의 법칙을 시각적으로 나타낸 것이다. ''n''번째 행에는 ''k'' = 0, ..., ''n''에 대한 이항 계수 \binom{n}{k}가 나열된다. 각 내부 값은 바로 위 두 값의 합과 같다.

0:1
1:11
2:121
3:1331
4:14641
5:15101051
6:1615201561
7:172135352171
8:18285670562881



'''곱셈 공식 및 팩토리얼 공식'''

개별 이항 계수를 직접 계산하는 효율적인 방법은 내림차순 계승을 이용한 다음 공식이다.

:\binom nk = \frac{n^{\underline{k}}}{k!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1} = \prod_{i=1}^k\frac{ n+1-i}{ i}

이는 크기 ''n''인 집합에서 ''k''개의 원소를 순서대로 뽑는 경우의 수(n^{\underline{k}})를 ''k''개 원소의 순열 수(''k''!)로 나눈 값으로 해석할 수 있다.

팩토리얼 함수를 이용한 간결한 형태는 다음과 같으며, 증명이나 다른 항등식 유도에 자주 사용된다.

:\binom nk = \frac{n!}{k!\,(n-k)!}

이 공식은 곱셈 공식의 분자와 분모에 (''n''-''k'')!를 곱하여 얻을 수 있다. 대칭성을 명확하게 보여주지만, 팩토리얼 값이 매우 빠르게 커지므로 직접 계산에는 비효율적일 수 있다.

'''합계 관련 항등식'''


:\sum_{k=0}^n \binom n k = 2^n

이는 이항 정리 (x+y)^n = \sum_{k=0}^n \binom nk x^{n-k} y^k에 ''x'' = ''y'' = 1을 대입하거나, 크기 ''n''인 집합의 모든 부분집합의 개수를 세는 조합적 방법으로 증명할 수 있다.
:\sum_{k=0}^n k \binom{n}{k} = n 2^{n-1}

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

이들은 이항 정리를 ''x''에 대해 미분한 후 ''x'' = ''y'' = 1을 대입하여 얻을 수 있다.
:\sum_{j=0}^k \binom m j \binom{n-m}{k-j} = \binom n k

이는 (1+x)^n = (1+x)^m (1+x)^{n-m}의 양변에서 x^k의 계수를 비교하여 증명할 수 있다.
:\sum_{j=0}^m \binom{m}{j} ^2 = \binom {2m} m

여기서 우변은 중심 이항 계수이다.
:\sum_{m=j}^n \binom m j \binom {n-m}{k-j}= \binom {n+1}{k+1}
:\sum_{m=k}^n \binom m k = \binom {n+1}{k+1}

:\sum_{r=0}^m \binom {n+r} r = \binom {n+m+1}{m}

'''피보나치 수 관련 항등식'''

''F''(''n'')을 ''n''번째 피보나치 수(F(0)=0, F(1)=1)라고 할 때, 다음이 성립한다.

: \sum_{k=0}^{\lfloor n/2\rfloor} \binom {n-k} k = F(n+1)

이는 수학적 귀납법이나 체켄도르프 정리, 또는 타일링을 이용한 조합 증명으로 보일 수 있다.[13]

'''기타 점화식 및 관계식'''

다음은 이항 계수들 사이의 다양한 관계를 보여주는 식들이다.

요약하면, 다음과 같은 관계들이 성립한다.

:\binom {n}{k} = \binom n{n-k} = \frac{n-k+1}{k} \binom {n}{k-1} = \frac{n}{n-k} \binom {n-1}{k} = \frac{n}{k} \binom {n-1}{k-1}

:= \frac{n}{n-2k} \left(\binom {n-1}{k} - \binom{n-1}{k-1}\right) = \binom{n-1}k + \binom{n-1}{k-1}

'''조합 증명 예시'''

많은 이항 계수 항등식은 조합 증명 또는 이중 계산을 통해 직관적으로 이해하고 증명할 수 있다.

4. 2. 급수 공식

이항 계수는 다양한 급수 공식을 만족시킨다. 이 공식들은 주로 생성함수 (1+x)^n 또는 그 도함수의 특정 값에서 유도된다.

가장 기본적인 합 공식은 다음과 같다.

:\sum_{k=0}^n\binom nk=2^n

이 공식은 생성함수 (1+x)^n에 x=1을 대입하여 얻을 수 있으며, 크기가 n인 집합의 모든 부분집합의 개수가 2^n임을 의미한다.

다음 공식들은 생성함수를 미분한 후 x=1을 대입하여 유도할 수 있다.

:\sum_{k=0}^nk\binom nk=n2^{n-1}

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

이항 계수의 부분합에 대한 공식도 존재한다. 예를 들어, k = 0, \dots, n-1에 대해 다음이 성립한다.

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

특히 n>0일 때, 모든 항을 더하면 다음과 같다.

:\sum_{j=0}^n (-1)^j\binom n j = 0

이항 계수는 피보나치 수와도 관련이 있다. F(n)을 n번째 피보나치 수라고 할 때 다음 등식이 성립한다.

: \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}k =F(n+1)

이 공식은 파스칼의 삼각형에서 대각선 방향으로 항들을 더하면 피보나치 수가 나타나는 것을 보여준다.

'''주세걸-방데르몽드 항등식'''(Zhu–Vandermonde identity영어)은 다음과 같다.

: \sum_{j=0}^k\binom mj\binom n{k-j}=\binom{m+n}k

이 항등식은 (1+x)^{m+n} = (1+x)^m (1+x)^n의 양변에서 x^k의 계수를 비교하여 증명할 수 있다.

이 항등식의 특별한 경우로, 이항 계수의 제곱의 합 공식이 있다.

: \sum_{k=0}^{n} \binom nk^2 =\binom{2n}n

이는 위 방데르몽드 항등식에서 m=n, k=n을 대입하고 \binom{n}{n-j} = \binom{n}{j}임을 이용하여 유도할 수 있다. 우변의 \binom{2n}{n}은 중심 이항 계수이다. 이 공식은 크기가 2n인 집합에서 n개의 원소를 선택하는 경우의 수를 두 가지 방법으로 세어 조합론적으로 증명할 수도 있다.

하키 스틱 항등식은 방데르몽드 항등식의 또 다른 형태로 유도될 수 있다.

:\sum_{m=k}^n \binom m k = \binom {n+1}{k+1}

:\sum_{r=0}^m \binom {n+r} r = \binom {n+m+1}{m}

급수 분할(Series multisection)을 이용하면 특정 간격으로 이항 계수를 더한 합을 구할 수 있다. 0 \le t < s인 정수 s, t에 대해 다음이 성립한다.

:\binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\ldots=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s}

예를 들어 s=3일 경우 다음과 같은 공식들을 얻는다.[9]

: \binom{n}{0} + \binom{n}{3}+\binom{n}{6}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{n\pi}{3}\right)

: \binom{n}{1} + \binom{n}{4}+\binom{n}{7}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{(n-2)\pi}{3}\right)

: \binom{n}{2} + \binom{n}{5}+\binom{n}{8}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{(n-4)\pi}{3}\right)

딕슨 항등식은 다음과 같다.

:\sum_{k=-a}^{a}(-1)^{k}{2a\choose k+a}^3 =\frac{(3a)!}{(a!)^3}

더 일반적인 형태는 다음과 같다.

:\sum_{k=-a}^a(-1)^k{a+b\choose a+k} {b+c\choose b+k}{c+a\choose c+k} = \frac{(a+b+c)!}{a!\,b!\,c!}\,,

여기서 ''a'', ''b'', ''c''는 음이 아닌 정수이다.

특정 삼각함수 적분은 이항 계수로 표현될 수 있다. 임의의 음이 아닌 정수 m, n에 대해 다음이 성립한다.

:\int_{-\pi}^{\pi} \cos((2m-n)x)\cos^n(x)\ dx = \frac{\pi}{2^{n-1}} \binom{n}{m}

:

\int_{-\pi}^{\pi} \sin((2m-n)x)\sin^n(x)\ dx =

\begin{cases}

(-1)^{m+(n+1)/2} \frac{\pi}{2^{n-1}} \binom{n}{m}, & n \text{이 홀수일 때} \\

0, & \text{그 외}

\end{cases}

:

\int_{-\pi}^{\pi} \cos((2m-n)x)\sin^n(x)\ dx =

\begin{cases}

(-1)^{m+(n/2)} \frac{\pi}{2^{n-1}} \binom{n}{m}, & n \text{이 짝수일 때} \\

0, & \text{그 외}

\end{cases}

이 식들은 오일러 공식을 사용하여 삼각함수를 복소 지수 함수로 변환하고, 이항 정리를 이용하여 전개한 뒤 항별로 적분하여 증명할 수 있다.

4. 3. 생성 함수

이항 계수는 여러 형태의 생성 함수를 가진다.
:\sum_{k=0}^\infty {n\choose k} x^k = (1+x)^n.
:\sum_{n=k}^\infty\binom nk y^n = \frac{y^k}{(1-y)^{k+1}}.
:\sum_{n=0}^\infty \sum_{k=0}^n {n\choose k} x^k y^n = \frac{1}{1-y-xy}.
:\sum_{n=0}^\infty \sum_{k=0}^\infty {n+k\choose k} x^k y^n = \frac{1}{1-x-y}.
:\sum_{n=0}^\infty \sum_{k=0}^\infty {n+k\choose k} \frac{x^k y^n}{(n+k)!} = e^{x+y}.

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

:\sum_{n=0}^\infty\binom{2n}nx^n=\frac1{\sqrt{1-4x}}

4. 4. 점근 공식

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

:\left( \frac{n}{k} \right)^k \le \binom{n}{k} \le \frac{n^k}{k!} \le \left( \frac{n\cdot e}{k} \right)^k

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

:\frac{4^n}{\sqrt{4n}} \le \binom{2n}{n} \le \frac{4^n}{\sqrt{3n+1}}\qquad\forall n\ge1

최소공배수를 이용한 다음 부등식도 알려져 있다.[14]

:\frac{\operatorname{lcm}(n-k, \ldots, n)}{(n-k) \cdot \operatorname{lcm}\left(\binom{k}{0}, \ldots, \binom{k}{k}\right)}\leq\binom{n}{k} \leq \frac{\operatorname{lcm}(n-k, \ldots, n)}{n - k}

스털링 근사를 사용하면 \binom{n}{k}에 대한 다양한 점근 공식을 얻을 수 있다.
:\binom{n}{k} \sim \frac{1}{\sqrt{2\pi k}} \left(\frac{ne}{k}\right)^k \exp\left(- \frac{k^2}{2n}(1 + o(1))\right)[18]

여기서 o는 소문자 o 표기법이다. 로그 형태로 나타내면 다음과 같다.

:\log \binom{n}{k} \approx k \ln\left( \frac{n}{k} -0.5\right)+k-0.5 \ln(2 \pi k)

더 정확한 근사는 다음과 같다.

:\log \binom{n}{k} \approx (n+0.5) \ln\frac{n+0.5}{n-k+0.5} + k \ln \frac{n-k+0.5}{k} - 0.5 \ln(2 \pi k)
:\binom{n}{k} \sim \binom{n}{\frac{n}{2}} e^{-d^2/(2n)} \sim \frac{2^n}{\sqrt{\frac{1}{2}n \pi }} e^{-d^2/(2n)} (여기서 d = n - 2k)[17]

이는 정규 분포를 이용한 근사와도 관련 있다. n이 충분히 클 때,

:\binom{n}{k} = \frac{2^n}{\sqrt{\tfrac{1}{2}n \pi}} e^{-\frac{(k-(n/2))^2}{n/2}}\left[1+O\left(\frac{1}{\sqrt{n}}\right)\right]
:\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}

다음 부등식도 성립한다.

:\sqrt{n}\binom{2n}{n} \ge 2^{2n-1}

더 일반적으로, m \ge 2이고 n \ge 1일 때 다음이 성립한다.

:\sqrt{n}\binom{mn}{n} \ge \frac{m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}
:{n \choose k} \sim \sqrt{n\over 2\pi k (n-k)} \cdot {n^n \over k^k (n-k)^{n-k}}

이항 엔트로피 함수 H(p) = -p\log_2(p) -(1-p)\log_2(1-p)를 사용하여 다음 부등식을 얻을 수 있다. 이는 정보이론에서 유용하다.[15]

:\frac{1}{n+1} 2^{nH(k/n)} \leq {n \choose k} \leq 2^{nH(k/n)}

이는 다음과 같이 강화될 수 있다 (1 \le k \le n-1).[16]

:\sqrt{\frac{n}{8k(n-k)}} 2^{nH(k/n)} \leq {n \choose k} \leq \sqrt{\frac{n}{2\pi k(n-k)}} 2^{nH(k/n)}

n, k가 모두 1보다 충분히 클 때, 스털링 근사에 따른 로그 형태의 점근 근사식은 다음과 같다.

:\log_2 \binom{n}{k} \sim n H\left(\frac{k}{n}\right)

감마 함수 \Gamma(z)를 이용한 점근 공식도 존재한다. k \to \infty일 때,

:\binom{z}{k} \approx \frac{(-1)^k}{\Gamma(-z) k^{z+1}}

:\binom{z+k}{k} = \frac{k^z}{\Gamma(z+1)}\left( 1+\frac{z(z+1)}{2k}+\mathcal{O}\left(k^{-2}\right)\right)

조화수 H_k와 오일러-마스케로니 상수 \gamma를 이용한 근사식은 다음과 같다.

:\binom{z+k}{k}\approx \frac{e^{z(H_k-\gamma)}}{\Gamma(z+1)}

또한, k \to \infty이고 적절한 복소수 x에 대해 j/k \to x일 때, 다음 점근 공식이 성립한다.

:\frac{\binom{z+k}{j}}{\binom{k}{j}}\to \left(1-\frac{j}{k}\right)^{-z}

:\frac{\binom{j}{j-k}}{\binom{j-z}{j-k}}\to \left(\frac{j}{k}\right)^z

이항 계수의 합에 대한 상계는 이항 정리를 이용하여 간단히 구할 수 있다.

:\sum_{i=0}^k \binom{n}{i} \leq (1+n)^k

이항 엔트로피 함수를 이용한 더 정확한 평가는 다음과 같다 (\varepsilon \doteq k/n \leq 1/2인 모든 정수 n > k \geq 1).[19][30]

:\frac{1}{\sqrt{8n\varepsilon(1-\varepsilon)}} \cdot 2^{H(\varepsilon) \cdot n} \leq \sum_{i=0}^k \binom{n}{i} \leq 2^{H(\varepsilon) \cdot n}

4. 5. 수론적 성질

'''쿠머 정리(Kummer定理, Kummer’s theorem영어)'''는 음이 아닌 정수 n \ge k와 소수 p에 대해, 이항 계수 \binom nk를 나누는 p의 가장 큰 거듭제곱 지수 c (즉, p^c \mid \binom nk를 만족하는 최대 c)를 구하는 방법을 제시한다. 1852년 쿠머가 증명한 이 정리에 따르면, 지수 c는 k와 n-k를 p진법으로 더할 때 발생하는 받아올림의 횟수와 같다. 다르게 표현하면, c는 \lfloor k/p^j \rfloor > \lfloor n/p^j \rfloor - \lfloor (n-k)/p^j \rfloor 를 만족하는, 즉 k/p^j의 소수 부분이 n/p^j의 소수 부분보다 큰 음이 아닌 정수 j의 개수와 같다. 이 정리로부터 \binom nk가 n / \gcd(n, k)로 나누어떨어진다는 것을 알 수 있다. 따라서 특히, 임의의 양의 정수 r과 s < p^r인 양의 정수 s에 대해, p는 \binom{p^r}{s}를 나눈다. 그러나 p의 더 높은 거듭제곱에 대해서는 항상 성립하지는 않는다. 예를 들어, 9는 \binom 96을 나누지 않는다.

'''뤼카의 정리'''는 이항 계수 \binom nk를 소수 p로 나눈 나머지를 구하는 방법을 제공한다.

'''에르되시 추측'''(Erdős squarefree conjecture영어)은 중심 이항 계수 \binom{2n}n이 n>4일 때 항상 제곱 인수가 없는 정수라는 내용이다. 이는 에르되시 팔이 1980년에 추측했고,[32] 앤드루 그랜빌(Andrew Granville)과 올리비에 라마레(Olivier Ramaré프랑스어)가 1996년에 증명했다.[33]

데이비드 싱매스터(David Singmaster)는 1974년에 임의의 양의 정수 d가 거의 모든 이항 계수 \binom nk를 나눈다는 다소 놀라운 결과를 증명했다.[34] 더 정확히 말하면, N 미만의 n에 대한 이항 계수 \binom nk (0 \le k \le n < N) 중에서 d로 나누어떨어지는 것의 개수를 f(N)이라 할 때, 그 비율은 N이 무한대로 갈 때 1에 수렴한다. 즉,

:\lim_{N\to\infty}\frac{f(N)}{N(N+1)/2}=1

여기서 N(N+1)/2는 n < N일 때 가능한 이항 계수 \binom nk의 총 개수이다.

이항 계수는 다음과 같은 나누어짐 성질도 가진다:[14]

또한 다음과 같은 성질들이 알려져 있다.
:

\binom {n-1} k = \frac{(n-1)(n-2)\cdots(n-k)}{1\cdot 2\cdots k}

= \prod_{i=1}^{k}\frac{n-i}{i}\equiv \prod_{i=1}^{k}\frac{-i}{i} = (-1)^k \pmod n.


증명:만약 p가 소수이면, 0 < k < p인 모든 k에 대해 \binom pk = \frac{p \cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1}는 p로 나누어진다. 왜냐하면 분자는 소인수 p를 포함하지만, 분모는 0 < k < p이므로 p를 소인수로 가지지 않기 때문이다.

만약 n이 합성수이면, p를 n의 가장 작은 소인수라 하고 k = n/p라고 하자. 그러면 0 < p < n이고, \binom np = \frac{n(n-1)\cdots(n-p+1)}{p!} = \frac{k(n-1)\cdots(n-p+1)}{(p-1)!}이다. 만약 \binom np가 n으로 나누어진다고 가정하면, 분자 k(n-1)\cdots(n-p+1)는 n = kp로 나누어져야 한다. 이는 (n-1)\cdots(n-p+1)이 p로 나누어질 때만 가능하다. 그러나 n은 p로 나누어지므로, n-1, n-2, \ldots, n-p+1 중 어느 것도 p로 나누어지지 않는다. p는 소수이므로, 곱 (n-1)\cdots(n-p+1)도 p로 나누어지지 않는다. 따라서 분자는 n으로 나누어질 수 없으므로 모순이다. 즉, \binom np는 n으로 나누어지지 않는다.

4. 6. 다항식으로서의 성질

음이 아닌 정수 ''k''에 대해, 이항 계수 \binom{t}{k}는 변수 ''t''에 대한 다항식으로 생각할 수 있다. 이 다항식은 다음과 같이 정의된다.

\binom{t}{k} = \frac{t(t-1)(t-2)\cdots(t-k+1)}{k!} = \frac{t^{\underline{k}}}{k!}

여기서 t^{\underline{k}}는 하강 계승곱을 나타낸다. 이 식은 ''t''에 대한 ''k''차 다항식이며, 그 계수는 유리수이다. 이 정의를 사용하면 ''t''가 정수가 아닌 실수나 복소수일 때도 이항 계수를 계산할 수 있으며, 이는 뉴턴의 일반화된 이항 정리에서 사용된다.

각각의 음이 아닌 정수 ''k''에 대해, 다항식 \binom{t}{k}는 p(0) = p(1) = \cdots = p(k-1) = 0 이고 p(k) = 1을 만족하는 유일한 ''k''차 다항식 p(t)이다.

이항 계수 다항식의 계수는 제1종 스털링 수 s(k,i) 또는 \left[{k \atop i} \right]를 사용하여 다음과 같이 나타낼 수 있다.

\binom{t}{k} = \sum_{i=0}^k s(k,i)\frac{t^i}{k!} = \sum_{i=0}^k \left[{k \atop i} \right]\frac{t^i}{k!}

다항식 \binom{t}{k}의 도함수는 로그 미분을 이용하여 계산할 수 있다.

\frac{\mathrm{d}}{\mathrm{d}t} \binom{t}{k} = \binom{t}{k} \sum_{i=0}^{k-1} \frac{1}{t-i}

이 식은 t가 0, 1, \dots, k-1 중 하나일 때 문제가 될 수 있지만, 다음 항등식을 사용하여 도함수를 계산할 수도 있다.

\frac{\mathrm{d}}{\mathrm{d}t} \binom{t}{k} = \sum_{i=0}^{k-1} \frac{(-1)^{k-i-1}}{k-i} \binom{t}{i}

표수가 0인 임의의 체 (예: 유리수체 \mathbb{Q}) 위에서, 차수가 최대 ''d''인 임의의 다항식 p(t)는 이항 계수 다항식의 선형 결합으로 유일하게 표현될 수 있다.

p(t) = \sum_{k=0}^d a_k \binom{t}{k}

여기서 계수 a_k는 수열 p(0), p(1), \dots, p(k)의 ''k''차 차분이며, 다음과 같이 명시적으로 주어진다.[7][26]

a_k = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} p(i) (4)

=== 정수값 다항식 ===

정수값 다항식은 모든 정수 입력값 ''t''에 대해 정수값을 갖는 다항식을 말한다. 이항 계수 다항식 \binom{t}{k}는 모두 정수값 다항식이다. 이는 파스칼의 규칙을 이용하여 ''k''에 대한 수학적 귀납법으로 증명할 수 있다. 따라서 이항 계수 다항식들의 정수 계수 선형 결합 역시 정수값 다항식이 된다.

반대로, 식 (4)는 모든 정수값 다항식이 이항 계수 다항식들의 정수 계수 선형 결합으로 표현될 수 있음을 보여준다. 예를 들어, 정수값 다항식 3t(3t+1)/2는 다음과 같이 나타낼 수 있다.

9\binom{t}{2} + 6 \binom{t}{1} + 0\binom{t}{0}

더 일반적으로, 표수가 0인 체 ''K''의 임의의 부분환 ''R''에 대해, ''K''[''t'']에 속하는 다항식이 모든 정수 입력에 대해 ''R''의 값을 가질 필요충분조건은 그 다항식이 이항 계수 다항식들의 ''R''-선형 결합이라는 것이다.

=== 테일러 급수 ===

제1종 스털링 수를 이용하면, 이항 계수 다항식 \binom{z}{k}의 임의의 점 z_0 주위에서의 테일러 급수 전개는 다음과 같이 주어진다.

\begin{align} \binom{z}{k} = \frac{1}{k!}\sum_{i=0}^k z^i s_{k,i}&=\sum_{i=0}^k (z- z_0)^i \sum_{j=i}^k \binom{z_0}{j-i} \frac{s_{k+i-j,i}}{(k+i-j)!} \\ &=\sum_{i=0}^k (z-z_0)^i \sum_{j=i}^k z_0^{j-i} \binom{j}{i} \frac{s_{k,j}}{k!}\end{align}

5. 응용

조합론에서 이항 계수는 크기가 n인 유한 집합에서 크기가 k인 부분집합을 고르는 경우의 수, 즉 n개 원소에서 k개를 선택하는 조합의 수 \tbinom nk를 나타낸다. 이 외에도 다양한 조합론 문제에 활용된다.



대수학에서는 이항 정리에 따라 이항식을 거듭제곱할 때 각 항의 계수로 나타난다. 이항 계수라는 이름도 여기에서 유래했다.

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

통계학에서는 성공 확률이 p인 베르누이 시행을 n번 독립적으로 반복할 때 성공 횟수가 k번일 확률을 나타내는 이항 분포의 확률 질량 함수 P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}에 사용된다.

수론에서는 베르트랑의 공준 증명에 중심 이항 계수(\binom{2n}{n})의 성질이 활용된다. 또한, 아페리 상수 \zeta(3)가 무리수임을 증명하는 데 사용된 급수에도 중심 이항 계수가 등장한다.

:\zeta(3)=\frac52\sum_{n=1}^\infty \frac{(-1)^{n+1}}{n^3\binom{2n}n}

6. 일반화

음수, 실수, 복소수로의 확장이항 계수의 정의는 곱셈 공식을 이용하여 ''n'' 자리에 음수, 실수, 복소수 등 임의의 수 α 또는 모든 양의 정수가 가역적인 임의의 가환환의 원소를 넣어 확장할 수 있다.[4]

\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1} \quad(\text{단, } k\in\N \text{ 이고 } \alpha\text{는 임의의 수})

이 정의는 이항급수와 연결되며, |X| < 1인 모든 복소수 α와 ''X''에 대해 다음 이항 정리의 일반화가 성립한다.

(1+X)^\alpha = \sum_{k=0}^\infty {\alpha \choose k} X^k.

이 식은 ''X''에 대한 형식적 멱급수의 항등식으로도 볼 수 있다. 이 정의를 사용하면 지수 법칙과 유사한 항등식, 예를 들어 (1+X)^\alpha(1+X)^\beta=(1+X)^{\alpha+\beta} 와 ((1+X)^\alpha)^\beta=(1+X)^{\alpha\beta} 가 성립한다.

만약 α가 음이 아닌 정수 ''n''이면, k > n인 모든 항은 0이 되어[5] 무한급수는 유한 합이 되어 원래의 이항 정리와 같아진다. 그러나 α가 음의 정수나 유리수 등 다른 값이면 급수는 일반적으로 무한하다. 예를 들어, α가 음의 정수 -''n''일 경우 다음과 같이 표현된다.

\begin{align}\binom{-n}{k} &= \frac{-n\cdot-(n+1)\dots-(n+k-1)}{k!}\\

&=(-1)^k\;\frac{n\cdot(n+1)\cdots (n + k - 1)}{k!}\\

&=(-1)^k\binom{n + k - 1}{k}\end{align}

이는 아래에서 설명할 다중집합 계수와 관련이 있다.

또한, 감마 함수 Γ 또는 베타 함수 Β를 이용하여 이항 계수를 두 개의 실수 또는 복소수 인수로 일반화할 수도 있다.

{x \choose y}= \frac{\Gamma(x+1)}{\Gamma(y+1) \Gamma(x-y+1)}= \frac{1}{(x+1) \Beta(y+1, x-y+1)}.

이 정의는 감마 함수의 성질을 상속받아 다음과 같은 관계식을 만족한다.

{x \choose y}= \frac{\sin (y \pi)}{\sin(x \pi)} {-y-1 \choose -x-1}= \frac{\sin((x-y) \pi)}{\sin (x \pi)} {y-x-1 \choose y};

{x \choose y} \cdot {y \choose x}= \frac{\sin((x-y) \pi)}{(x-y) \pi}.

이 일반화된 함수의 그래프는 복잡하며, 특히 ''x''가 음수일 때 음의 정수 값에서 특이점을 가지고 양수와 음수 영역이 번갈아 나타나는 패턴을 보인다. 유한한 경우 성립했던 대칭성 \binom n m = \binom n {n-m} 등 많은 항등식이 이 일반화에서는 성립하지 않는다.
다항 계수이항 계수는 여러 항의 거듭제곱을 전개할 때 나타나는 '''다항 계수'''로 일반화될 수 있다. ''k''1 + ''k''2 + ... + ''k''''r'' = ''n'' 일 때, 다항 계수는 다음과 같이 정의된다.

{n\choose k_1,k_2,\ldots,k_r} =\frac{n!}{k_1!k_2!\cdots k_r!}

이항 계수가 (x + y)^n의 계수인 반면, 다항 계수는 (x_1 + x_2 + \cdots + x_r)^n의 전개식에서 각 항의 계수이다. ''r'' = 2인 경우, 다항 계수는 이항 계수와 같다.

{n\choose k_1,k_2}={n\choose k_1, n-k_1}={n\choose k_1}= {n\choose k_2}.

조합론적으로 다항 계수는 ''n''개의 구별 가능한 원소를 ''r''개의 구별 가능한 상자에 넣을 때, 각 상자 ''i''에 정확히 ''ki''개의 원소가 들어가도록 나누는 방법의 수를 센다.

다항 계수는 이항 계수와 유사한 성질을 가진다. 예를 들어, 다음과 같은 재귀 관계가 성립한다.

{n\choose k_1,k_2,\ldots,k_r} ={n-1\choose k_1-1,k_2,\ldots,k_r}+{n-1\choose k_1,k_2-1,\ldots,k_r}+\ldots+{n-1\choose k_1,k_2,\ldots,k_r-1}

또한, 인덱스의 순열 (\sigma_i)에 대해 대칭성을 가진다.

{n\choose k_1,k_2,\ldots,k_r} ={n\choose k_{\sigma_1},k_{\sigma_2},\ldots,k_{\sigma_r}}
다중집합 계수이항 계수가 집합에서 원소를 중복 없이 선택하는 경우의 수라면, '''다중집합 계수'''는 원소를 중복을 허용하여 선택하는 경우의 수를 센다. ''n''개의 원소를 가진 집합에서 ''k''개의 원소를 중복을 허용하여 선택하는 방법의 수는 \left(\!\!\binom n k\!\!\right)로 표기한다.[20][31]

다중집합 계수는 이항 계수를 이용하여 다음과 같이 표현할 수 있다.

\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.

이 관계는 하강 계승 멱(x^{\underline k} = x(x-1)\cdots(x-k+1))과 상승 계승 멱(x^{\overline k} = x(x+1)\cdots(x+k-1))을 사용하여 설명할 수도 있다. 이항 계수가 \binom{n}{k} = \frac{n^{\underline k}}{k!}로 표현되는 반면, 다중집합 계수는 \left(\!\!\binom{n}{k}\!\!\right)=\frac{n^{\overline k}}{k!}로 표현된다.

앞서 살펴본 음의 정수에 대한 이항 계수는 다중집합 계수와 다음과 같은 관계를 가진다.

\binom{-n}{k} = (-1)^k\binom{n+k-1}{k} = (-1)^k\left(\!\!\binom{n}{k}\!\!\right).

즉, 음의 정수 -''n''에 대한 이항 계수는 부호 (-1)^k를 가진 다중집합 계수와 같다. 특히 n=1일 경우 \binom{-1}{k} = (-1)^k이다.
q-아날로그이항 계수는 q-아날로그로 일반화될 수 있으며, 이를 '''가우스 이항 계수'''라고 부른다.
무한 기수로의 확장이항 계수의 정의는 기수가 무한한 경우로도 확장될 수 있다. 임의의 기수 \kappa, \lambda에 대하여, '''초한 이항 계수'''(transfinite binomial coefficient영어) \binom\kappa\lambda는 크기가 \kappa인 집합의, 크기가 \lambda인 부분 집합의 개수를 의미한다. 선택 공리를 가정하면 이 정의는 집합의 선택과 무관하게 잘 정의된다.

\kappa가 무한 기수이고 \lambda가 유한 또는 무한 기수일 때, 초한 이항 계수의 값은 다음과 같다.

\binom\kappa\lambda=\begin{cases}

\kappa^\lambda & \lambda\le\kappa \text{ 이고 } \kappa\ge\aleph_0 \\

0 & \lambda>\kappa \\

\binom nk & k=\lambda<\aleph_0,\;n=\kappa<\aleph_0 \text{ (유한 경우)}

\end{cases}

여기서 \aleph_0는 가장 작은 무한 기수이다. \lambda\le\kappa이고 \kappa가 무한 기수일 때 \binom\kappa\lambda=\kappa^\lambda가 되는 이유는 \kappa^\lambda\le\binom\kappa\lambda\le\kappa^\lambda 이기 때문이다.

특히, 무한 기수 \kappa에 대해 중심 이항 계수는 \binom{2\kappa}\kappa = 2^\kappa 이고, 또한 \binom{\kappa}\kappa = 2^\kappa 이다.

유한 이항 계수에서 성립하는 대칭성 \binom n k = \binom n {n-k}는 초한 이항 계수에서는 일반적으로 성립하지 않는다. 예를 들어,

\binom{\aleph_0+1}1 = \aleph_0

\binom{\aleph_0+1}{\aleph_0} = 2^{\aleph_0}

이므로 \binom{\aleph_0+1}1 \ne \binom{\aleph_0+1}{\aleph_0} 이다.

참조

[1] 저서
[2] 문서 Lilavati
[3] 저서
[4] 문서 Mathematical reflections: in a room with many mirrors
[5] 문서
[6] 저널 Note on Selected Combinations https://books.google[...]
[7] 문서
[8] 저널 Sets with a negative number of elements
[9] 저서
[10] 저널 The Egg-Drop Numbers
[11] 저널 Nearly homogeneous multi-partitioning with a deterministic generator
[12] 저널 An Algebraic Identity Leading to Wilson's Theorem
[13] 저서
[14] 저널 Nontrivial lower bounds for the least common multiple of some finite sequence of integers
[15] 서적 Elements of Information Theory Wiley 2006-07-18
[16] 서적 The Theory of Error-Correcting Codes North-Holland
[17] 서적 Asymptopia American Mathematical Society 2014
[18] 서적 Asymptopia American Mathematical Society 2014
[19] 저서
[20] 저널 Riordan matrices and sums of harmonic numbers http://www.doiserbia[...]
[21] 문서 Lilavati
[22] 저서
[23] 저서
[24] 서적 Mathematical Reflections: In a Room With Many Mirrors Springer
[25] 저널 Note on selected combinations https://books.google[...]
[26] 문서
[27] 저널 The Egg-drop numbers
[28] 저널 Nearly homogeneous multi-partitioning with a deterministic generator
[29] 저널 An algebraic identity leading to Wilson's theorem http://www.jstor.org[...]
[30] 저서
[31] 저널 Riordan matrices and sums of harmonic numbers
[32] 서적 Old and new problems and results in combinatorial number theory Université de Genève 1980
[33] 저널 Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients http://www.dms.umont[...] 1996-06
[34] 저널 Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients 1974


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

문의하기 : help@durumis.com