Binomial coefficient

수학(mathematics)에서, 이항 계수(binomial coefficient)는 이항 정리(binomial theorem)에서 계수(coefficient)로 발생하는 양의 정수(integer)입니다. 공통적으로, 이항 계수는 정수 $n \geq k \geq 0$ 의 쌍에 의해 인덱스되고 ${\tbinom {n}{k}}$ 으로 쓰입니다. 그것은 이항(binomial) 거듭제곱(power) $(1 + x) n$ 의 다항 전개(polynomial expansion)에서 $x k$ 항의 계수(coefficient)이고, 다음 공식에 의해 주어집니다:

{\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.

예를 들어, $1 + x$ 의 네 번째 거듭제곱은 다음입니다:

{\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}

그리고 이항 계수 ${\tbinom {4}{2}}={\tfrac {4!}{2!2!}}=6$ 는 $x 2$ 항의 계수입니다.

$n=0,1,2,\ldots$ 에 대한 연속적인 행에서 숫자 ${\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}$ 를 정렬하면, 파스칼의 삼각형(Pascal's triangle)으로 불리는 삼각형 배열을 제공하며, 다음 재귀 관계(recurrence relation)를 만족시킵니다:

{\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.

이항 계수는 수학의 많은 분야, 특히 조합론(combinatorics)에서 발생합니다. 기호 ${\tbinom {n}{k}}$ 는 " $n$ 선택 $k$ "로 보통 읽혀지는데, 왜냐하면 $n$ 원소의 고정된 집합으로부터 $k$ 원소의 (비-순서화) 부분-집합을 선택하기 위한 ${\tbinom {n}{k}}$ 방법이 있기 때문입니다. 예를 들어, $\{1,2,3,4\}$ 로부터 2 원소를 선택하기 위한 ${\tbinom {4}{2}}=6$ 방법이 있습니다; 즉 $\{1,2\}{\text{, }}\{1,3\}{\text{, }}\{1,4\}{\text{, }}\{2,3\}{\text{, }}\{2,4\}{\text{,}}$ 및 $\{3,4\}$ 입니다.

이항 계수는 임의의 복소수 $z$ 와 정수 $k \geq 0$ 에 대해 ${\tbinom {z}{k}}$ 로 일반화될 수 있고, 많은 그들의 속성들이 이 보다 일반적인 형식에서 계속 유지됩니다.

History and notation

안드레아스 폰 에팅스하우젠(Andreas von Ettingshausen)은, 비록 숫자가 수세기 전에 알려져 있었을지라도, 1826년에 표기법 ${\tbinom {n}{k}}$ 을 도입했습니다^[1] (파스칼의 삼각형(Pascal's triangle)을 참조하십시오). 이항 계수의 가장-오래된 알려진 자세한 논의는, 할라유터(Halayudha)에 의한, 고대 산스크리트(Sanskrit) 문헌, 핀갈라(Pingala)의 찬다예살라(Chandaḥśāstra)에 대한 10세기 주석에 있습니다. 약 1150년에서, 인도의 수학자 바스카라 II(Bhaskaracharya)는 그의 저서 릴라바티(Līlāvatī)에서 이항 계수에 대한 설명을 제공했습니다.^[2]

대안적인 표기법은 $C (n, k)$ , $n C k$ , $n C k$ , $C k n$ , $C n k$ , 및 $C n, k$ 를 포함하며, 이것 모두에서 $C$ 는 조합(combination) 또는 선택(choices)을 의미합니다. 많은 계산기는 $C$ 표기법의 변형을 사용하는데, 왜냐하면 그들은 단일-행 디스플레이에서 그것을 표현할 수 있기 때문입니다. 이 형식에서, 이항 계수는 $P (n, k)$ , 등으로 쓰인, $n$ 의 $k$ -순열과 쉽게 비교됩니다.

Definition and interpretations

(0을 포함하도록 취해진) 자연수(natural number) n 및 k에 대해, 이항 계수 ${\tbinom {n}{k}}$ 는 (1 + X)ⁿ의 전개에서 단항(monomial) X^k의 계수(coefficient)로 정의될 수 있습니다. 같은 계수는 (만약 k ≤ n이면) 이항 공식(binomial formula)에서 역시 발생합니다:

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

(∗)

(교환 링(commutative ring)의 임의의 원소 x,y에 대해 유효합니다), 이것은 이름 "이항 계수"를 설명합니다.

이 숫자의 또 다른 발생은 조합론에서 있으며, 여기서 그것은, 순서를 무시하고, k 대상이 n 대상 중에서 선택될 수 있는 방법의 숫자를 제공합니다; 보다 공식적으로, n-원소 집합의 k-원소 부분-집합 (또는 k-조합(combination))의 숫자입니다. 이 숫자는 그것을 계산하기 위한 아래의 공식의 임의의 것과 독립적으로, 첫 번째 정의의 하나와 같은 것으로 보일 수 있습니다: 만약 거듭제곱 (1 + X)ⁿ의 n 인수의 각각에서 우리가 임시로 (1에서 n까지 실행하는) 인덱스 i를 갖는 항 X에 라벨을 붙이면, k 인덱스의 각 부분-집합은 전개 후에 기여 X^k를 제공하고, 결과에서 해당 단항의 계수는 그러한 부분-집합의 개수일 것입니다. 이것은 특히 ${\tbinom {n}{k}}$ 가 임의의 자연수 n과 k에 대해 자연수임을 보여줍니다. 이항 계수의 많은 다른 조합 해석이 있으며 (답이 이항 계수 표현에 의해 제공되는 것에 대해 세는 문제), 예를 들어 그의 합이 k인 n 비트(bit) (자릿수 0 또는 1)로 형성된 단어의 숫자는 ${\tbinom {n}{k}}$ 에 의해 제공되지만, 모든 각 a_i는 비-음의 정수인 $k=a_{1}+a_{2}+\cdots +a_{n}$ 를 쓰기 위한 방법의 숫자는 ${\tbinom {n+k-1}{n-1}}$ 에 의해 제공됩니다. 이들 해석의 대부분은 k-조합을 세는 것과 동등한 것임을 쉽게 알 수 있습니다.

Computing the value of binomial coefficients

여러가지 방법이 실제로 이항 거듭제곱을 전개하는 것 또는 k-조합을 세는 것없이 ${\tbinom {n}{k}}$ 의 값을 계산하는 것이 존재합니다.

Recursive formula

하나의 방법은, 다음 초기/경계 값

{\binom {n}{0}}={\binom {n}{n}}=1\quad {\text{for all integers }}n\geq 0,

을 갖는, 다음 재귀(recursion), 순순하게 더하는, 공식을 사용합니다:

{\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}\quad {\text{for all integers }}n,k:1\leq k\leq n-1

.

공식은 집합 {1,2,3,…,n}을 고려하고 (a) 모든 각 그룹에서, 특정 집합 원소, 말하자면 "i"를 포함하는 k-원소 그룹화 (왜냐하면 "i"는 이미 모든 각 그룹에서 하나의 자리를 채우기 위해 선택되었기 때문에, 우리는 남아있는 n − 1으로부터 k − 1을 오직 선택하는 것이 필요합니다) 및 (b) "i"를 포함하지 않는 모든 k-그룹화를 분리해서 세는 것으로부터 따릅니다; 이것은 n 원소의 모든 가능한 k-조합을 열거합니다. 그것은 역시 (1 + X)ⁿ⁻¹(1 + X) 안의 X^k에 대한 기여를 추적하는 것으로부터 따릅니다. (1 + X)ⁿ 안의 영 Xⁿ⁺¹ 또는 X⁻¹이 있으므로, 우리는 k > n 또는 k < 0일 때 ${\tbinom {n}{k}}$ = 0을 포함하기 위해 위쪽 경계를 넘어 정의를 확장할 수 있습니다. 이 재귀 공식은, 그런-다음, 영, 또는 자명한 계수가 될 수 있는 공백으로 둘러쌓인, 파스칼의 삼각형(Pascal's triangle)의 구성을 허용합니다.

Multiplicative formula

개별적인 이항 계수를 계산하기 위한 보다 효율적인 방법은 다음 공식에 의해 제공됩니다:

{\binom {n}{k}}={\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^{\underline {k}}$ 의 분자는 떨어지는 팩토리얼 거듭제곱(falling factorial power)으로 표현됩니다. 이 공식은 이항 계수의 조합론적 해석에 대해 이해하는 것이 가장 쉽습니다. 분자는 n 대상의 집합으로부터 선택의 순서를 유지하면서 k 구별되는 대상의 수열을 선택하는 방법의 숫자를 제공합니다. 분모는 순서가 무시될 때 같은 k-조합을 정의하는 구별되는 수열의 숫자를 셉니다.

k와 n–k에 관한 이항 계수의 대칭성으로 기인하여, 계산은 위의 곱의 위쪽 상한을 k와 n−k의 더 작은 값으로 설정함으로써 최적화될 수 있습니다.

Factorial formula

마지막으로, 비록 계산적으로 부적합할지라도, 증명과 유도에서 종종 사용되는 간결한 형식이 있으며, 이것은 익숙한 팩토리얼(factorial) 함수를 반복적인 사용을 만듭니다:

{\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,

여기서 n!은 n의 팩토리얼을 나타냅니다. 이 수식은 (n − k)!에 의한 분자와 분모를 곱함으로써 위의 곱셈적 공식으로부터 따릅니다; 결과적으로 그것은 분자와 분모에 공통적인 많은 인수를 포함합니다. 그것은 만약 (특히 팩토리얼 값이 매우 빠르게 증가하기 때문에) 공통 인수가 먼저 취소되지 않으면 (k가 작고 n이 큰 경우에서) 명시적 계산에 대해 덜 실용적입니다. 공식은 다음 곱셈적 공식으로부터 덜 명확한 대칭을 나타냅니다 (비록 그것이 정의에서 온 것일지라도)

{\binom {n}{k}}={\binom {n}{n-k}}\quad {\text{for }}\ 0\leq k\leq n,

(1)

이것은 보다 효과적인 곱셈적 연산의 루틴으로 이어집니다. 떨어지는 팩토리얼 표기법(falling factorial notation)을 사용하여,

{\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!&{\text{if }}\ k\leq {\frac {n}{2}}\\n^{\underline {n-k}}/(n-k)!&{\text{if }}\ k>{\frac {n}{2}}\end{cases}}.

Generalization and connection to the binomial series

곱셈적 공식은 임의의 숫자 α (음수, 실수, 복소수) 또는 심지어 모든 양의 정수가 역-가능한 임의의 교환 링(commutative ring)의 원소에 의한 n을 대체함으로써 확장되어지는 이항 계수의 정의를 허용합니다.^[3]

{\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{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .

이 정의와 함께 우리는 (1로 변수 집합의 하나를 설정함으로써) 이항 공식의 일반화를 가지며, 이것은 여전히 ${\tbinom {\alpha }{k}}$ 이항 계수를 호출함을 정당화합니다:

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

(2)

이 공식은 모든 복수수 α와 |X| < 1을 갖는 X에 대해 유효합니다. 그것은 X 안의 형식적 거듭제곱 급수(formal power series)의 항등식으로 역시 해석될 수 있으며, 여기서 그것은 1과 같은 상수 계수를 갖는 거듭제곱 급수의 임의의 거듭제곱의 정의로 실제로 쓸 수 있습니다; 요점은 이 정의와 함께 모든 항등식은 우리가 지수화(exponentiation)에 대해 기대하는 것을 유지한다는 것이며, 특히

(1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta }\quad {\text{and}}\quad ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }.

만약 α가 비-음의 정수 n이면, k > n을 갖는 모든 항은 영이고, 무한 급수는 유한 합이 되며, 그것으로 인해서 이항 공식을 다시-덮습니다. 어쨌든, 음의 정수와 유리수를 포함하는, α의 다른 값에 대해, 급수는 실제로 무한입니다.

Pascal's triangle

파스칼의 규칙(Pascal's rule)은 다음의 중요한 재귀 관계(recurrence relation)입니다:

{n \choose k}+{n \choose k+1}={n+1 \choose k+1},

(3)

이것은 ${\tbinom {n}{k}}$ 이 모든 n 및 k에 대해 자연수임을 수학적 귀납법(mathematical induction)에 의해 증명하기 위해 사용될 수 있으며, 사실 공식 (1)으로부터 즉시 명백한 것은 아닙니다.

파스칼의 규칙은 파스칼의 삼각형(Pascal's triangle)을 역시 야기합니다:

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

행 숫자 $n$ 은 $k = 0, ..., n$ 에 대해 숫자 ${\tbinom {n}{k}}$ 를 포함합니다. 그것은 가장 바깥쪽에서 1들을 위치시키고, 그런-다음 바로 위의 두 숫자의 합으로 각 내부 위치를 채움으로써 구성됩니다. 이 방법은 분수 또는 곱셈에 대한 필요없이 이항 계수의 빠른 계산을 허용합니다. 예를 들어, 삼각형의 행 숫자 5를 보면, 우리는 다음임을 빠르게 읽을 수 있습니다:

(x+y)^{5}={\underline {1}}x^{5}+{\underline {5}}x^{4}y+{\underline {10}}x^{3}y^{2}+{\underline {10}}x^{2}y^{3}+{\underline {5}}xy^{4}+{\underline {1}}y^{5}.

Combinatorics and statistics

이항 계수는 조합론(combinatorics)에서 중요한데, 왜냐하면 그들은 특정 빈번한 세는 문제에 대해 준비된 공식을 제공하기 때문입니다:

n 원소의 집합으로부터 k 원소를 선택하는 ${\tbinom {n}{k}}$ 방법이 있습니다. 조합(Combination)을 참조하십시오.
만약 반복이 허용된다면 n 원소의 집합으로부터 k 원소를 선택하는 ${\tbinom {n+k-1}{k}}$ 방법이 있습니다. 중복집합(Multiset)을 참조하십시오.
k 문자열과 n 영을 포함하는 ${\tbinom {n+k}{k}}$ 문자열(strings)이 있습니다.
두 문자열이 인접하지 않는 것을 만족하는 k 문자열과 n 영으로 구성되는 ${\tbinom {n+1}{k}}$ 문자열이 있습니다.^[4]
카탈랑 숫자(Catalan number)는 ${\tfrac {1}{n+1}}{\tbinom {2n}{n}}$ 입니다.
통계학(statistics)에서 이항 분포(binomial distribution)는 ${\tbinom {n}{k}}p^{k}(1-p)^{n-k}$ 입니다.

Binomial coefficients as polynomials

임의의 비-음의 정수 k에 대해, 표현 $\scriptstyle {\binom {t}{k}}$ 은 k!로 나눈 다항식으로 단순화되고 정의될 수 있습니다:

{\binom {t}{k}}={\frac {(t)_{k}}{k!}}={\frac {(t)_{k}}{(k)_{k}}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};

이것은 유리수(rational) 계수를 갖는 t에서 다항식(polynomial)을 나타냅니다.

이와 같이, 그것은 그러한 첫 번째 인수를 갖는 이항 계수를 정의하기 위해 임의의 실수 또는 복소수 t에서 평가될 수 있습니다. 이들 "일반화된 이항 계수"는 뉴턴의 일반화된 이항 정리(Newton's generalized binomial theorem)에 나타납니다.

각 k에 대해, 다항식 ${\tbinom {t}{k}}$ 는 p(0) = p(1) = ... = p(k − 1) = 0 및 p(k) = 1를 만족시키는 유일한 차수 k 다항식 p(t)로 특성화될 수 있습니다.

그의 계수는 첫 번째 종류의 스털링 숫자(Stirling numbers of the first kind)의 관점에서 표현할 수 있습니다:

{\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.

${\tbinom {t}{k}}$ 의 도함수(derivative)는 로그 미분화(logarithmic differentiation)에 의해 계산될 수 있습니다:

{\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}\,.

Binomial coefficients as a basis for the space of polynomials

특성 0(characteristic 0)의 임의의 필드(field) (즉, 유리수(rational number)를 포함하는 임의의 필드)에 걸쳐, 최대 d 차수의 각 다항식 p(t)는 이항 계수의 선형 조합 $\sum _{k=0}^{d}a_{k}{\binom {t}{k}}$ 으로 고유하게 표현될 수 있습니다. 계수 a_k는 수열 p(0), p(1), …, p(k)의 k번째 차이(kth difference)입니다. 명시적으로,^[5]

a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).

(4)

Integer-valued polynomials

각 다항식 ${\tbinom {t}{k}}$ 는 정수-값(integer-valued)입니다: 그것은 모든 정수 입력 $t$ 에서 정수 값을 가집니다. (이것을 입증하기 위한 한 방법은, 파스칼의 항등식(Pascal's identity)을 사용하여, k에 대한 귀납법에 의한 것입니다.) 그러므로, 이항 계수 다항식의 임의의 정수 선형 조합은 역시 정수-값입니다. 반대로, (4)는 임의의 정수-값 다항식은 이들 이항 계수 다항식의 정수 선형 조합임을 보입니다. 보다 일반적으로, 특성 0 필드 K의 임의의 부분-링 R에 대해, K[t]에서 다항식은 모든 정수에서 R에서 값을 취하는 것과 그것이 이항 계수 다항식의 R-선형 조합인 것은 필요충분 조건입니다.

Example

정수-값 다항식 3t(3t + 1)/2은 다음으로 쓸 수 있습니다:

9{\tbinom {t}{2}}+6{\tbinom {t}{1}}+0{\tbinom {t}{0}}.

Identities involving binomial coefficients

팩토리얼 공식은 근처의 이항 계수를 관련시키기에 용이합니다. 예를 들어, 만약 k가 양의 정수이고 n이 임의의 것이면, 다음입니다:

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

(5)

및, 조금 더 작업하면,

{\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.

게다가, 다음이 유용할 것입니다:

{\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}.

상수 n에 대해, 우리는 다음 재귀를 가집니다:

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

Sums of the binomial coefficients

공식

\sum _{k=0}^{n}{\binom {n}{k}}=2^{n}

(∗∗)

은 파스칼의 삼각형의 n^번째 행에서 원소들은 합해져서 n^번째 거듭제곱이 올려진 2와 항상 같음을 말합니다. 이것은 x = 1 및 y = 1로 설정함으로써 이항 정리 (∗)로부터 얻습니다. 공식은 자연적인 조합 해석을 역시 가집니다: 왼쪽 변은 크기 k = 0,1,...,n의 {1,...,n}의 부분-집합의 숫자를 합하며, 부분-집합의 전체 숫자를 제공합니다. (즉, 왼쪽 변은 {1,...,n}의 거듭제곱 집합(power set)을 셉니다.) 어쨌든, 이들 부분-집합은 각 원소 1,...,n을 연속적으로 선택함 또는 제외함으로써 역시 생성될 수 있습니다; n 개의 독립적인 이진 선택 (비트-문자열)은 전체 $2^{n}$ 선택을 허용합니다. 왼쪽과 오른쪽 변은 부분집합의 같은 모음을 세기 위한 두 방법이므로, 그들은 같습니다.

공식

\sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}

(6)

및 $\sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}$ 은 x에 관한 미분화(differentiating) (후자에서 두 번)하고 그런-다음 x = 1을 대체한 후에 (2)로부터 따릅니다.

임의의 복소수-값 m과 n 및 임의의 비-음의 정수 k에 대해 유지되는 추시–방데르몽드 항등식(Chu–Vandermonde identity)은 다음입니다:

\sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}

(7)

및 방정식 (2)를 사용하여 $(1 + x) m (1 + x) n - m = (1 + x) n$ 의 전개에서 $x^{k}$ 의 계수의 검사에 의해 구할 수 있습니다. $m = 1$ 일 때, 방정식 (7)은 방정식 (3)으로 줄어둡니다. 특별한 경우 $n = 2 m, k = m$ 에서, (1)을 사용하여, 전개 (7)는 (오른쪽에서 파스칼의 삼각형 안에 보이는 것처럼) 다음이 됩니다:

{\begin{array}{c}1\\1\qquad 1\\1\qquad 2\qquad 1\\{\color {blue}1\qquad 3\qquad 3\qquad 1}\\1\qquad 4\qquad 6\qquad 4\qquad 1\\1\qquad 5\qquad 10\qquad 10\qquad 5\qquad 1\\1\qquad 6\qquad 15\qquad {\color {red}20}\qquad 15\qquad 6\qquad 1\\1\qquad 7\qquad 21\qquad 35\qquad 35\qquad 21\qquad 7\qquad 1\end{array}}

Pascal's triangle, rows 0 through 7. Equation 8 for m = 3 is illustrated in rows 3 and 6 as

1^{2}+3^{2}+3^{2}+1^{2}=20.

\sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},

(8)

여기서 오른쪽 변에 대한 항은 중앙 이항 계수(central binomial coefficient)입니다.

$0 \leq j \leq k \leq n$ 을 만족시키는 임의의 정수 j, k, 및 n에 대해 적용하는 추시–방데르몽드 항등식의 또 다른 형식은 다음입니다:

\sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}.

(9)

증명은 비슷하지만, 음의 정수 지수를 갖는 이항 급수 전개 (2)를 사용합니다. $j = k$ 일 때, 방정식 (9)은 하키-스틱 항등식(hockey-stick identity)을 제공합니다:

\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-번째 피보나치 숫자(Fibonacci number)를 표시하는 것으로 놓습니다. 그런-다음,

\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1).

이것은 (3)을 사용하여 귀납법(induction)에 의해 또는 제켄도프의 표시(Zeckendorf's representation)에 의해 입증될 수 있습니다. 조합론적 증명은 아래에 주어집니다.

Multisections of sums

$0\leq t<s$ 를 만족하는 정수 s와 t에 대해, 급수 중복절개(series multisection)는 이항 계수의 합에 대해 다음 항등식을 제공합니다:

{\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에 대해, 이들 급수는 특히 좋은 형식을 가집니다; 예를 들어,^[6]

{\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)

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

{\binom {n}{1}}+{\binom {n}{5}}+{\binom {n}{9}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)

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

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

Partial sums

비록 이항 계수의 부분 합

\sum _{j=0}^{k}{\binom {n}{j}}

에 대해 닫힌 공식이 없을지라도,^[7] 우리는 k = 0, ..., n − 1에 대해, 다음임을 보이기 위해 (3) 및 귀납법을 다시 사용할 수 있습니다:

\sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}}

위와 함께 n > 0에 대해, 다음 특별한 경우를 가집니다:^[8]

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0

.

이 후자의 결과는, n보다 작은 차수의 임의의 다항식 P(x)에 대해 다음인, 유한 차이의 이론으로부터 결과의 역시 특수한 경우입니다:^[9]

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(j)=0.

(2)를 k번 미분하고 x = −1을 설정하면, 0 ≤ k < n일 때, $P(x)=x(x-1)\cdots (x-k+1)$ 에 대해 이것을 산출하고, 일반적인 경우는 이들의 선형 조합을 취하는 것에 의해 따릅니다.

P(x)가 n보다 작거나 같은 차수일 때,

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(n-j)=n!a_{n}

(10)

여기서 $a_{n}$ 은 P(x)에서 차수 n의 계수입니다.

보다 일반적으로, (10)에 대해,

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(m+(n-j)d)=d^{n}n!a_{n}

여기서 m과 d는 복소수입니다. 이것은 즉시 $P(x)$ 대신에 다항식 $Q(x):=P(m+dx)$ 에 (10)을 적용하고, $Q(x)$ 가 여전히 n보다 작거나 같은 차수를 가짐고, 차수 n의 그의 계수가 dⁿa_n임을 관찰함을 따릅니다.

급수(series) ${\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}$ 는 k ≥ 2에 대해 수렴입니다. 이 공식은 독일 탱크 문제(German tank problem)의 해석에서 사용됩니다. 그것은 ${\frac {k-1}{k}}\sum _{j=0}^{M}{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}-{\frac {1}{\binom {M+x}{k-1}}}$ 로부터 따르고 M에 대한 귀납법(induction)에 의해 입증됩니다.

Identities with combinatorial proofs

이항 계수를 포함하는 많은 항등식은 조합론적 수단(combinatorial means)에 의해 입증될 수 있습니다. 예를 들어, 비-음의 정수 ${n}\geq {q}$ 에 대해, 항등식

\sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}

은 (이것은, q = 1일 때, (6)으로 줄어듭니다), 다음 처럼, 이중 셈 증명(double counting proof)으로 제공될 수 있습니다. 왼쪽 변은 [n] = {1, 2, …, n}에서 적어도 q 원소를 갖는 [n] = {1, 2, …, n}의 부분집합을 선택하고, 선택된 그들 중에서 q 원소를 표시하는 방법의 숫자를 셉니다. 오른쪽 변은 같은 것을 세는데, 왜냐하면 표시할 q 원소의 집합을 선택하는 것의 ${\tbinom {n}{q}}$ 방법이 있고, [n]의 남아있는 원소 중의 어떤 것이 역시 부분집합에 속할지를 선택하기 위한 $2^{n-q}$ 방법이 있기 때문입니다.

다음 파스칼의 항등식에서

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k},

양쪽 변은 [n]의 k-원소 부분집합의 숫자를 셉니다: 오른쪽 변에 대한 두 항은 원소 n을 포함하는 원소와 그렇지 않은 원소로 그룹을 만듭니다.

항등식 (8)은 역시 조합론적 증명을 가집니다. 항등식은 다음을 읽습니다:

\sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.

여러분이 한 행에서 정렬된 $2n$ 빈 사각형을 가지고 여러분은 그들의 n 개를 표시 (선택)하기을 원한다고 가정합니다. 이것을 하기 위해 ${\tbinom {2n}{n}}$ 방법이 있습니다. 다른 한편으로, 여러분은 처음 n 개 중에서 k 개를 선택하고 남아있는 n 개의 사각형으로부터 n – k 개의 사각형을 선택함으로써 n 개의 사각형을 선택할 수 있을 것입니다; 0에서 n까지의 임의의 k가 작동할 것입니다. 이것은 다음을 제공합니다:

\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.

이제 결과를 얻기 위해 (5)를 적용하십시오.

만약 우리가 피보나치 숫자(Fibonacci number)의 수열을 $F (i)$ 로 나타내고, $F (0) = F (1) = 1$ 되도록 인덱스화하면, 항등식 $\sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\tbinom {n-k}{k}}=F(n)$ 은 다음 조합론적 증명을 가집니다.^[10] 우리는 $F (n)$ 은 사각형의 $n \times 1$ 조각이 $2 \times 1$ 및 $1 \times 1$ 의 타일로 덮어질 수 있는 방법의 숫자를 세는 것을 귀납법(induction)에 의해 보일 수 있습니다. 다른 한편으로, 만약 그러한 타일링이 $2 \times 1$ 타일의 정확히 $k$ 개를 사용하면, 그것은 $1 \times 1$ 타일의 $n - 2 k$ 를 사용하고, 그래서 전체 $n - k$ 타일을 사용합니다. 이들 타일을 순서화하기 위한 ${\tbinom {n-k}{k}}$ 방법이 있고, 그래서 $k$ 의 모든 가능한 값에 걸쳐 이 계수를 합하는 것은 항등식을 제공합니다.

Sum of coefficients row

모든 k에 대해 k-조합(combinations)의 숫자, $\sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}$ 는 이항 계수의 (0으로부터 세는) n번째 행의 합입니다. 이들 조합은 0에서 $2^{n}-1$ 까지 세는 밑수 2(base 2) 숫자의 집합의 1 자릿수에 의해 열거되며, 여기서 각 자릿수 위치는 n의 집합으로부터 항목입니다.

Dixon's identity

딕슨의 항등식(Dixon's identity)은 다음입니다:

\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는 비-음의 정수입니다.

Continuous identities

특정 삼각 적분은 이항 계수의 관점에서 표현-가능한 값을 가집니다: 임의의 $\textstyle m,n\in \mathbb {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{ odd}}\\0,&{\text{otherwise}}\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{ even}}\\0,&{\text{otherwise}}\end{cases}}

이들은 오일러의 공식(Euler's formula)을 사용하여 삼각 함수(trigonometric functions)를 복소 지수로 변환하고, 이항 정리를 사용하여 전개하고, 항별로 적분함으로써 입증될 수 있습니다.

Generating functions

Ordinary generating functions

고정된 $n$ 에 대해, 수열 ${\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots$ 의 보통의 생성 함수(ordinary generating function)는 다음입니다:

\sum _{k=0}^{\infty }{n \choose k}x^{k}=(1+x)^{n}.

고정된 $k$ 에 대해, 수열 ${\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},\ldots$ 의 보통의 생성 함수는 다음입니다:

\sum _{n=k}^{\infty }{n \choose k}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}.

이항 계수의 이변수 생성 함수(bivariate generating function)는 다음입니다:

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

Exponential generating function

이항 계수의 대칭 지수 이변수 생성 함수(exponential bivariate generating function)는 다음입니다.

\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.

Divisibility properties

1852년에서, 쿠머(Kummer)는 만약 m과 n이 비-음의 정수이고 p가 소수이면, ${\tbinom {m+n}{m}}$ 을 나누는 p의 가장 큰 거듭제곱은 p^c와 같음을 입증했으며, 여기서 c는 m과 n이 밑수 p에서 더해질 때 캐리의 숫자입니다. 동등하게, ${\tbinom {n}{k}}$ 에서 소수 p의 지수는 ${\tbinom {n}{k}}$ 의 분수 부분(fractional part)이 n/p^j의 분수 부분보다 더 큰 것을 만족하는 비-음의 정수 j의 숫자와 같습니다. 그것은 ${\tbinom {n}{k}}$ 은 n/gcd(n,k)에 의해 나누어질 수 있음을 이것으로부터 추론될 수 있습니다. 특히 그러므로 그것은 s < p^r를 만족하는 모든 양의 정수에 대해 p가 ${\tbinom {p^{r}}{s}}$ 을 나누는 것을 따릅니다. 어쨌든 이것은 p의 더 높은 거듭제곱에 대해서 참이 아닙니다: 예를 들어 9는 ${\tbinom {9}{6}}$ 를 나누지 않습니다.

데이비드 싱매스트(David Singmaster) (1974)에 의한 다소 놀라운 결과는 임의의 정수가 거의 모든(almost all) 이항 계수를 나눈다는 것입니다. 보다 정확하게, 정수 d를 고정하고 f(N)를 d가 ${\tbinom {n}{k}}$ 을 나누는 것을 만족하는 n < N을 갖는 이항 계수 ${\tbinom {n}{k}}$ 의 숫자를 나타내는 것으로 놓습니다. 그런-다음 다음입니다:

\lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.

왜냐하면 n < N을 갖는 이항 계수 ${\tbinom {n}{k}}$ 의 숫자는 N(N + 1) / 2이기 때문이며, 이것은 d에 의해 나누어질 수 있는 이항 계수의 밀도는 1로 감을 의미합니다.

이항 계수는 연속 정수의 최소 공통 배수와 관련된 나눗-가능성 속성을 가집니다. 예를 들어:^[11]

${\binom {n+k}{k}}$ divides ${\frac {{\text{lcm}}(n,n+1,\ldots ,n+k)}{n}}$ .

${\binom {n+k}{k}}$ is a multiple of ${\frac {{\text{lcm}}(n,n+1,\ldots ,n+k)}{n\cdot {\text{lcm}}({\binom {k}{0}},{\binom {k}{1}},\ldots ,{\binom {k}{k}})}}$ .

또 다른 사실: 정수 $n \geq 2$ 이 소수인 것과 모든 중간의 이항 계수

{\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}

가 n에 의해 나누어질 수 있는 것은 필요충분 조건입니다.

증명: p가 소수일 때, p는 다음을 나눕니다:

{\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}

for all

0 < k < p

왜냐하면 ${\tbinom {p}{k}}$ 는 자연수이고 p는 분자를 나누지만 분모는 나누지 않기 때문입니다. n이 합성수일 때, p를 n의 가장-작은 소수 인수로 놓고 $k = n/p$ 로 놓습니다. 그런-다음 $0 < p < n$ 이고 다음입니다:

{\binom {n}{p}}={\frac {n(n-1)(n-2)\cdots (n-p+1)}{p!}}={\frac {k(n-1)(n-2)\cdots (n-p+1)}{(p-1)!}}\not \equiv 0{\pmod {n}}

그렇지 않으면 분자 $k (n - 1)(n - 2)\times...\times(n - p + 1)$ 는 $n = k \times p$ 에 의해 나누어져야 하며, 이것은 오직 $(n - 1)(n - 2)\times...\times(n - p + 1)$ 가 p에 의해 나누어지는 경우일 것입니다. 그러나 n이 p에 의해 나누어질 수 있으므로, p는 $n - 1, n - 2, ..., n - p + 1$ 를 나눌 수 없고 p는 소수이기 때문에, 우리는 p가 $(n - 1)(n - 2)\times...\times(n - p + 1)$ 를 나눌 수 없고 그래서 분자는 n에 의해 절대 나눌 수 없음을 압니다.

Bounds and asymptotic formulas

${\tbinom {n}{k}}$ 에 대해 다음 경계는 1 ≤ k ≤ n을 만족하는 n과 k의 모든 값에 대해 유지됩니다:

{\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}

.

첫 번째 부등식은 다음

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

이고, 이 곱에서 이들 $k$ 항의 각각은 $\geq {\frac {n}{k}}$ 인 사실으로부터 따릅니다. 비슷한 논증은 두 번째 부등식을 보이기 위해 만들어질 수 있습니다. 마지막 엄격한 부등식은 $e^{k}>k^{k}/k!$ 와 동등하며, 그것은 분명한데 왜냐하면 RHS는 지수 급수 $e^{k}=\sum _{j=0}^{\infty }k^{j}/j!$ 의 항이기 때문입니다.

나눔-가능성 속성으로부터 우리는 다음임을 추론할 수 있습니다:

{\frac {{\text{lcm}}(n-k,\ldots ,n)}{(n-k)\cdot {\text{lcm}}({\binom {k}{0}},\ldots ,{\binom {k}{k}})}}\leq {\binom {n}{k}}\leq {\frac {{\text{lcm}}(n-k,\ldots ,n)}{n-k}}

,

여기서 등호 둘 다는 성립될 수 있습니다.^[11]

Both $n$ and $k$ large

스털링의 근사(Stirling's approximation)는 다음 근사를 산출하며, $n,k$ 둘 다가 무한대로 경향일 때 유효합니다:

{n \choose k}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}

왜냐하면 스털링의 공식의 부등식 형식은 역시 팩토리얼에 경계지기 때문에, 위의 점근 근사에 대한 약간의 변형은 정확한 경계를 제공합니다.

특히, $n$ 이 충분히 클 때:

{2n \choose n}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}

and

{\sqrt {n}}{2n \choose n}\geq 2^{2n-1}

및, 일반적으로, m ≥ 2 및 n ≥ 1에 대해,^[why?]

{\sqrt {n}}{mn \choose n}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}

숫자 둘 다가 같은 비율에서 커질 때, 또 다른 유용한 접근적 근사는 다음입니다:

\log _{2}{n \choose k}\sim nH(k/n)=k\log _{2}(n/k)+(n-k)\log _{2}(n/(n-k))

여기서 $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ 는 이진 엔트로피 함수(binary entropy function)입니다.

$n$ much larger than $k$

$n$ 이 크고 $k$ 가 $n$ 보다 충분히 더 작을 때, 우리는 역시 다음을 쓸 수 있습니다:

{n \choose k}={\frac {n(n-1)\dots (n-k+1)}{k!}}\approx {\frac {(n-k/2)^{k}}{k^{k}e^{-k}{\sqrt {2\pi k}}}}={\frac {(n/k-0.5)^{k}e^{k}}{\sqrt {2\pi k}}}\,,

이것은 스털링의 공식의 다음 아날로그를 제공합니다:

\ln {n \choose k}\approx k\ln(n/k-0.5)+k-0.5\ln(2\pi k)\,.

만약 보다 정밀도가 요구되면, 우리는 적분과 함께 $\ln {(n(n-1)\dots (n-k+1))}$ 을 근사할 수 있으며, 다음을 얻습니다:

\ln {n \choose 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)

$n=20$ 및 $k=10$ , $\ln {\tbinom {n}{k}}\approx 12.127$ 에 대해, 이들 근사는 각각 12.312 및 12.133을 산출합니다.

만약 n이 크고 k는 n에서 선형이면, 다양한 정확한 점근 추정은 이항 계수 ${\binom {n}{k}}$ 에 대해 존재합니다. 예를 들어, 만약 $|n/2-k|=o(n^{2/3})$ 이면, 다음입니다:^[12]

{\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입니다.

Sums of binomial coefficients

이항 계수의 합에 대해 간단하고 거친 위쪽 경계는 이항 정리(binomial theorem)를 사용하여 구할 수 있습니다:

\sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}

보다 정확한 경계는 다음에 의해 제공됩니다:

{\frac {1}{\sqrt {8n\epsilon (1-\epsilon )}}}\cdot 2^{H(\epsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\epsilon )\cdot n}\,.

이것은 $\epsilon \doteq k/n\leq 1/2$ 을 갖는 모든 정수 $n\geq k\geq 1$ 에 대해 유효합니다.^[13]

Generalized binomial coefficients

감마 함수에 대해 무한 곱 공식은 이항 계수에 대해 역시 표현을 제공합니다:

(-1)^{k}{z \choose k}={-z+k-1 \choose k}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {(1+{\frac {1}{j}})^{-z-1}}{1-{\frac {z+1}{j}}}}

이것은 $k\to \infty$ 일 때, 다음 점근 공식을 산출합니다:

{z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad \mathrm {and} \qquad {z+k \choose k}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)

.

이 점근적 행동은 마찬가지로 다음 근사에서 포함됩니다:

{z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}

.

(여기서 $H_{k}$ 는 k-번째 조화 숫자(harmonic number)이고 $\gamma$ 는 오일러–마스케로니 상수(Euler–Mascheroni constant)입니다.)

게다가, 점근 공식

{\frac {z+k \choose j}{k \choose j}}\to \left(1-{\frac {j}{k}}\right)^{-z}\quad {\text{and}}\quad {\frac {j \choose j-k}{j-z \choose j-k}}\to \left({\frac {j}{k}}\right)^{z}

은, 어떤 복소수 $x$ 에 대해 $k\to \infty$ 이고 $j/k\to x$ 일 때마다, 참을 유지합니다.

Generalizations

Generalization to multinomials

이항 계수는 다음 숫자로 정의되는 다항 계수(multinomial coefficients)로 일반화될 수 있습니다:

{n \choose k_{1},k_{2},\ldots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}

여기서

\sum _{i=1}^{r}k_{i}=n.

이항 계수가 (x+y)ⁿ의 계수를 나타내지만, 다항 계수는 다음 다항식의 계수를 나타냅니다:

(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}}.

다항 계수의 조합론적 해석은 r (구별-가능한) 컨테이너에 걸쳐 n 구별-가능한 원소의 분포이며, 각각 정확하게 k_i 원소를 포함하며, 여기서 i는 컨테이너의 인덱스입니다.

다중 계수는 이항 계수의 속성과 비슷한 많은 속성을 가지며, 예를 들어 재귀 관계:

{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}

및 대칭:

{n \choose k_{1},k_{2},\ldots ,k_{r}}={n \choose k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}

여기서 $(\sigma _{i})$ 는 (1,2,...,r)의 순열(permutation)입니다.

Taylor series

첫 번째 종류의 스털링 숫자(Stirling numbers of the first kind)를 사용하여, 임의의 임의적으로 선택된 점 $z_{0}$ 주위의 급수 전개(series expansion)는 다음입니다:

{\begin{aligned}{z \choose 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}{z_{0} \choose 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}{j \choose i}{\frac {s_{k,j}}{k!}}.\end{aligned}}

Binomial coefficient with n = 1/2

이항 계수의 정의는 $n$ 이 실수이고 $k$ 가 정수인 경우로 확장될 수 있습니다.

특히, 다음 항등식은 임의의 비-음의 정수 $k$ 에 대해 유지됩니다:

{{1/2} \choose {k}}={{2k} \choose {k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.

이것은 ${\sqrt {1+x}}$ 를 뉴턴 이항 급수를 사용하여 거듭제곱 급수로 전개할 때 나타납니다:

{\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}.

Identity for the product of binomial coefficients

우리는 이항 계수의 곱을 이항 계수의 선형 조합으로 표현할 수 있습니다:

{z \choose m}{z \choose n}=\sum _{k=0}^{m}{m+n-k \choose k,m-k,n-k}{z \choose m+n-k},

여기서 연결 계수는 다항 계수(multinomial coefficients)입니다. 레이블된 조합론적 대상의 관점에서, 연결 계수는 그들의 첫 번째 k 레이블을 식별, 또는 가중치 m + n − k의 새로운 레이블된 조합론적 대상을 얻기 위해 함께 접착되어진—각각 가중치 m과 n의—레이블된 조합론적 대상의 쌍에 대해 m + n − k 레이블을 할당하기 위한 방법의 숫자를 나타냅니다. (즉, 레이블을 세 부분으로 분리하여 접착 부분, 첫 번째 대상의 접착되지 않은 부분, 및 두 번째 대상의 접착되지 않은 부분에 적용하는 것입니다.) 이것과 관련하여, 이항 계수는 떨어지는 팩토리얼(falling factorial)이 보통의 생성 급수인 것에 대해 지수 생성 급수인 것입니다.

Partial fraction decomposition

역수의 부분 분수 분해(partial fraction decomposition)는 다음에 의해 제공됩니다:

{\frac {1}{z \choose n}}=\sum _{i=0}^{n-1}(-1)^{n-1-i}{n \choose i}{\frac {n-i}{z-i}},\qquad {\frac {1}{z+n \choose n}}=\sum _{i=1}^{n}(-1)^{i-1}{n \choose i}{\frac {i}{z+i}}.

Newton's binomial series

아이작 뉴턴 경(Sir Isaac Newton)의 이름을 따서 지은, 뉴턴의 이항 급수는 무한 급수에 대한 이항 정리의 일반화입니다:

(1+z)^{\alpha }=\sum _{n=0}^{\infty }{\alpha \choose n}z^{n}=1+{\alpha \choose 1}z+{\alpha \choose 2}z^{2}+\cdots .

항등식은 양쪽 변이 미분 방정식(differential equation) (1 + z) f'(z) = α f(z)을 만족시키는 것을 보임으로써 획득될 수 있습니다.

이 급수의 수렴의 반지름(radius of convergence)은 1입니다. 대안적인 표현은 다음입니다:

{\frac {1}{(1-z)^{\alpha +1}}}=\sum _{n=0}^{\infty }{n+\alpha \choose n}z^{n}

여기서 다음 항등식이 적용됩니다:

{n \choose k}=(-1)^{k}{k-n-1 \choose k}

.

Multiset (rising) binomial coefficient

이항 계수는 주어진 집합으로부터 지정된 크기의 부분-집합을 셉니다. 관련된 조합론적 문제는 주어진 집합으로부터 추출된 원소를 갖는 지정된 크기의 중복-집합(multiset)을 세는 것입니다. 즉, 같은 원소를 반복적으로 선택할 수 있는 가능성과 함께 주어진 집합으로부터 특정 숫자의 원소를 선택하는 방법의 숫자를 셉니다. 결과 집합은 중복-집합 계수(multiset coefficients)로 불립니다;^[14] n 원소 집합으로부터 k 항목을 "중복-선택(multichoose") (즉, 복원과 함께 선택(choose with replacement))하는 방법의 숫자는 $\left(\!\!{\binom {n}{k}}\!\!\right)$ 로 표시됩니다.

이 기사에서 n의 주된 표기와 모호함과 혼동을 피하기 위해,
f = n = r + (k – 1) 및 r = f – (k – 1)으로 놓습니다.

중복-집합 계수는 다음 규칙에 의해 이항 계수의 관점에서 표현될 수 있습니다:

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

이 항등식의 한 가지 가능한 대안적인 특성화는 다음처럼 입니다: 우리는 떨어지는 팩토리얼(falling factorial)을 다음으로 정의할 수 있을 것입니다:

(f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f

,

그리고 대응하는 올라가는 팩토리얼은 다음으로 정의할 수 있을 것입니다:

{\color {white}{\big |}}r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1)

;

그래서, 예를 들어,

17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}

.

그런-다음 이항 계수는 다음으로 쓸 수 있습니다:

{\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)\cdots (f-2)\cdot (f-1)\cdot f}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}

