Combination - Number of k-combinations

Number of k-combinations

The number of k-combinations from a given set S of n elements is often denoted in elementary combinatorics texts by C(n, k), or by a variation such as, or even (the latter form is standard in French, Russian, and Polish texts). The same number however occurs in many other mathematical contexts, where it is denoted by (often read as "n choose k"); notably it occurs as coefficient in the binomial formula, hence its name binomial coefficient. One can define for all natural numbers k at once by the relation

from which it is clear that and for k > n. To see that these coefficients count k-combinations from S, one can first consider a collection of n distinct variables X_s labeled by the elements s of S, and expand the product over all elements of S:

it has 2n distinct terms corresponding to all the subsets of S, each subset giving the product of the corresponding variables X_s. Now setting all of the X_s equal to the unlabeled variable X, so that the product becomes (1 + X)n, the term for each k-combination from S becomes Xk, so that the coefficient of that power in the result equals the number of such k-combinations.

Binomial coefficients can be computed explicitly in various ways. To get all of them for the expansions up to (1 + X)n, one can use (in addition to the basic cases already given) the recursion relation

which follows from (1 + X)n = (1 + X)n − 1(1 + X); this leads to the construction of Pascal's triangle.

For determining an individual binomial coefficient, it is more practical to use the formula

The numerator gives the number of k-permutations of n, i.e., of sequences of k distinct elements of S, while the denominator gives the number of such k-permutations that give the same k-combination when the order is ignored.

When k exceeds n/2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation

This expresses a symmetry that is evident from the binomial formula, and can also be understood in terms of k-combinations by taking the complement of such a combination, which is an (n − k)-combination.

Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy to remember:

where n! denotes the factorial of n. It is obtained from the previous formula by multiplying denominator and numerator by (n − k)!, so it is certainly inferior as a method of computation to that formula.

The last formula can be understood directly, by considering the n! permutations of all the elements of S. Each such permutation gives a k-combination by selecting its first k elements. There are many duplicate selections: any combined permutation of the first k elements among each other, and of the final (n − k) elements among each other produces the same combination; this explains the division in the formula.

From the above formulas follow relations between adjacent numbers in Pascal's triangle in all three directions:

,

,

.

Together with the basic cases, these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal's triangle), of k-combinations of sets of growing sizes, and of combinations with a complement of fixed size n − k.