Binomial coefficient

From Wikipedia, the free encyclopedia

Categories: Combinatorics | Factorial and binomial topics | Integer sequences | Triangles of numbers

In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+y)ⁿ. Colloquially given, say there are n pizza toppings to select from, if one wishes to bake a pizza with exactly k toppings, then the binomial coefficient expresses how many different types of such k-topping pizzas are possible.

Definition

Given a non-negative integer n and an integer k, the binomial coefficient is defined to be the natural number

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)} {k \cdot (k-1) \cdots 1} = \frac{n!}{k!(n-k)!} \quad \mbox{if}\ n\geq k\geq 0 \qquad (1)

and

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} = 0 \quad \mbox{if } k<0 \mbox{ or } k>n

where n! denotes the factorial of n.

According to Nicholas J. Higham, the Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k}

notation was introduced by Albert von Ettinghausen in 1826, although these numbers were already known centuries before that (see Pascal's triangle). Alternative notations include C(n, k), _nC_k or Failed to parse (Missing texvc executable; please see math/README to configure.): C^{k}_{n}

, in all of which the C stands for combination or choose. Indeed, another name for the binomial coefficient is choose function, and the binomial coefficient of n and k is often read as "n choose k".

The binomial coefficients are the coefficients in the expansion of the binomial (x + y)ⁿ (hence the name):

Failed to parse (Missing texvc executable; please see math/README to configure.): (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k. \qquad (2)

This is generalized by the binomial theorem, which allows the exponent n to be negative or a non-integer. See the article on combination.

Combinatorial interpretation

The importance of the binomial coefficients (and the motivation for the alternate name 'choose') lies in the fact that Failed to parse (Missing texvc executable; please see math/README to configure.): {\tbinom n k}

is the number of ways that k objects can be chosen from among n objects, regardless of order. More formally,

Failed to parse (Missing texvc executable; please see math/README to configure.): {\tbinom n k}

is the number of k-element subsets of an n-element set. Failed to parse (Missing texvc executable; please see math/README to configure.): \qquad (1a)

In fact, this property is often chosen as an alternative definition of the binomial coefficient, since from (1a) one may derive (1) as a corollary by a straightforward combinatorial proof. For a colloquial demonstration, note that in the formula

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1},

the numerator gives the number of ways to fill the k slots using the n options, where the slots are distinguishable from one another. Thus a pizza with mushrooms added before chicken is considered to be different from a pizza with chicken added before mushrooms. The denominator eliminates these repetitions because if the k slots are indistinguishable, then all of the k! ways of arranging them are considered identical.

On the context of computer science, it also helps to see Failed to parse (Missing texvc executable; please see math/README to configure.): {\tbinom n k}

as the number of strings consisting of ones and zeros with k ones and n−k zeros. For each k-element subset, K, of an n-element set, N, the indicator function, 1_K : N->{0,1}, where 1_K(x) = 1 whenever x in K and 0 otherwise, produces a unique bit string of length n with exactly k ones by feeding 1_K with the n elements in a specific order.^[1]

Example

Failed to parse (Missing texvc executable; please see math/README to configure.): {7 \choose 3} = \frac{7!}{3!(7-3)!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(3 \cdot 2 \cdot 1)(4 \cdot 3 \cdot 2 \cdot 1)} = \frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35.






The calculation of the binomial coefficient is conveniently arranged like this: ((((5/1)·6)/2)·7)/3, alternately dividing and multiplying with increasing integers. Each division produces an integer result which is itself a binomial coefficient.

Derivation from binomial expansion




For exponent 1, (x+y)¹ is x+y. For exponent 2, (x+y)² is (x+y)(x+y), which forms terms as follows. The first factor supplies either an x or a y; likewise for the second factor. Thus to form x², the only possibility is to choose x from both factors; likewise for y². However, the xy term can be formed by x from the first and y from the second factor, or y from the first and x from the second factor; thus it acquires a coefficient of 2. Proceeding to exponent 3, (x+y)³ reduces to (x+y)²(x+y), where we already know that (x+y)²= x²+2xy+y², giving an initial expansion of (x+y)(x²+2xy+y²). Again the extremes, x³ and y³ arise in a unique way. However, the x²y term is either 2xy times x or x² times y, for a coefficient of 3; likewise xy² arises in two ways, summing the coefficients 1 and 2 to give 3.


This suggests an induction. Thus for exponent n, each term has total degree (sum of exponents) n, with n−k factors of x and k factors of y.  If k is 0 or n, the term arises in only one way, and we get the terms xⁿ and yⁿ.  If k is neither 0 nor n, then the term arises in two ways, from x^n-k-1y^k × x and from x^n-ky^k-1 × y. For example, x²y² is both xy² times x and x²y times y, thus its coefficient is 3 (the coefficient of xy²) + 3 (the coefficient of x²y). This is the origin of Pascal's triangle, discussed below.


Another perspective is that to form x^n−ky^k from n factors of (x+y), we must choose y from k of the factors and x from the rest. To count the possibilities, consider all n! permutations of the factors. Represent each permutation as a shuffled list of the numbers from 1 to n. Select an x from the first n−k factors listed, and a y from the remaining k factors; in this way each permutation contributes to the term x^n−ky^k. For example, the list 〈4,1,2,3〉 selects x from factors 4 and 1, and selects y from factors 2 and 3, as one way to form the term x²y².

(x +¹ y)(x +² y)(x +³ y)(x +⁴ y)




But the distinct list 〈1,4,3,2〉 makes exactly the same selection; the binomial coefficient formula must remove this redundancy. The n−k factors for x have (n−k)! permutations, and the k factors for y have k! permutations. Therefore n!/(n−k)!k! is the number of truly distinct ways to form the term x^n−ky^k.


A simpler explanation follows:
One can pick a random element out of Failed to parse (Missing texvc executable; please see math/README to configure.): n

in exactly




Failed to parse (Missing texvc executable; please see math/README to configure.): n

ways, a second random element in Failed to parse (Missing texvc executable; please see math/README to configure.):  (n-1)
ways, and so forth. Thus, Failed to parse (Missing texvc executable; please see math/README to configure.): k
elements can be picked out of n in Failed to parse (Missing texvc executable; please see math/README to configure.):  n\cdot (n-1) \cdot \ldots \cdot (n-k+1)




ways. In this calculation, however, each order-independent selection occurs Failed to parse (Missing texvc executable; please see math/README to configure.): k!

times, as a list of Failed to parse (Missing texvc executable; please see math/README to configure.): k
elements can be permuted in so many ways. Thus eq. (1) is obtained.

Pascal's triangle




Pascal's rule is the important recurrence relation

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} + {n \choose k+1} = {n+1 \choose k+1}, \qquad (3)




