Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Binomial coefficient

From Wikipedia, the free encyclopedia
Number of subsets of a given size
"nCk" redirects here. For other uses, seeNCK (disambiguation).
The binomial coefficients can be arranged to formPascal's triangle, in which each entry is the sum of the two immediately above.
Visualisation of binomial expansion up to the4th power

Inmathematics, thebinomial coefficients are the positiveintegers that occur ascoefficients in thebinomial theorem. Commonly, a binomial coefficient is indexed by a pair of integersn ≥k ≥ 0 and is written(nk).{\displaystyle {\tbinom {n}{k}}.} It is the coefficient of thexk term in thepolynomial expansion of thebinomialpower(1 +x)n; this coefficient can be computed by the multiplicative formula

(nk)=n×(n−1)×⋯×(n−k+1)k×(k−1)×⋯×1,{\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\times \cdots \times 1}},}

which usingfactorial notation can be compactly expressed as

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

For example, the fourth power of1 +x is

(1+x)4=(40)x0+(41)x1+(42)x2+(43)x3+(44)x4=1+4x+6x2+4x3+x4,{\displaystyle {\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}}}

and the binomial coefficient(42)=4×32×1=4!2!2!=6{\displaystyle {\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6} is the coefficient of thex2 term.

Arranging the numbers(n0),(n1),…,(nn){\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}} in successive rows forn = 0, 1, 2, ... gives atriangular array calledPascal's triangle, satisfying therecurrence relation

(nk)=(n−1k−1)+(n−1k).{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}.}

The binomial coefficients occur in many areas of mathematics, and especially incombinatorics. In combinatorics the symbol(nk){\displaystyle {\tbinom {n}{k}}} is usually read as "n choosek" because there are(nk){\displaystyle {\tbinom {n}{k}}} ways to choose an (unordered) subset ofk elements from a fixed set ofn elements. For example, there are(42)=6{\displaystyle {\tbinom {4}{2}}=6} ways to choose2 elements from{1, 2, 3, 4}, namely{1, 2},{1, 3},{1, 4},{2, 3},{2, 4} and{3, 4}.

The first form of the binomial coefficients can be generalized to(zk){\displaystyle {\tbinom {z}{k}}} for anycomplex numberz and integerk ≥ 0, and many of their properties continue to hold in this more general form.

History and notation

[edit]

Andreas von Ettingshausen introduced the notation(nk){\displaystyle {\tbinom {n}{k}}} in 1826,[1] although the numbers were known centuries earlier (seePascal's triangle). In about 1150, the Indian mathematicianBhaskaracharya gave an exposition of binomial coefficients in his bookLīlāvatī.[2]

Alternative notations includeC(n,k),nCk,nCk,Ck
n,[3]Cn
k, andCn,k, in all of which theC stands forcombinations orchoices; theC notation means the number of ways to choosek out ofn objects. Many calculators use variants of theC notation because they can represent it on a single-line display. In this form the binomial coefficients are easily compared to the numbers ofk-permutations ofn, written asP(n,k), etc.

Definition and interpretations

[edit]
k
n
01234⋯
010000⋯
111000⋯
212100⋯
313310⋯
414641⋯
⋮⋮⋮⋮⋮⋮⋱
The first few binomial coefficients
on a left-aligned Pascal's triangle

Fornatural numbers (taken to include 0)n andk, the binomial coefficient(nk){\displaystyle {\tbinom {n}{k}}} can be defined as thecoefficient of themonomialXk in the expansion of(1 +X)n. The same coefficient also occurs (ifk ≤n) in thebinomial formula

(x+y)n=∑k=0n(nk)xkyn−k{\displaystyle (x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n-k}}∗

(valid for any elementsx,y of acommutative ring),which explains the name "binomial coefficient".

Another occurrence of this number is in combinatorics, where it gives the number of ways, disregarding order, thatk objects can be chosen from amongn objects; more formally, the number ofk-element subsets (ork-combinations) of ann-element set. This number can be seen as equal to that of the first definition, independently of any of the formulas below to compute it: if in each of then factors of the power(1 +X)n one temporarily labels the termX with an indexi (running from1 ton), then each subset ofk indices gives after expansion a contributionXk, and the coefficient of that monomial in the result will be the number of such subsets. This shows in particular that(nk){\displaystyle {\tbinom {n}{k}}} is a natural number for any natural numbersn andk. There are many other combinatorial interpretations of binomial coefficients (counting problems for which the answer is given by a binomial coefficient expression), for instance the number of words formed ofnbits (digits 0 or 1) whose sum isk is given by(nk){\displaystyle {\tbinom {n}{k}}}, while the number of ways to writek=a1+a2+⋯+an{\displaystyle k=a_{1}+a_{2}+\cdots +a_{n}} where everyai is a nonnegative integer is given by⁠(n+k−1n−1){\displaystyle {\tbinom {n+k-1}{n-1}}}⁠. Most of these interpretations can be shown to be equivalent to countingk-combinations.

Computing the value of binomial coefficients

[edit]

Several methods exist to compute the value of(nk){\displaystyle {\tbinom {n}{k}}} without actually expanding a binomial power or countingk-combinations.

Recursive formula

[edit]

One method uses therecursive, purely additive formula(nk)=(n−1k−1)+(n−1k){\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}} for all integersn,k{\displaystyle n,k} such that1≤k<n,{\displaystyle 1\leq k<n,}with boundary values(n0)=(nn)=1{\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}for all integersn ≥ 0.

The formula follows from considering the set{1, 2, 3, ...,n} and counting separately (a) thek-element groupings that include a particular set element, say "i", in every group (since "i" is already chosen to fill one spot in every group, we need only choosek − 1 from the remainingn − 1) and (b) all thek-groupings that don't include "i"; this enumerates all the possiblek-combinations ofn elements. It also follows from tracing the contributions toXk in(1 +X)n−1(1 +X). As there is zeroXn+1 orX−1 in(1 +X)n, one might extend the definition beyond the above boundaries to include(nk)=0{\displaystyle {\tbinom {n}{k}}=0} when eitherk >n ork < 0. This recursive formula then allows the construction ofPascal's triangle, surrounded by white spaces where the zeros, or the trivial coefficients, would be.

Multiplicative formula

[edit]

