combination

In combinatorial mathematics, a k-combination of a finite set S is a subset of k distinct elements of S. Specifying a subset does not arrange them in a particular order; by contrast, producing the k distinct elements in a specific order defines a sequence without repetition, also called k-permutation (but which is not a permutation of S in the usual sense of that term). As an example, a poker hand can be described as a 5-combination of cards from a 52-card deck: the 5 cards of the hand are all distinct, and the order of the cards in the hand does not matter.

The number of k-combinations of an n-element set is equal to the binomial coefficient . For this reason the set of all k-combinations of a set X is sometimes denoted by .

Number of k-combinations

The number of k-combinations from a given set S of n elements of often denoted in elementary combinatorics texts by C(n,k), or by a variation such as , _nC_k, ⁿC_k or even (the latter form is standard in French texts). The same number however occurs in many other mathematical contexts, where it is denoted by ; notably it occurs as coefficient in the binomial formula, whence 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 fist 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 2ⁿ 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)ⁿ, the term for each k-combination from S becomes X^k, so that 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)ⁿ, one can use (in addition to the basic cases already given) the recursion relation

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

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

In this 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.

As a concrete example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:

An alternative, almost equivalent computation, is

which gives

Using the symmetric formula in terms of factorials gives

which illustrates the size of such a computation, and of the numbers involved.

Number of combinations with repetition

The number of combinations with repetition can be calculated as:

For example, if you have ten types of donuts (n) on a menu to choose from and you want three donuts (k) the number of ways to choose can be calculated as (see also multiset):

There is an easy way to understand the above result. Imagine we have n + k identical boxes arranged on a line. From these boxes (except the first one), we arbitrarily choose k of them and mark the chosen boxes as empty. The rest of the boxes can be filled by the n elements in the set S. For each non-empty box, if it is followed by M successive empty boxes, we choose the corresponding element in the non-empty box M times. As a result, each arrangement of choosing empty boxes corresponds to a way of choosing k out of the n elements with repetition. The total number is therefore the number of combinations with repetition, which equals

Example 2

Another explanation may be helpful. Imagine you have slots (or boxes) for 4 types of fruits (apple, orange, pear, banana), all next to one another at the grocery store. That means n=4. If you choose a type of fruit you mark that box, so you put a '1' into that slot. You want to choose 12 pieces of fruit, and you can choose one type of fruit more than once. Therefore, altogether you'll put 12 '1's into the fruit slots. That means k = 12. Now imagine that each separator of a slot is marked by a '0'. For the 4 boxes you will have 4 − 1 = 3 separators.

If you want to choose 2 apples from the first slot, 3 oranges from the second, 5 pears from the third, and 2 bananas from the fourth, that would be denoted by 11 0 111 0 11111 0 11 . The total number of ways we can choose 12 fruits from the 4 boxes (or slots) is simply the number of ways we can put 12 '1's and 3 '0's into order. Thus the total number of ways is the permutation of 12 '1's and 3 '0's. Expressed with k and n:

k = 12; n = 4;

See also

References

External links

• Many Common types of permutation and combination math problems, with detailed solutions
• The Unknown Formula For combinations when choices can be repeated and order does NOT matter
• [1]Combinations with repetitions (by: Akshatha AG and Smitha B)