which follows directly from the definition:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{align} {n \choose k} + {n \choose k+1} &{}= \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-(k+1))!} \\ &{} = \left(\frac{n!(k+1)}{k!(n-k)!(k+1)} + \frac{n!(n-k)}{(k+1)!(n-(k+1))!(n-k)}\right)\\ &{} = \left(\frac{n!(k+1 + n-k)}{(k+1)!(n-k)!}\right) \\ &{} = \frac{(n+1)!}{(k+1)!((n+1)-(k+1))!} \\ &{} = {n+1 \choose k+1} \end{align}






The recurrence relation just proved can be used to prove by mathematical induction that C(n, k) is a natural number for all n and k, a fact that is not immediately obvious from the definition.


Pascal's rule also gives rise to 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




Row number n contains the numbers C(n, k) for k = 0,…,n. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath. 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)⁵ = 1 x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1 y⁵.




The differences between elements on other diagonals are the elements in the previous diagonal, as a consequence of the recurrence relation (3) above.


In the 1303 AD treatise Precious Mirror of the Four Elements, Zhu Shijie mentioned the triangle as an ancient method for evaluating binomial coefficients indicating that the method was known to Chinese mathematicians five centuries before Pascal.

Combinatorics and statistics




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

Every set with n elements has Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{C}(n, k)

different subsets having k elements each (these are called k-combinations).

The number of strings of length n containing k ones and n − k zeros is Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{C}(n, k).

There are Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{C}(n+1, k)

strings consisting of k ones and n zeros such that no two ones are adjacent.

The number of sequences consisting of n natural numbers whose sum equals k is Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{C}(n+k-1, k)

this is also the number of ways to choose k elements from a set of n if repetitions are allowed.

The Catalan numbers have an easy formula involving binomial coefficients; they can be used to count various structures, such as trees and parenthesized expressions.




The binomial coefficients also occur in the formula for the binomial distribution in statistics and in the formula for a Bézier curve.

Formulas involving binomial coefficients