A more efficient method to compute individual binomial coefficients is given by the formula(nk)=nk_k!=n(n−1)(n−2)⋯(n−(k−1))k(k−1)(k−2)⋯1=∏i=1kn+1−ii,{\displaystyle {\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}},}where the numerator of the first fraction,nk_{\displaystyle n^{\underline {k}}}, is afalling factorial.This formula is easiest to understand for the combinatorial interpretation of binomial coefficients.The numerator gives the number of ways to select a sequence ofk distinct objects, retaining the order of selection, from a set ofn objects. The denominator counts the number of distinct sequences that define the samek-combination when order is disregarded. This formula can also be stated in a recursive form. Using the "C" notation from above,Cn,k=Cn,k−1⋅(n−k+1)/k{\displaystyle C_{n,k}=C_{n,k-1}\cdot (n-k+1)/k}, whereCn,0=1{\displaystyle C_{n,0}=1}. It is readily derived by evaluatingCn,k/Cn,k−1{\displaystyle C_{n,k}/C_{n,k-1}} and can intuitively be understood as starting at the leftmost coefficient of then{\displaystyle n}-th row ofPascal's triangle, whose value is always1{\displaystyle 1}, and recursively computing the next coefficient to its right until thek{\displaystyle k}-th one is reached.

Due to the symmetry of thebinomial coefficients with regard tok andn −k, calculation of the above product, as well as the recursive relation, may be optimised by setting its upper limit to the smaller ofk andn −k.

Factorial formula

[edit]

Finally, though computationally unsuitable, there is the compact form, often used in proofs and derivations, which makes repeated use of the familiarfactorial function:(nk)=n!k!(n−k)!for  0≤k≤n,{\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,}wheren! denotes the factorial ofn. This formula follows from the multiplicative formula above by multiplying numerator and denominator by(n −k)!; as a consequence it involves many factors common to numerator and denominator. It is less practical for explicit computation (in the case thatk is small andn is large) unless common factors are first cancelled (in particular since factorial values grow very rapidly). The formula does exhibit a symmetry that is less evident from the multiplicative formula (though it is from the definitions)

(nk)=(nn−k)for  0≤k≤n,{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}\quad {\text{for }}\ 0\leq k\leq n,}1

which leads to a more efficient multiplicative computational routine. Using thefalling factorial notation,(nk)={nk_/k!if  k≤n2nn−k_/(n−k)!if  k>n2.{\displaystyle {\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

[edit]
Main article:Binomial series

The multiplicative formula allows the definition of binomial coefficients to be extended[4] by replacingn by an arbitrary numberα (negative, real, complex) or even an element of anycommutative ring in which all positive integers are invertible:(αk)=αk_k!=α(α−1)(α−2)⋯(α−k+1)k(k−1)(k−2)⋯1for k∈N and arbitrary α.{\displaystyle {\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 .}

With this definition one has a generalization of the binomial formula (with one of the variables set to 1), which justifies still calling the(αk){\displaystyle {\tbinom {\alpha }{k}}} binomial coefficients:

(1+X)α=∑k=0∞(αk)Xk.{\displaystyle (1+X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.}2

This formula is valid for all complex numbersα andX with |X| < 1. It can also be interpreted as an identity offormal power series inX, where it actually can serve as definition of arbitrary powers ofpower series with constant coefficient equal to 1; the point is that with this definition all identities hold that one expects forexponentiation, notably(1+X)α(1+X)β=(1+X)α+βand((1+X)α)β=(1+X)αβ.{\displaystyle (1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta }\quad {\text{and}}\quad ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }.}

Ifα is a nonnegative integern, then all terms withk >n are zero,[5] and the infinite series becomes a finite sum, thereby recovering the binomial formula. However, for other values ofα, including negative integers and rational numbers, the series is really infinite.

Pascal's triangle

[edit]
1000th row of Pascal's triangle, arranged vertically, with grey-scale representations of decimal digits of the coefficients, right-aligned. The left boundary of the image corresponds roughly to the graph of the logarithm of the binomial coefficients, and illustrates that they form alog-concave sequence.
Main articles:Pascal's triangle andPascal's rule

Pascal's rule is the importantrecurrence relation

(nk)+(nk+1)=(n+1k+1),{\displaystyle {n \choose k}+{n \choose k+1}={n+1 \choose k+1},}3

which can be used to prove bymathematical induction that(nk){\displaystyle {\tbinom {n}{k}}} is a natural number for all integern ≥ 0 and all integerk, a fact that is not immediately obvious fromformula (1). To the left and right of Pascal's triangle, the entries (shown as blanks) are all zero.

Pascal's rule also gives rise toPascal's triangle:

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

Row numbern contains the numbers(nk){\displaystyle {\tbinom {n}{k}}} fork = 0, …,n. It is constructed by first placing 1s in the outermost positions, and then filling each inner position with the sum of the two numbers directly above. This method allows the quick calculation of binomial coefficients without the need for fractions or multiplications. For instance, by looking at row number 5 of the triangle, one can quickly read off that

(x+y)5=1_x5+5_x4y+10_x3y2+10_x2y3+5_xy4+1_y5.{\displaystyle (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

[edit]

Binomial coefficients are of importance incombinatorics because they provide ready formulas for certain frequent counting problems:

Binomial coefficients as polynomials

[edit]

For any nonnegative integerk, the expression(tk){\textstyle {\binom {t}{k}}} can be written as a polynomial with denominatork!:

(tk)=tk_k!=t(t−1)(t−2)⋯(t−k+1)k(k−1)(k−2)⋯2⋅1;{\displaystyle {\binom {t}{k}}={\frac {t^{\underline {k}}}{k!}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};}

this presents apolynomial int withrational coefficients.

As such, it can be evaluated at any real or complex numbert to define binomial coefficients with such first arguments. These "generalized binomial coefficients" appear inNewton's generalized binomial theorem.

For eachk, the polynomial(tk){\displaystyle {\tbinom {t}{k}}} can be characterized as the unique degreek polynomialp(t) satisfyingp(0) =p(1) = ⋯ =p(k − 1) = 0 andp(k) = 1.

Its coefficients are expressible in terms ofStirling numbers of the first kind:

(tk)=∑i=0ks(k,i)tik!.{\displaystyle {\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.}

Thederivative of(tk){\displaystyle {\tbinom {t}{k}}} can be calculated bylogarithmic differentiation:

ddt(tk)=(tk)∑i=0k−11t−i.{\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}.}

This can cause a problem when evaluated at integers from0{\displaystyle 0} tot−1{\displaystyle t-1}, but using identities below we can compute the derivative as:

ddt(tk)=∑i=0k−1(−1)k−i−1k−i(ti).{\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}=\sum _{i=0}^{k-1}{\frac {(-1)^{k-i-1}}{k-i}}{\binom {t}{i}}.}

Binomial coefficients as a basis for the space of polynomials

[edit]

Over anyfield ofcharacteristic 0 (that is, any field that contains therational numbers), each polynomialp(t) of degree at mostd is uniquely expressible as a linear combination∑k=0dak(tk){\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}} of binomial coefficients, because the binomial coefficients consist of one polynomial of each degree. The coefficientak is thekth difference of the sequencep(0),p(1), ...,p(k). Explicitly,[7]

ak=∑i=0k(−1)k−i(ki)p(i).{\displaystyle a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).}4

Integer-valued polynomials

[edit]
Main article:Integer-valued polynomial

Each polynomial(tk){\displaystyle {\tbinom {t}{k}}} isinteger-valued: it has an integer value at all integer inputst{\displaystyle t}. (One way to prove this is by induction onk usingPascal's identity.) Therefore, any integer linear combination of binomial coefficient polynomials is integer-valued too. Conversely, (4) shows that any integer-valued polynomial is an integer linear combination of these binomial coefficient polynomials. More generally, for any subringR of a characteristic 0 fieldK, a polynomial inK[t] takes values inR at all integersif and only if it is anR-linear combination of binomial coefficient polynomials.

Example

[edit]

The integer-valued polynomial3t(3t + 1) / 2 can be rewritten as

9(t2)+6(t1)+0(t0).{\displaystyle 9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.}

Identities involving binomial coefficients

[edit]

The factorial formula facilitates relating nearby binomial coefficients. For instance, ifk is a positive integer andn is arbitrary, then

(nk)=nk(n−1k−1){\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}}5

and, with a little more work,

(n−1k)−(n−1k−1)=n−2kn(nk).{\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.}

We can also get

(n−1k)=n−kn(nk).{\displaystyle {\binom {n-1}{k}}={\frac {n-k}{n}}{\binom {n}{k}}.}

Moreover, the following may be useful:

(nk)(kj)=(nj)(n−jk−j)=(nk−j)(n−k+jj).{\displaystyle {\binom {n}{k}}{\binom {k}{j}}={\binom {n}{j}}{\binom {n-j}{k-j}}={\binom {n}{k-j}}{\binom {n-k+j}{j}}.}

For constantn, we have the following recurrence:

(nk)=n−k+1k(nk−1).{\displaystyle {\binom {n}{k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}.}

To sum up, we have

(nk)=(nn−k)=n−k+1k(nk−1)=nn−k(n−1k){\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}={\frac {n}{n-k}}{\binom {n-1}{k}}}
=nk(n−1k−1)=nn−2k((n−1k)−(n−1k−1))=(n−1k)+(n−1k−1).{\displaystyle ={\frac {n}{k}}{\binom {n-1}{k-1}}={\frac {n}{n-2k}}{\Bigg (}{\binom {n-1}{k}}-{\binom {n-1}{k-1}}{\Bigg )}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.}

Sums of the binomial coefficients

[edit]

The formula

∑k=0n(nk)=2n{\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}=2^{n}}∗∗

says that the elements in thenth row of Pascal's triangle always add up to 2 raised to thenth power. This is obtained from the binomial theorem (∗) by settingx = 1 andy = 1. The formula also has a natural combinatorial interpretation: the left side sums the number of subsets of {1, ...,n} of sizesk = 0, 1, ...,n, giving the total number of subsets. (That is, the left side counts thepower set of {1, ...,n}.) However, these subsets can also be generated by successively choosing or excluding each element 1, ...,n; then independent binary choices (bit-strings) allow a total of2n{\displaystyle 2^{n}} choices. The left and right sides are two ways to count the same collection of subsets, so they are equal.

The formulas

∑k=0nk(nk)=n2n−1{\displaystyle \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}}6

and

∑k=0nk2(nk)=(n+n2)2n−2{\displaystyle \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}}

