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 Xs 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 Xs. Now setting all of the Xs 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.
Read more about this topic: Combination
Famous quotes containing the words number of and/or number:
“Without claiming superiority of intellectual over visual understanding, one is nevertheless bound to admit that the cinema allows a number of æsthetic-intellectual means of perception to remain unexercised which cannot but lead to a weakening of judgment.”
—Johan Huizinga (18721945)
“I will not adopt that ungenerous and impolitic custom so common with novel writers, of degrading by their contemptuous censure the very performances, to the number of which they are themselves addingjoining with their greatest enemies in bestowing the harshest epithets on such works, and scarcely ever permitting them to be read by their own heroine, who, if she accidentally take up a novel, is sure to turn over its insipid leaves with disgust.”
—Jane Austen (17751817)