,

반면에 대응하는 중복집합 계수는 떨어지는 팩토리얼을 올라가는 팩토리얼로 대체함으로써 정의됩니다:

\left(\!\!{\binom {r}{k}}\!\!\right)={\frac {r^{(k)}}{k!}}={\frac {r\cdot (r+1)\cdot (r+2)\cdots (r+k-1)}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}

.

Generalization to negative integers

임의의 n에 대해,

{\begin{aligned}{\binom {-n}{k}}&={\frac {-n\cdot -(n+1)\dots -(n+k-2)\cdot -(n+k-1)}{k!}}\\&=(-1)^{k}\;{\frac {n\cdot (n+1)\cdot (n+2)\cdots (n+k-1)}{k!}}\\&=(-1)^{k}{\binom {n+k-1}{k}}\\&=(-1)^{k}\left(\!\!{\binom {n}{k}}\!\!\right)\;.\end{aligned}}

특히, 음의 정수에서 평가된 이항 계수는 부호화된 중복집합 계수에 의해 제공됩니다. 특별한 경우 $n=-1$ 에서, 이것은 $(-1)^{k}={\binom {-1}{k}}=\left(\!\!{\binom {-k}{k}}\!\!\right)$ 로 줄어듭니다.

예를 들어, 만약 n = –4이고 k = 7이면, r = 4이고 f = 10입니다:

{\begin{aligned}{\binom {-4}{7}}&={\frac {-10\cdot -9\cdot -8\cdot -7\cdot -6\cdot -5\cdot -4}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=(-1)^{7}\;{\frac {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=\left(\!\!{\binom {-7}{7}}\!\!\right)\left(\!\!{\binom {4}{7}}\!\!\right)={\binom {-1}{7}}{\binom {10}{7}}.\end{aligned}}

Two real or complex valued arguments

이항 계수는 다음을 통해 감마 함수(gamma function) 또는 베타 함수(beta function)를 사용하여 두 실수 또는 복소수-값 인수에 대해 일반화됩니다.

{x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (x-y+1,y+1)}}

.

이 정의는 $\Gamma$ 로부터 이들 다음 추가적인 속성을 상속합니다:

{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 }}.

결과 함수는 거의 연구되지 않았으며, 분명히 (Fowler 1996)에서 첫 번째 그래프로 나타납니다. 특히, 많은 이항 항은 실패합니다: n 양수 (그래서 $-n$ 은 음수)에 대해 $\textstyle {{n \choose m}={n \choose n-m}}$ 이지만 $\textstyle {{-n \choose m}\neq {-n \choose -n-m}}$ 입니다. 이 동작은 매우 복잡하고, 다양한 팔분면 (즉, x 및 y 축 및 직선 $y=x$ 에 관하여)에서 현저하게 다르며, 음의 x에 대해 동작은 음수 정수 값 및 양과 음의 영역의 체커보드에서 특이점을 가집니다:

팔분면 $0\leq y\leq x$ 에서, 그것은, 산등성이 ("파스칼의 산등성이")을 갖는, 보통의 이항의 매끄러운 보간된 형식입니다.
팔분면 $0\leq x\leq y$ 및 사분면 $x\geq 0,y\leq 0$ 에서, 함수는 영에 근접합니다.
사분면 $x\leq 0,y\geq 0$ 에서, 함수는 다음 꼭짓점을 갖는 평행사변형에서 교대로 매우 큰 양수 및 음수입니다:

(-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)

팔분면 $0>x>y$ 에서, 동작은 다시 교대로 양과 음이지만, 사각형 격자 위에 있습니다.
팔분면 $-1>y>x+1$ 에서, 그것은 특이점 근처를 제외하고 영에 근접합니다.

Generalization to q-series

이항 계수는 가우스 이항 계수(Gaussian binomial coefficient)로 알려진 q-아날로그(q-analog) 일반화를 가집니다.

Generalization to infinite cardinals

이항 계수의 정의는 다음 정의에 의해 무한 세는-숫자(infinite cardinals)로 일반화될 수 있습니다:

{\alpha \choose \beta }=|\{B\subseteq A:|B|=\beta \}|

여기서 A는 카디널리티(cardinality) $\alpha$ 를 갖는 어떤 집합입니다. 우리가 세는-숫자 $\alpha$ , ${\alpha \choose \beta }$ 를 나타내기 위해 선택한 집합이 동일하게 유지될 것이라는 의미에서, 우리는 일반화된 이항 계수가 잘-정의되어 있음을 보일 수 있습니다. 유한 세는-숫자에 대해, 이 정의는 이항 계수의 표준 정의와 일치합니다.

선택의 공리(Axiom of Choice)를 가정하면, 우리는 임의의 무한 세는-숫자 $\alpha$ 에 대해 ${\alpha \choose \alpha }=2^{\alpha }$ 임을 보일 수 있습니다.

Binomial coefficient in programming languages

표기법 ${n \choose k}$ 은 손으로 쓰기에 편리하지만 타자기(typewriter)와 컴퓨터 터미널(computer terminal)에서 불편합니다. 많은 프로그래밍 언어(programming language)는 이항 계수 계산을 위한 표준 서브-루틴(subroutine)을 제공하지 않지만, 예를 들어 APL 프로그래밍 언어(APL programming language)와 (관련된) J 프로그래밍 언어(J programming language) 둘 다는 느낌표를 사용합니다: k ! n .

파이썬(Python)의 다음 스니펫과 같은 팩토리얼 공식의 소박한 구현:

from math import factorial
def binomialCoefficient(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

은 매우 느리고 매우 높은 숫자의 팩토리얼을 계산하는 것에는 쓸모가 없습니다 (C 또는 자바(Java)와 같은 언어에서 그들은 이 이유때문에 오버플로 오류를 겪습니다). 곱셈적 공식의 직접 구현이 잘 작동합니다:

def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k) # take advantage of symmetry
    c = 1
    for i in range(k):
        c = c * (n - i) / (i + 1)
    return c

(파이썬에서, range(k)는 0에서 k–1까지 목록을 생성합니다.)

파스칼의 규칙(Pascal's rule)은 재귀 정의를 제공하며 이것은 비록 그것이 덜 효과적일지라도, 파이썬에서 역시 구현 될 수 있습니다:

def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k > n - k: # take advantage of symmetry
        k = n - k
    if k == 0 or n <= 1:
    	return 1
    return binomialCoefficient(n-1, k) + binomialCoefficient(n-1, k-1)

위에 언급된 예제는 함수형 스타일에서 역시 쓸 수 있습니다. 다음 스킴(Scheme) 예제는 재귀 관계를 사용합니다:

{n \choose k+1}={\frac {n-k}{k+1}}{n \choose k}

유리수 산술은 정수 나눗셈을 사용하여 쉽게 회피될 수 있습니다:

{n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)

다음 구현은 모든 이들 아이디어를 사용합니다:

(define (binomial n k)
;; Helper function to compute C(n,k) via forward recursion
  (define (binomial-iter n k i prev)
    (if (>= i k)
      prev
     (binomial-iter n k (+ i 1) (/ (* (- n i) prev) (+ i 1)))))
;; Use symmetry property C(n,k)=C(n, n-k)
  (if (< k (-  n k))
    (binomial-iter n k 0 1)
    (binomial-iter n (- n k) 0 1)))

고정된-길이 정수를 갖는 언어에서 $\textstyle {n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)$ 를 계산할 때, $(n-k)$ 와 곱셈은 심지어 결과가 적합할 때에도 오버플로일 수 있습니다. 오버플로는 먼저 나누고 나머지를 사용하여 결과를 수정함으로써 피해질 수 있습니다:

{n \choose k+1}=\left[\textstyle {n \choose k}\div (k+1)\right](n-k)+{\left[{n \choose k}\ \mathrm {mod} \ (k+1)\right](n-k) \over (k+1)}

C 언어에서 구현:

#include <limits.h>

unsigned long binomial(unsigned long n, unsigned long k) {
  unsigned long c = 1, i;
  
  if (k > n-k) // take advantage of symmetry
    k = n-k;
  
  for (i = 1; i <= k; i++, n--) {
    if (c/i > UINT_MAX/n) // return 0 on overflow
      return 0;
      
    c = c / i * n + c % i * n / i;  // split c * n / i into (c / i * i + c % i) * n / i
  }
  
  return c;
}

큰 숫자를 사용할 때 이항 계수를 계산하기 위한 또 다른 방법은 다음임을 인식하는 것입니다:

{n \choose k}={\frac {n!}{k!\,(n-k)!}}={\frac {\Gamma (n+1)}{\Gamma (k+1)\,\Gamma (n-k+1)}}=\exp(\ln \Gamma (n+1)-\ln \Gamma (k+1)-\ln \Gamma (n-k+1)),

여기서 $\ln$ $\Gamma (n)$ 은 $n$ 에서 감마 함수(gamma function)의 자연 로그(natural logarithm)를 나타냅니다. 맥시마(Maxima)에서 log_gamma, 매스매티카(Mathematica)에서 LogGamma, 매트랩(MATLAB)의 gammaln 및 파이썬의 사이파이(PciPy) 모듈, PARI/GP에서 lngamma 또는 C, R,^[15] 및 줄리아(Julia)에서 lgamma와 같은 일부 프로그래밍 언어에서 쉽게 계산되고 표준인 특수 함수입니다. 반올림 오류는 반환된 값이 정수가 아닌 원인이 될 수 있습니다.

Notes

^ Higham (1998)
^ Lilavati Section 6, Chapter 4 (see Knuth (1997)).
^ See (Graham, Knuth & Patashnik 1994), which also defines ${\tbinom {n}{k}}=0$ for $k<0$ . Alternative generalizations, such as to two real or complex valued arguments using the Gamma function assign nonzero values to ${\tbinom {n}{k}}$ for $k<0$ , but this causes most binomial coefficient identities to fail, and thus is not widely used by the majority of definitions. One such choice of nonzero values leads to the aesthetically pleasing "Pascal windmill" in Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997, but causes even Pascal's identity to fail (at the origin).
^ Muir, Thomas (1902). "Note on Selected Combinations". Proceedings of the Royal Society of Edinburgh.
^ This can be seen as a discrete analog of Taylor's theorem. It is closely related to Newton's polynomial. Alternating sums of this form may be expressed as the Nörlund–Rice integral.
^ Gradshteyn & Ryzhik (2014, pp. 3–4) .
^ Boardman, Michael (2004), "The Egg-Drop Numbers", Mathematics Magazine, 77 (5): 368–372, doi:10.2307/3219201, JSTOR 3219201, MR 1573776, it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients.
^ see induction developed in eq (7) p. 1389 in Aupetit, Michael (2009), "Nearly homogeneous multi-partitioning with a deterministic generator", Neurocomputing, 72 (7–9): 1379–1389, doi:10.1016/j.neucom.2008.12.024, ISSN 0925-2312.
^ Ruiz, Sebastian (1996). "An Algebraic Identity Leading to Wilson's Theorem". The Mathematical Gazette. 80 (489): 579–582. arXiv:math/0406086. doi:10.2307/3618534. JSTOR 3618534.
^ Benjamin & Quinn 2003, pp. 4−5
^ ^a ^b Farhi, Bakir (2007). "Nontrivial lower bounds for the least common multiple of some finite sequence of integers". Journal of Number Theory. 125: 393–411. arXiv:0803.0290. doi:10.1016/j.jnt.2006.10.017.
^ Spencer, Joel; Florescu, Laura (2014). Asymptopia. Student mathematical library. Vol. 71. AMS. p. 66. ISBN 978-1-4704-0904-3. OCLC 865574788.
^ see e.g. Ash (1990, p. 121) or Flum & Grohe (2006, p. 427).
^ Munarini, Emanuele (2011), "Riordan matrices and sums of harmonic numbers" (PDF), Applicable Analysis and Discrete Mathematics, 5 (2): 176–200, doi:10.2298/AADM110609014M, MR 2867317.
^ Bloomfield, Victor A. (2016). Using R for Numerical Analysis in Science and Engineering. CRC Press. p. 74. ISBN 978-1-4987-8662-1.

References

Ash, Robert B. (1990) [1965]. Information Theory. Dover Publications, Inc. ISBN 0-486-66521-6. {{cite book}}: Invalid |ref=harv (help)
Benjamin, Arthur T.; Quinn, Jennifer J. (2003). Proofs that Really Count: The Art of Combinatorial Proof. Dolciani Mathematical Expositions. Vol. 27. Mathematical Association of America. ISBN 978-0-88385-333-7. {{cite book}}: Invalid |ref=harv (help)
Bryant, Victor (1993). Aspects of combinatorics. Cambridge University Press. ISBN 0-521-41974-3.
Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. {{cite book}}: Invalid |ref=harv (help)
Fowler, David (January 1996). "The Binomial Coefficient Function". The American Mathematical Monthly. 103 (1). Mathematical Association of America: 1–17. doi:10.2307/2975209. JSTOR 2975209. {{cite journal}}: Invalid |ref=harv (help)
Goetgheluck, P. (1987). "Computing Binomial Coefficients". American Mathematical Monthly. 94: 360–365. doi:10.2307/2323099.
Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (Second ed.). Addison-Wesley. pp. 153–256. ISBN 0-201-55802-5. {{cite book}}: Invalid |ref=harv (help)
Gradshteyn, I. S.; Ryzhik, I. M. (2014). Table of Integrals, Series, and Products (8th ed.). Academic Press. ISBN 978-0-12-384933-5. {{cite book}}: Invalid |ref=harv (help); Unknown parameter |titlelink= ignored (|title-link= suggested) (help)
Grinshpan, A. Z. (2010), "Weighted inequalities and negative binomials", Advances in Applied Mathematics, 45 (4): 564–606, doi:10.1016/j.aam.2010.04.004
Higham, Nicholas J. (1998). Handbook of writing for the mathematical sciences. SIAM. p. 25. ISBN 0-89871-420-6. {{cite book}}: Invalid |ref=harv (help)
Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Third ed.). Addison-Wesley. pp. 52–74. ISBN 0-201-89683-4. {{cite book}}: Invalid |ref=harv (help)
Singmaster, David (1974). "Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients". Journal of the London Mathematical Society. 8 (3): 555–560. doi:10.1112/jlms/s2-8.3.555. {{cite journal}}: Invalid |ref=harv (help)
Shilov, G. E. (1977). Linear algebra. Dover Publications. ISBN 978-0-486-63518-7. {{cite book}}: Invalid |ref=harv (help)

External links

"Binomial coefficients", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Andrew Granville (1997). "Arithmetic Properties of Binomial Coefficients I. Binomial coefficients modulo prime powers". CMS Conf. Proc. 20: 151–162.

This article incorporates material from the following PlanetMath articles, which are licensed under the Creative Commons Attribution/Share-Alike License: Binomial Coefficient, Upper and lower bounds to binomial coefficient, Binomial coefficient is an integer, Generalized binomial coefficients.

[1] Higham (1998)

[2] Lilavati Section 6, Chapter 4 (see Knuth (1997)).

[3] See (Graham, Knuth & Patashnik 1994), which also defines ${\tbinom {n}{k}}=0$ for $k<0$ . Alternative generalizations, such as to two real or complex valued arguments using the Gamma function assign nonzero values to ${\tbinom {n}{k}}$ for $k<0$ , but this causes most binomial coefficient identities to fail, and thus is not widely used by the majority of definitions. One such choice of nonzero values leads to the aesthetically pleasing "Pascal windmill" in Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997, but causes even Pascal's identity to fail (at the origin).

[4] Muir, Thomas (1902). "Note on Selected Combinations". Proceedings of the Royal Society of Edinburgh.

[5] This can be seen as a discrete analog of Taylor's theorem. It is closely related to Newton's polynomial. Alternating sums of this form may be expressed as the Nörlund–Rice integral.

[6] Gradshteyn & Ryzhik (2014, pp. 3–4) .

[7] Boardman, Michael (2004), "The Egg-Drop Numbers", Mathematics Magazine, 77 (5): 368–372, doi:10.2307/3219201, JSTOR 3219201, MR 1573776, it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients.

[8] see induction developed in eq (7) p. 1389 in Aupetit, Michael (2009), "Nearly homogeneous multi-partitioning with a deterministic generator", Neurocomputing, 72 (7–9): 1379–1389, doi:10.1016/j.neucom.2008.12.024, ISSN 0925-2312.

[9] Ruiz, Sebastian (1996). "An Algebraic Identity Leading to Wilson's Theorem". The Mathematical Gazette. 80 (489): 579–582. arXiv:math/0406086. doi:10.2307/3618534. JSTOR 3618534.

[10] Benjamin & Quinn 2003, pp. 4−5

[Farhi2007-11] Farhi, Bakir (2007). "Nontrivial lower bounds for the least common multiple of some finite sequence of integers". Journal of Number Theory. 125: 393–411. arXiv:0803.0290. doi:10.1016/j.jnt.2006.10.017.

[12] Spencer, Joel; Florescu, Laura (2014). Asymptopia. Student mathematical library. Vol. 71. AMS. p. 66. ISBN 978-1-4704-0904-3. OCLC 865574788.

[13] see e.g. Ash (1990, p. 121) or Flum & Grohe (2006, p. 427).

[14] Munarini, Emanuele (2011), "Riordan matrices and sums of harmonic numbers" (PDF), Applicable Analysis and Discrete Mathematics, 5 (2): 176–200, doi:10.2298/AADM110609014M, MR 2867317.

[15] Bloomfield, Victor A. (2016). Using R for Numerical Analysis in Science and Engineering. CRC Press. p. 74. ISBN 978-1-4987-8662-1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]