follow from the binomial theorem afterdifferentiating with respect tox (twice for the latter) and then substitutingx =y = 1.

TheChu–Vandermonde identity, which holds for any complex valuesm andn and any non-negative integerk, is

∑j=0k(mj)(n−mk−j)=(nk){\displaystyle \sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}}7

and can be found by examination of the coefficient ofxk{\displaystyle x^{k}} in the expansion of(1 +x)m(1 +x)n−m = (1 +x)n using equation (2). Whenm = 1, equation (7) reduces to equation (3). In the special casen = 2m,k =m, using (1), the expansion (7) becomes (as seen in Pascal's triangle at right)

Pascal's triangle, rows 0 through 7. Equation8 form = 3 is illustrated in rows 3 and 6 as12+32+32+12=20.{\displaystyle 1^{2}+3^{2}+3^{2}+1^{2}=20.}
∑j=0m(mj)2=(2mm),{\displaystyle \sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},}8

where the term on the right side is acentral binomial coefficient.

Another form of the Chu–Vandermonde identity, which applies for any integersj,k, andn satisfying0 ≤j ≤k ≤n, is

∑m=0n(mj)(n−mk−j)=(n+1k+1).{\displaystyle \sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}.}9

The proof is similar, but uses the binomial series expansion (2) with negative integer exponents.Whenj =k, equation (9) gives thehockey-stick identity

∑m=kn(mk)=(n+1k+1){\displaystyle \sum _{m=k}^{n}{\binom {m}{k}}={\binom {n+1}{k+1}}}

and its relative

∑r=0m(n+rr)=(n+m+1m).{\displaystyle \sum _{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m+1}{m}}.}

LetF(n) denote then-thFibonacci number.Then

∑k=0⌊n/2⌋(n−kk)=F(n+1).{\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1).}

This can be proved byinduction using (3) or byZeckendorf's representation. A combinatorial proof is given below.

Multisections of sums

[edit]

For integerss andt such that0≤t<s,{\displaystyle 0\leq t<s,}series multisection gives the following identity for the sum of binomial coefficients:

(nt)+(nt+s)+(nt+2s)+…=1s∑j=0s−1(2cos⁡πjs)ncos⁡π(n−2t)js.{\displaystyle {\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}}.}