One has that

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k}= {n \choose n-k},\qquad\qquad(4)






This follows immediately from the definition or can be seen from expansion (2) by using (x + y)ⁿ = (y + x)ⁿ, and is reflected in the numerical "symmetry" of Pascal's triangle.


Another formula is

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{k=0}^{n} {n \choose k} = 2^n, \qquad\qquad(5)






it is obtained from expansion (2) using x = y = 1.  This is equivalent to saying that the elements in one row of Pascal's triangle always add up to two raised to an integer power. A combinatorial proof of this fact is given by counting subsets of size 0, size 1, size 2, and so on up to size n of a set S of n elements. Since we count the number of subsets of size i for 0 ≤ i ≤ n, this sum must be equal to the number of subsets of S, which is known to be 2ⁿ.


The formula

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{k=1}^{n} {k} {n \choose k} = {n} 2^{n-1} \qquad(6)




follows from expansion (2), after differentiating with respect to either x or y and then substituting x = y = 1.


Vandermonde's identity

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{j} {m\choose j} {{n-m} \choose {k-j}} = {n \choose k} \qquad (7a)




is found by expanding (1+x)^m (1+x)^n-m = (1+x)ⁿ with (2). As C(n, k) is zero if k > n, the sum is finite for integer n and m. Equation (7a) generalizes equation (3).  It holds for arbitrary, complex-valued Failed to parse (Missing texvc executable; please see math/README to configure.): m

and Failed to parse (Missing texvc executable; please see math/README to configure.): n




, the Chu-Vandermonde identity.


A related formula is

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{m} {m\choose j} {n-m\choose k-j}= {n+1\choose k+1}. \qquad (7b)






While equation (7a) is true for all values of m, equation (7b) is true for all values of j.


From expansion (7a) using n=2m, k = m, and (4), one finds

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{j=0}^{m} {m \choose j}^2 = {{2m} \choose m}. \qquad (8)






Denote by F(n + 1) the Fibonacci numbers. We obtain a formula about the diagonals of Pascal's triangle

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{k=0}^{n} {{n-k} \choose k} = \mathrm{F}(n+1). \qquad (9)






This can be proved by induction using (3).


Also using (3) and induction, one can show that

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{j=k}^{n} {j \choose k} = {{n+1} \choose {k+1}}. \qquad (10)






Again by (3) and induction, one can show that for k = 0, ... , n - 1

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{j=0}^{k} (-1)^j{n \choose j} = (-1)^k{{n-1} \choose k} \qquad(11)






as well as

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{j=0}^{n} (-1)^j{n \choose j} = 0 \qquad(12)






which is itself a special case of the result that for any integer a = 1, ..., n - 1,

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{j=0}^{n} (-1)^j{n \choose j}j^a = 0.






which can be shown by differentiating (2) a times and setting x=-1 and y=1.

Combinatorial identities involving binomial coefficients




We present some identities that have combinatorial proofs. We have, for example,

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{k=q}^{n} {n \choose k}{k \choose q} = 2^{n-q} {n \choose q}.\qquad(13)






for Failed to parse (Missing texvc executable; please see math/README to configure.): {n} \geq {q}.

The combinatorial proof goes as follows: the left side counts the number of ways of selecting a subset of Failed to parse (Missing texvc executable; please see math/README to configure.): [n]
of at least q elements, and marking q elements among those selected. The right side counts the same parameter, because there are Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{C}(n, q)
ways of choosing a set of q marks and they occur in all subsets that additionally contain some subset of the remaining elements, of which there are Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{n-q}.
This reduces to (6) when Failed to parse (Missing texvc executable; please see math/README to configure.): q=1.






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

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{k=0}^n {n\choose k}^2 = {2n\choose n}.






Suppose you have Failed to parse (Missing texvc executable; please see math/README to configure.): 2n

empty squares arranged in a row and you want to mark (select) n of them. There are Failed to parse (Missing texvc executable; please see math/README to configure.): C(2n, n)
ways to do this. On the other hand, you may select your n squares by selecting k squares from among the first n and Failed to parse (Missing texvc executable; please see math/README to configure.): n-k
squares from the remaining n squares. This gives

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{k=0}^{n} {n \choose k} {n \choose n-k} = {{2n} \choose n}.




Now apply (4) to get the result.

Generating functions