For smalls, these series have particularly nice forms; for example,[8]

(n0)+(n3)+(n6)+⋯=13(2n+2cos⁡nπ3){\displaystyle {\binom {n}{0}}+{\binom {n}{3}}+{\binom {n}{6}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {n\pi }{3}}\right)}
(n1)+(n4)+(n7)+⋯=13(2n+2cos⁡(n−2)π3){\displaystyle {\binom {n}{1}}+{\binom {n}{4}}+{\binom {n}{7}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-2)\pi }{3}}\right)}
(n2)+(n5)+(n8)+⋯=13(2n+2cos⁡(n−4)π3){\displaystyle {\binom {n}{2}}+{\binom {n}{5}}+{\binom {n}{8}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-4)\pi }{3}}\right)}
(n0)+(n4)+(n8)+⋯=12(2n−1+2n2cos⁡nπ4){\displaystyle {\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)}
(n1)+(n5)+(n9)+⋯=12(2n−1+2n2sin⁡nπ4){\displaystyle {\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)}
(n2)+(n6)+(n10)+⋯=12(2n−1−2n2cos⁡nπ4){\displaystyle {\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)}
(n3)+(n7)+(n11)+⋯=12(2n−1−2n2sin⁡nπ4){\displaystyle {\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

[edit]

Although there is noclosed formula forpartial sums

∑j=0k(nj){\displaystyle \sum _{j=0}^{k}{\binom {n}{j}}}

of binomial coefficients,[9] one can again use (3) and induction to show that fork = 0, …,n − 1,

∑j=0k(−1)j(nj)=(−1)k(n−1k),{\displaystyle \sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}},}

with special case[10]

∑j=0n(−1)j(nj)=0{\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0}

forn > 0. This latter result is also a special case of the result from the theory offinite differences that for any polynomialP(x) of degree less thann,[11]

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

Differentiating (2)k times and settingx = −1 yields this forP(x)=x(x−1)⋯(x−k+1){\displaystyle P(x)=x(x-1)\cdots (x-k+1)},when 0 ≤k <n,and the general case follows by taking linear combinations of these.

WhenP(x) is of degree less than or equal ton,

∑j=0n(−1)j(nj)P(n−j)=n!an{\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(n-j)=n!a_{n}}10

wherean{\displaystyle a_{n}} is the coefficient of degreen inP(x).

More generally for (10),

∑j=0n(−1)j(nj)P(m+(n−j)d)=dnn!an{\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(m+(n-j)d)=d^{n}n!a_{n}}

wherem andd are complex numbers. This follows immediately applying (10) to the polynomial⁠Q(x):=P(m+dx){\displaystyle Q(x):=P(m+dx)}⁠ instead of⁠P(x){\displaystyle P(x)}⁠, and observing that⁠Q(x){\displaystyle Q(x)}⁠ still has degree less than or equal ton, and that its coefficient of degreen isdnan.

Theseriesk−1k∑j=0∞1(j+xk)=1(x−1k−1){\textstyle {\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}} is convergent fork ≥ 2. This formula is used in the analysis of theGerman tank problem. It follows fromk−1k∑j=0M1(j+xk)=1(x−1k−1)−1(M+xk−1){\textstyle {\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}}}} which is proved byinduction onM.

Identities with combinatorial proofs

[edit]

Many identities involving binomial coefficients can be proved bycombinatorial means. For example, for nonnegative integersn≥q{\displaystyle {n}\geq {q}}, the identity

∑k=qn(nk)(kq)=2n−q(nq){\displaystyle \sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}}

(which reduces to (6) whenq = 1) can be given adouble counting proof, as follows. The left side counts the number of ways of selecting a subset of [n] = {1, 2, ...,n} with at leastq elements, and markingq elements among those selected. The right side counts the same thing, because there are(nq){\displaystyle {\tbinom {n}{q}}} ways of choosing a set ofq elements to mark, and2n−q{\displaystyle 2^{n-q}} to choose which of the remaining elements of [n] also belong to the subset.

In Pascal's identity

(nk)=(n−1k−1)+(n−1k),{\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k},}

both sides count the number ofk-element subsets of [n]: the two terms on the right side group them into those that contain elementn and those that do not.

The identity (8) also has a combinatorial proof. The identity reads

∑k=0n(nk)2=(2nn).{\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.}

Suppose you have2n{\displaystyle 2n} empty squares arranged in a row and you want to mark (select)n of them. There are(2nn){\displaystyle {\tbinom {2n}{n}}} ways to do this. On the other hand, you may select yourn squares by selectingk squares from among the firstn andn−k{\displaystyle n-k} squares from the remainingn squares; anyk from 0 ton will work. This gives

∑k=0n(nk)(nn−k)=(2nn).{\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.}

Now apply (1) to get the result.

If one denotes byF(i) the sequence ofFibonacci numbers, indexed so thatF(0) =F(1) = 1, then the identity∑k=0⌊n2⌋(n−kk)=F(n){\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F(n)}has the following combinatorial proof.[12] One may show byinduction thatF(n) counts the number of ways that an × 1 strip of squares may be covered by2 × 1 and1 × 1 tiles. On the other hand, if such a tiling uses exactlyk of the2 × 1 tiles, then it usesn − 2k of the1 × 1 tiles, and so usesn −k tiles total. There are(n−kk){\displaystyle {\tbinom {n-k}{k}}} ways to order these tiles, and so summing this coefficient over all possible values ofk gives the identity.

Sum of coefficients row

[edit]
See also:Combination § Number of k-combinations for all k

The number ofk-combinations for allk,∑0≤k≤n(nk)=2n{\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}, is the sum of thenth row (counting from 0) of the binomial coefficients. These combinations are enumerated by the 1 digits of the set ofbase 2 numbers counting from 0 to2n−1{\displaystyle 2^{n}-1}, where each digit position is an item from the set ofn.

Dixon's identity

[edit]

Dixon's identity is

∑k=−aa(−1)k(2ak+a)3=(3a)!(a!)3{\displaystyle \sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}}

or, more generally,

∑k=−aa(−1)k(a+ba+k)(b+cb+k)(c+ac+k)=(a+b+c)!a!b!c!,{\displaystyle \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!}}\,,}

wherea,b, andc are non-negative integers.

Continuous identities

[edit]

Certain trigonometric integrals have values expressible in terms of binomial coefficients: For anym,n∈N,{\displaystyle m,n\in \mathbb {N} ,}

∫−ππcos⁡((2m−n)x)cosn⁡(x) dx=π2n−1(nm){\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}(x)\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}}
∫−ππsin⁡((2m−n)x)sinn⁡(x) dx={(−1)m+(n+1)/2π2n−1(nm),n odd0,otherwise{\displaystyle \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}}}
∫−ππcos⁡((2m−n)x)sinn⁡(x) dx={(−1)m+(n/2)π2n−1(nm),n even0,otherwise{\displaystyle \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}}}

These can be proved by usingEuler's formula to converttrigonometric functions to complex exponentials, expanding using the binomial theorem, and integrating term by term.

Congruences

[edit]

Ifn is prime, then(n−1k)≡(−1)kmodn{\displaystyle {\binom {n-1}{k}}\equiv (-1)^{k}\mod n} for everyk with0≤k≤n−1.{\displaystyle 0\leq k\leq n-1.}More generally, this remains true ifn is any number andk is such that all the numbers between 1 andk are coprime ton.

Indeed, we have

(n−1k)=(n−1)(n−2)⋯(n−k)1⋅2⋯k=∏i=1kn−ii≡∏i=1k−ii=(−1)kmodn.{\displaystyle {\binom {n-1}{k}}={(n-1)(n-2)\cdots (n-k) \over 1\cdot 2\cdots k}=\prod _{i=1}^{k}{n-i \over i}\equiv \prod _{i=1}^{k}{-i \over i}=(-1)^{k}\mod n.}

Generating functions

[edit]

Ordinary generating functions

[edit]

For a fixedn, theordinary generating function of the sequence(n0),(n1),(n2),…{\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots } is

∑k=0∞(nk)xk=(1+x)n.{\displaystyle \sum _{k=0}^{\infty }{n \choose k}x^{k}=(1+x)^{n}.}

For a fixedk, the ordinary generating function of the sequence(0k),(1k),(2k),…,{\displaystyle {\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},\ldots ,} is

∑n=0∞(nk)yn=yk(1−y)k+1.{\displaystyle \sum _{n=0}^{\infty }{n \choose k}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}.}

Thebivariate generating function of the binomial coefficients is

∑n=0∞∑k=0n(nk)xkyn=11−y−xy.{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{n \choose k}x^{k}y^{n}={\frac {1}{1-y-xy}}.}

A symmetric bivariate generating function of the binomial coefficients is

∑n=0∞∑k=0∞(n+kk)xkyn=11−x−y.{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}x^{k}y^{n}={\frac {1}{1-x-y}}.}

which is the same as the previous generating function after the substitutionx→xy{\displaystyle x\to xy}.

Exponential generating function

[edit]

A symmetricexponential bivariate generating function of the binomial coefficients is:

∑n=0∞∑k=0∞(n+kk)xkyn(n+k)!=ex+y.{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.}

Divisibility properties

[edit]
Main articles:Kummer's theorem andLucas' theorem

In 1852,Kummer proved that ifm andn are nonnegative integers andp is aprime number, then the largest power ofp dividing(m+nm){\displaystyle {\tbinom {m+n}{m}}} equalspc, wherec is the number of carries whenm andn are added in basep.Equivalently, the exponent of a primep in(nk){\displaystyle {\tbinom {n}{k}}}equals the number of nonnegative integersj such that thefractional part ofk/pj is greater than the fractional part ofn/pj. (For example,(nk){\displaystyle {\tbinom {n}{k}}} is not divisible byp if every digit in the base-p representation ofk is less than or equal to the corresponding digit in the base-p representation ofn.) It can be deduced from this that(nk){\displaystyle {\tbinom {n}{k}}} is divisible byn/gcd(n,k). In particular therefore it follows thatp divides(prs){\displaystyle {\tbinom {p^{r}}{s}}} for all positive integersr ands such thats <pr. However this is not true of higher powers ofp: for example 9 does not divide(96){\displaystyle {\tbinom {9}{6}}}.

Any integer dividesalmost all binomial coefficients.[13] More precisely, fix an integerd and letf(N) denote the number of binomial coefficients(nk){\displaystyle {\tbinom {n}{k}}} withn<N{\displaystyle n<N} such thatd divides(nk){\displaystyle {\tbinom {n}{k}}}. Then

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

Since the number of binomial coefficients(nk){\displaystyle {\tbinom {n}{k}}} withn <N isN(N + 1) / 2, this implies that the density of binomial coefficients divisible byd goes to 1.

Binomial coefficients have divisibility properties related to least common multiples of consecutive integers. For example:[14]

(n+kk){\displaystyle {\binom {n+k}{k}}} divideslcm⁡(n,n+1,…,n+k)n{\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n}}}.
(n+kk){\displaystyle {\binom {n+k}{k}}} is a multiple oflcm⁡(n,n+1,…,n+k)n⋅lcm⁡((k0),(k1),…,(kk)){\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n\cdot \operatorname {lcm} ({\binom {k}{0}},{\binom {k}{1}},\ldots ,{\binom {k}{k}})}}}.

Another fact:An integern ≥ 2 is prime if and only ifall the intermediate binomial coefficients

(n1),(n2),…,(nn−1){\displaystyle {\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}}

are divisible byn.

Proof:Whenp is prime,p divides

(pk)=p⋅(p−1)⋯(p−k+1)k⋅(k−1)⋯1{\displaystyle {\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}} for all0 <k <p

because(pk){\displaystyle {\tbinom {p}{k}}} is a natural number andp divides the numerator but not the denominator.Whenn is composite, letp be the smallest prime factor ofn and letk =n/p. Then0 <p <n and

(np)=n(n−1)(n−2)⋯(n−p+1)p!=k(n−1)(n−2)⋯(n−p+1)(p−1)!≢0(modn){\displaystyle {\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}}}

otherwise the numeratork(n − 1)(n − 2)⋯(n −p + 1) has to be divisible byn =k×p, this can only be the case when(n − 1)(n − 2)⋯(n −p + 1) is divisible byp. Butn is divisible byp, sop does not dividen − 1,n − 2, …,n −p + 1 and becausep is prime, we know thatp does not divide(n − 1)(n − 2)⋯(n −p + 1) and so the numerator cannot be divisible byn.

Bounds and asymptotic formulas

[edit]