If we didn't know about binomial coefficients we could derive them using the labelled case of the Fundamental Theorem of Combinatorial Enumeration. This is done by defining Failed to parse (Missing texvc executable; please see math/README to configure.): C(n, k)

to be the number of ways of partitioning Failed to parse (Missing texvc executable; please see math/README to configure.): [n]
into two subsets, the first of which has size k. These partitions form a combinatorial class with the specification

Failed to parse (Missing texvc executable; please see math/README to configure.): \mathfrak{S}_2(\mathfrak{P}(\mathcal{Z})) = \mathfrak{P}(\mathcal{Z}) \mathfrak{P}(\mathcal{Z}).






Hence the exponential generating function B of the sum function of the binomial coefficients is given by

Failed to parse (Missing texvc executable; please see math/README to configure.): B(z) = \exp{z} \exp{z} = \exp(2z)\,.






This immediately yields

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{k=0}^{n} {n \choose k} = n! [z^n] \exp (2z) = 2^n,






as expected. We mark the first subset with Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{U}

in order to obtain the binomial coefficients themselves, giving

Failed to parse (Missing texvc executable; please see math/README to configure.): \mathfrak{P}(\mathcal{U} \; \mathcal{Z}) \mathfrak{P}(\mathcal{Z}).






This yields the bivariate generating function

Failed to parse (Missing texvc executable; please see math/README to configure.): B(z, u) = \exp uz \exp z\,.






Extracting coefficients, we find that

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} = n! [u^k] [z^n] \exp uz \exp z = n! [z^n] \frac{z^k}{k!} \exp z

or

Failed to parse (Missing texvc executable; please see math/README to configure.): \frac{n!}{k!} [z^{n-k}] \exp z = \frac{n!}{k! \, (n-k)!},






again as expected. This derivation is included here because it closely parallels that of the Stirling numbers of the first and second kind, and hence lends support to the binomial-style notation that is used for these numbers.

Divisors of binomial coefficients




The prime divisors of C(n, k) can be interpreted as follows: if p is a prime number and p^r is the highest power of p which divides C(n, k), then r is equal to the number of natural numbers j such that the fractional part of k/p^j is bigger than the fractional part of n/p^j. In particular, C(n, k) is always divisible by n/gcd(n,k).


A somewhat surprising result by David Singmaster (1974) is that any integer divides almost all binomial coefficients. More precisely, fix an integer d and let f(N) denote the number of binomial coefficients C(n, k) with n < N such that d divides C(n, k). Then

Failed to parse (Missing texvc executable; please see math/README to configure.): \lim_{N\to\infty} \frac{f(N)}{N(N+1)/2} = 1.




Since the number of binomial coefficients C(n, k) with n < N is N(N+1) / 2, this implies that the density of binomial coefficients divisible by d goes to 1.

Bounds for binomial coefficients




The following bounds for C(n, k) hold:

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} \le \frac{n^k}{k!}

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} \le \left(\frac{n\cdot e}{k}\right)^k

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} \ge \left(\frac{n}{k}\right)^k

Generalizations

Generalization to multinomials




Binomial coefficients can be generalized to multinomial coefficients.
They are defined to be the number:

Failed to parse (Missing texvc executable; please see math/README to configure.): {n\choose k_1,k_2,\ldots,k_r} =\frac{n!}{k_1!k_2!\cdots k_r!}




where

Failed to parse (Missing texvc executable; please see math/README to configure.): \sum_{i=1}^rk_i=n






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

(x₁ + x₂ + ... + x_r)ⁿ.




See multinomial theorem.  The case k = 2 gives binomial coefficients:

Failed to parse (Missing texvc executable; please see math/README to configure.): {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 of n distinguishable elements over r (distinguishable) containers, each containing exactly k_i elements, where i is the index of the container.


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

Failed to parse (Missing texvc executable; please see math/README to configure.): {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:

Failed to parse (Missing texvc executable; please see math/README to configure.): {n\choose k_1,k_2,\ldots,k_r} ={n\choose k_{\sigma_1},k_{\sigma_2},\ldots,k_{\sigma_r}}




where Failed to parse (Missing texvc executable; please see math/README to configure.): (\sigma_i)

is a permutation of (1,2,...,r).

Generalization to negative integers




The definition can be extended to negative integers as follows:

Failed to parse (Missing texvc executable; please see math/README to configure.): {-n\choose r} = (-1)^r{n+r-1\choose r} \quad \mbox{if } r\geq 0, n\geq 0

and

Failed to parse (Missing texvc executable; please see math/README to configure.): {-n\choose -r} = \begin{cases}0\quad \mbox{if }r<n,\\ {-n\choose r-n}\quad \mbox{if }r\geq n,\end{cases} n>0, r>0

and

Failed to parse (Missing texvc executable; please see math/README to configure.): {n\choose r} = 0 \quad \mbox{if } n\geq 0, r<0\quad\mbox{or }r>n




This gives rise to the Pascal Hexagon or Pascal Windmill.

Hilton, Holton and Pedersen (1997). Mathematical Reflections. Springer. ISBN 0-387-94770-1.

Generalization to real and complex argument




The binomial coefficient Failed to parse (Missing texvc executable; please see math/README to configure.): {z\choose k}

can be defined for any complex number z and any natural number k as follows:

Failed to parse (Missing texvc executable; please see math/README to configure.): {z\choose k} = \prod_{n=1}^{k}{z-k+n\over n}= \frac{z(z-1)(z-2)\cdots (z-k+1)}{k!}. \qquad (14)






This generalization is known as the generalized binomial coefficient and is used in the formulation of the binomial theorem and satisfies properties (3) and (7).


For fixed k, the expression Failed to parse (Missing texvc executable; please see math/README to configure.): f(z)={z\choose k}

is a polynomial in z of degree k with rational coefficients.




f(z) is the unique polynomial of degree k satisfying

f(0) = f(1) = ... = f(k − 1) = 0 and f(k) = 1.




Any polynomial p(z) of degree d can be written in the form

Failed to parse (Missing texvc executable; please see math/README to configure.): p(z) = \sum_{k=0}^{d} a_k {z\choose k}.






This is important in the theory of difference equations and finite differences, and 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.


In particular, one can express the product of binomial coefficients as such a linear combination:

Failed to parse (Missing texvc executable; please see math/README to configure.): {x\choose m} {x\choose n} = \sum_{k=0}^m {m+n-k\choose k,m-k,n-k} {x\choose m+n-k}






where the connection coefficients are multinomial coefficients. In terms of labelled combinatorial objects, the connection coefficients represent the number of ways to assign m+n-k labels to a pair of labelled combinatorial objects of weight m and n respectively, that have had their first k labels identified, or glued together, in order to get a new labelled combinatorial object of weight m+n-k. (That is, to separate the labels into 3 portions to be applied 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 what falling factorials are to ordinary generating series.

Newton's binomial series




Newton's binomial series, named after Sir Isaac Newton, is one of the simplest Newton series:

Failed to parse (Missing texvc executable; please see math/README to configure.): (1+z)^{\alpha} = \sum_{n=0}^{\infty}{\alpha\choose n}z^n = 1+{\alpha\choose1}z+{\alpha\choose 2}z^2+\cdots.






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


The radius of convergence of this series is 1.  An alternative expression is

Failed to parse (Missing texvc executable; please see math/README to configure.): \frac{1}{(1-z)^{\alpha+1}} = \sum_{n=0}^{\infty}{n+\alpha \choose n}z^n






where the identity

Failed to parse (Missing texvc executable; please see math/README to configure.): {n \choose k} = (-1)^k {k-n-1 \choose k}






is applied.


The formula for the binomial series was etched onto Newton's gravestone in Westminster Abbey in 1727.

Generalization to q-series




The binomial coefficient has a q-analog generalization known as the Gaussian binomial.

Generalization to infinite cardinals




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

Failed to parse (Missing texvc executable; please see math/README to configure.): {\alpha \choose \beta} = | \{ B \subseteq A : |B| = \beta \} |






where A is some set with cardinality Failed to parse (Missing texvc executable; please see math/README to configure.): \alpha
. One can show that the generalized binomial coefficient is well-defined, in the sense that no matter what set we choose to represent the cardinal number Failed to parse (Missing texvc executable; please see math/README to configure.): \alpha
, Failed to parse (Missing texvc executable; please see math/README to configure.): {\alpha \choose \beta}

will remain the same. For finite cardinals, this definition coincides with the standard definition of the binomial coefficient.




Assuming the Axiom of Choice, one can show that Failed to parse (Missing texvc executable; please see math/README to configure.): {\alpha \choose \alpha} = 2^{\alpha}

for any infinite cardinal Failed to parse (Missing texvc executable; please see math/README to configure.): \alpha