The following bounds for(nk){\displaystyle {\tbinom {n}{k}}} hold for all values ofn andk such that1 ≤k ≤n:nkkk≤(nk)≤nkk!<(n⋅ek)k.{\displaystyle {\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}.}The first inequality follows from the fact that(nk)=nk⋅n−1k−1⋯n−(k−1)1{\displaystyle {n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}}and each of thesek{\displaystyle k} terms in this product is≥nk{\textstyle \geq {\frac {n}{k}}}. A similar argument can be made to show the second inequality. The final strict inequality is equivalent toek>kk/k!{\textstyle e^{k}>k^{k}/k!}, that is clear since the RHS is a term of the exponential seriesek=∑j=0∞kj/j!{\textstyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}.

From the divisibility properties we can infer thatlcm⁡(n−k,…,n)(n−k)⋅lcm⁡((k0),…,(kk))≤(nk)≤lcm⁡(n−k,…,n)n−k,{\displaystyle {\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}},}where both equalities can be achieved.[14]

The following bounds are useful in information theory:[15]: 353 1n+12nH(k/n)≤(nk)≤2nH(k/n){\displaystyle {\frac {1}{n+1}}2^{nH(k/n)}\leq {n \choose k}\leq 2^{nH(k/n)}}whereH(p)=−plog2⁡(p)−(1−p)log2⁡(1−p){\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)} is thebinary entropy function. It can be further tightened ton8k(n−k)2nH(k/n)≤(nk)≤n2πk(n−k)2nH(k/n){\displaystyle {\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)}}for all1≤k≤n−1{\displaystyle 1\leq k\leq n-1}.[16]: 309 

Bothn andk large

[edit]

Stirling's approximation yields the following approximation, valid whenn−k,k{\displaystyle n-k,k} both tend to infinity:(nk)∼n2πk(n−k)⋅nnkk(n−k)n−k{\displaystyle {n \choose k}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}}Because the inequality forms of Stirling's formula also bound the factorials, slight variants on the above asymptotic approximation give exact bounds.In particular, whenn{\displaystyle n} is sufficiently large, one has(2nn)∼22nnπ{\displaystyle {2n \choose n}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}} andn(2nn)≥22n−1{\displaystyle {\sqrt {n}}{2n \choose n}\geq 2^{2n-1}}. More generally, form ≥ 2 andn ≥ 1 (again, by applying Stirling's formula to the factorials in the binomial coefficient),n(mnn)≥mm(n−1)+1(m−1)(m−1)(n−1).{\displaystyle {\sqrt {n}}{mn \choose n}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}.}

Ifn is large andk is linear inn, various precise asymptotic estimates exist for the binomial coefficient(nk){\textstyle {\binom {n}{k}}}. For example, if|n/2−k|=o(n2/3){\displaystyle |n/2-k|=o(n^{2/3})} then(nk)∼(nn2)e−d2/(2n)∼2n12nπe−d2/(2n){\displaystyle {\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)}}whered =n − 2k.[17]

n much larger thank

[edit]

Ifn is large andk iso(n) (that is, ifk/n → 0), then(nk)∼(nek)k⋅(2πk)−1/2⋅exp⁡(−k22n(1+o(1))){\displaystyle {\binom {n}{k}}\sim \left({\frac {ne}{k}}\right)^{k}\cdot (2\pi k)^{-1/2}\cdot \exp \left(-{\frac {k^{2}}{2n}}(1+o(1))\right)}where againo is thelittle o notation.[18]

Sums of binomial coefficients

[edit]

A simple and rough upper bound for the sum of binomial coefficients can be obtained using thebinomial theorem:∑i=0k(ni)≤∑i=0kni⋅1k−i≤(1+n)k{\displaystyle \sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}}More precise bounds are given by18nε(1−ε)⋅2H(ε)⋅n≤∑i=0k(ni)≤2H(ε)⋅n,{\displaystyle {\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},}valid for all integersn>k≥1{\displaystyle n>k\geq 1} withε≐k/n≤1/2{\displaystyle \varepsilon \doteq k/n\leq 1/2}.[19]

Generalized binomial coefficients

[edit]

Theinfinite product formula for the gamma function also gives an expression for binomial coefficients(−1)k(zk)=(−z+k−1k)=1Γ(−z)1(k+1)z+1∏j=k+1(1+1j)−z−11−z+1j{\displaystyle (-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 {\left(1+{\frac {1}{j}}\right)^{-z-1}}{1-{\frac {z+1}{j}}}}}which yields the asymptotic formulas(zk)≈(−1)kΓ(−z)kz+1and(z+kk)=kzΓ(z+1)(1+z(z+1)2k+O(k−2)){\displaystyle {z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad {\text{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)}ask→∞{\displaystyle k\to \infty }.

This asymptotic behaviour is contained in the approximation(z+kk)≈ez(Hk−γ)Γ(z+1){\displaystyle {z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}as well. (HereHk{\displaystyle H_{k}} is thek-thharmonic number andγ{\displaystyle \gamma } is theEuler–Mascheroni constant.)

Further, the asymptotic formula(z+kj)(kj)→(1−jk)−zand(jj−k)(j−zj−k)→(jk)z{\displaystyle {\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}}hold true, wheneverk→∞{\displaystyle k\to \infty } andj/k→x{\displaystyle j/k\to x} for some complex numberx{\displaystyle x}.

Generalizations

[edit]

Generalization to multinomials

[edit]
Main article:Multinomial theorem

Binomial coefficients can be generalized tomultinomial coefficients defined to be the number:

(nk1,k2,…,kr)=n!k1!k2!⋯kr!{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}}

where

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

While the binomial coefficients represent the coefficients of(x +y)n, the multinomial coefficientsrepresent the coefficients of the polynomial

(x1+x2+⋯+xr)n.{\displaystyle (x_{1}+x_{2}+\cdots +x_{r})^{n}.}

The caser = 2 gives binomial coefficients:

(nk1,k2)=(nk1,n−k1)=(nk1)=(nk2).{\displaystyle {n \choose k_{1},k_{2}}={n \choose k_{1},n-k_{1}}={n \choose k_{1}}={n \choose k_{2}}.}

The combinatorial interpretation of multinomial coefficients is distribution ofn distinguishable elements overr (distinguishable) containers, each containing exactlyki elements, wherei is the index of the container.

Multinomial coefficients have many properties similar to those of binomial coefficients, for example the recurrence relation:

(nk1,k2,…,kr)=(n−1k1−1,k2,…,kr)+(n−1k1,k2−1,…,kr)+…+(n−1k1,k2,…,kr−1){\displaystyle {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}}

and symmetry:

(nk1,k2,…,kr)=(nkσ1,kσ2,…,kσr){\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={n \choose k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}}

where(σi){\displaystyle (\sigma _{i})} is apermutation of (1, 2, ...,r).

Taylor series

[edit]

UsingStirling numbers of the first kind theseries expansion around any arbitrarily chosen pointz0{\displaystyle z_{0}} is

(zk)=1k!∑i=0kzisk,i=∑i=0k(z−z0)i∑j=ik(z0j−i)sk+i−j,i(k+i−j)!=∑i=0k(z−z0)i∑j=ikz0j−i(ji)sk,jk!.{\displaystyle {\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 withn = 1/2

[edit]

The definition of the binomial coefficients can be extended to the case wheren{\displaystyle n} is real andk{\displaystyle k} is integer.

In particular, the following identity holds for any non-negative integerk{\displaystyle k}:

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

This shows up when expanding1+x{\displaystyle {\sqrt {1+x}}} into a power series using the Newton binomial series :

1+x=∑k≥0(1/2k)xk.{\displaystyle {\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}.}

Products of binomial coefficients

[edit]

One can express the product of two binomial coefficients as a linear combination of binomial coefficients:

(zm)(zn)=∑k=0min(m,n)(m+n−kk,m−k,n−k)(zm+n−k),{\displaystyle {z \choose m}{z \choose n}=\sum _{k=0}^{\min(m,n)}{m+n-k \choose k,m-k,n-k}{z \choose m+n-k},}

where the connection coefficients aremultinomial coefficients. In terms of labelled combinatorial objects, the connection coefficients represent the number of ways to assignm +n −k labels to a pair of labelled combinatorial objects—of weightm andn respectively—that have had their firstk labels identified, or glued together to get a new labelled combinatorial object of weightm +n −k. (That is, to separate the labels into three portions to apply to the glued part, the unglued part of the first object, and the unglued part of the second object.) In this regard, binomial coefficients are to exponential generating series whatfalling factorials are to ordinary generating series.

The product of all binomial coefficients in thenth row of the Pascal triangle is given by the formula:

∏k=0n(nk)=∏k=1nk2k−n−1.{\displaystyle \prod _{k=0}^{n}{\binom {n}{k}}=\prod _{k=1}^{n}k^{2k-n-1}.}

Partial fraction decomposition

[edit]

Thepartial fraction decomposition of the reciprocal is given by

1(zn)=∑i=0n−1(−1)n−1−i(ni)n−iz−i,1(z+nn)=∑i=1n(−1)i−1(ni)iz+i.{\displaystyle {\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

[edit]
Main article:Binomial series

Newton's binomial series, named afterSir Isaac Newton, is a generalization of the binomial theorem to infinite series:

(1+z)α=∑n=0∞(αn)zn=1+(α1)z+(α2)z2+⋯.{\displaystyle (1+z)^{\alpha }=\sum _{n=0}^{\infty }{\alpha \choose n}z^{n}=1+{\alpha \choose 1}z+{\alpha \choose 2}z^{2}+\cdots .}

The identity can be obtained by showing that both sides satisfy thedifferential equation(1 +z)f'(z) =αf(z).

Theradius of convergence of this series is 1. An alternative expression is

1(1−z)α+1=∑n=0∞(n+αn)zn{\displaystyle {\frac {1}{(1-z)^{\alpha +1}}}=\sum _{n=0}^{\infty }{n+\alpha \choose n}z^{n}}

where the identity

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

is applied.

Multiset (rising) binomial coefficient

[edit]
Main article:Multichoose § Counting multisets

Binomial coefficients count subsets of prescribed size from a given set. A related combinatorial problem is to countmultisets of prescribed size with elements drawn from a given set, that is, to count the number of ways to select a certain number of elements from a given set with the possibility of selecting the same element repeatedly. The resulting numbers are calledmultiset coefficients;[20] the number of ways to "multichoose" (i.e., choose with replacement)k items from ann element set is denoted((nk)){\textstyle \left(\!\!{\binom {n}{k}}\!\!\right)}.

To avoid ambiguity and confusion withn's main denotation in this article,
letf =n =r + (k − 1) andr =f − (k − 1).

Multiset coefficients may be expressed in terms of binomial coefficients by the rule(fk)=((rk))=(r+k−1k).{\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.}One possible alternative characterization of this identity is as follows:We may define thefalling factorial as(f)k=fk_=(f−k+1)⋯(f−3)⋅(f−2)⋅(f−1)⋅f,{\displaystyle (f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,}and the corresponding rising factorial asr(k)=rk¯=r⋅(r+1)⋅(r+2)⋅(r+3)⋯(r+k−1);{\displaystyle r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1);}so, for example,17⋅18⋅19⋅20⋅21=(21)5=215_=175¯=17(5).{\displaystyle 17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}.}Then the binomial coefficients may be written as(fk)=(f)kk!=(f−k+1)⋯(f−2)⋅(f−1)⋅f1⋅2⋅3⋅4⋅5⋯k,{\displaystyle {\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}},}while the corresponding multiset coefficient is defined by replacing the falling with the rising factorial:((rk))=r(k)k!=r⋅(r+1)⋅(r+2)⋯(r+k−1)1⋅2⋅3⋅4⋅5⋯k.{\displaystyle \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 integersn

[edit]
Binomial coefficientsC (n,k) extended for negative and fractionaln, illustrated with a simplebinomial. It can be observed thatPascal's triangle is rotated and alternate terms are negated.The casen = −1 givesGrandi's series.

For anyn,

(−nk)=−n⋅−(n+1)⋯−(n+k−2)⋅−(n+k−1)k!=(−1)kn⋅(n+1)⋅(n+2)⋯(n+k−1)k!=(−1)k(n+k−1k)=(−1)k((nk)).{\displaystyle {\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}}}

In particular, binomial coefficients evaluated at negative integersn are given by signed multiset coefficients. In the special casen=−1{\displaystyle n=-1}, this reduces to(−1)k=(−1k)=((−kk)).{\displaystyle (-1)^{k}={\binom {-1}{k}}=\left(\!\!{\binom {-k}{k}}\!\!\right).}

For example, ifn = −4 andk = 7, thenr = 4 andf = 10:

(−47)=−10⋅−9⋅−8⋅−7⋅−6⋅−5⋅−41⋅2⋅3⋅4⋅5⋅6⋅7=(−1)74⋅5⋅6⋅7⋅8⋅9⋅101⋅2⋅3⋅4⋅5⋅6⋅7=((−77))((47))=(−17)(107).{\displaystyle {\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

[edit]

The binomial coefficient is generalized to two real or complex valued arguments using thegamma function orbeta function via

(xy)=Γ(x+1)Γ(y+1)Γ(x−y+1)=1(x+1)B(y+1,x−y+1).{\displaystyle {x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (y+1,x-y+1)}}.}

This definition inherits these following additional properties fromΓ{\displaystyle \Gamma }:

(xy)=sin⁡(yπ)sin⁡(xπ)(−y−1−x−1)=sin⁡((x−y)π)sin⁡(xπ)(y−x−1y);{\displaystyle {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};}

moreover,

(xy)⋅(yx)=sin⁡((x−y)π)(x−y)π.{\displaystyle {x \choose y}\cdot {y \choose x}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}.}

The resulting function has been little-studied, apparently first being graphed in (Fowler 1996). Notably, many binomial identities fail:(nm)=(nn−m){\textstyle {\binom {n}{m}}={\binom {n}{n-m}}} but(−nm)≠(−n−n−m){\textstyle {\binom {-n}{m}}\neq {\binom {-n}{-n-m}}} forn positive (so−n{\displaystyle -n} negative). The behavior is quite complex, and markedly different in various octants (that is, with respect to thex andy axes and the liney=x{\displaystyle y=x}), with the behavior for negativex having singularities at negative integer values and a checkerboard of positive and negative regions:

Generalization toq-series

[edit]

The binomial coefficient has aq-analog generalization known as theGaussian binomial coefficient. These coefficients are polynomials in anindeterminate (traditionally denotedq) and have applications to many enumerative problems in combinatorics, such as counting the number oflinear subspaces of avector space over afinite field and counting the number of subsets of {1, 2, ...,n} with certain symmetries (an instance of thecyclic sieving phenomenon).

Generalization to infinite cardinals

[edit]

The definition of the binomial coefficient can be generalized toinfinite cardinals by defining:

(αβ)=|{B⊆A:|B|=β}|{\displaystyle {\alpha \choose \beta }=\left|\left\{B\subseteq A:\left|B\right|=\beta \right\}\right|}

whereA is some set withcardinalityα{\displaystyle \alpha }. One can show that the generalized binomial coefficient is well-defined, in the sense that no matter what set we choose to represent thecardinal numberα{\displaystyle \alpha },(αβ){\textstyle {\alpha \choose \beta }} will remain the same. For finite cardinals, this definition coincides with the standard definition of the binomial coefficient.

Assuming theAxiom of Choice, one can show that(αα)=2α{\textstyle {\alpha \choose \alpha }=2^{\alpha }} for any infinite cardinalα{\displaystyle \alpha }.

See also

[edit]

Notes

[edit]
  1. ^Higham (1998)
  2. ^Lilavati Section 6, Chapter 4 (seeKnuth (1997)).
  3. ^Uspensky 1937, p. 18
  4. ^See (Graham, Knuth & Patashnik 1994), which also defines(nk)=0{\displaystyle {\tbinom {n}{k}}=0} fork<0{\displaystyle k<0}. Alternative generalizations, such as totwo real or complex valued arguments using theGamma function assign nonzero values to(nk){\displaystyle {\tbinom {n}{k}}} fork<0{\displaystyle 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 evenPascal's identity to fail (at the origin).
  5. ^Whenα=n{\displaystyle \alpha =n} is a nonnegative integer,(nk)=0{\displaystyle \textstyle {\binom {n}{k}}=0} fork>n{\displaystyle k>n} because the(k=n+1){\displaystyle (k=n+1)}-th factor of the numerator isn−(n+1)+1=0{\displaystyle n-(n+1)+1=0}. Thus, thek{\displaystyle k}-th term is azero product for allk≥n+1{\displaystyle k\geq n+1}.
  6. ^Muir, Thomas (1902)."Note on Selected Combinations".Proceedings of the Royal Society of Edinburgh.
  7. ^This can be seen as a discrete analog ofTaylor's theorem. It is closely related toNewton's polynomial. Alternating sums of this form may be expressed as theNörlund–Rice integral.
  8. ^Gradshteyn & Ryzhik (2014, pp. 3–4).
  9. ^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.
  10. ^see induction developed in eq (7) p. 1389 inAupetit, 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.
  11. ^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.S2CID 125556648.
  12. ^Benjamin & Quinn 2003, pp. 4−5
  13. ^David Singmaster (1974)
  14. ^abFarhi, Bakir (2007). "Nontrivial lower bounds for the least common multiple of some finite sequence of integers".Journal of Number Theory.125 (2):393–411.arXiv:0803.0290.doi:10.1016/j.jnt.2006.10.017.S2CID 115167580.
  15. ^Thomas M. Cover; Joy A. Thomas (18 July 2006).Elements of Information Theory. Hoboken, New Jersey: Wiley.ISBN 0-471-24195-4.
  16. ^F. J. MacWilliams; N. J. A. Sloane (1981).The Theory of Error-Correcting Codes. Vol. 16 (3rd ed.). North-Holland.ISBN 0-444-85009-0.
  17. ^Spencer, Joel; Florescu, Laura (2014).Asymptopia. Student mathematical library. Vol. 71.AMS. p. 66.ISBN 978-1-4704-0904-3.OCLC 865574788.
  18. ^Spencer, Joel; Florescu, Laura (2014).Asymptopia. Student mathematical library. Vol. 71.AMS. p. 59.ISBN 978-1-4704-0904-3.OCLC 865574788.
  19. ^see e.g.Ash (1990, p. 121) orFlum & Grohe (2006, p. 427).
  20. ^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.

References

[edit]

External links

[edit]

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

Core
Combinatorics basics
Identities, numbers, sequences
Multinomial generalizations
Distributions
Special functions (connections)
Factorials & approximations
Structures & arrays
Operators & calculus links
Theorems & results
Methods & integrals
Retrieved from "https://en.wikipedia.org/w/index.php?title=Binomial_coefficient&oldid=1316791603"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp