Combination

This formula can be derived from the fact that each k-combination of a set S of n members has

[4] If, in the above example, it were possible to have two of any one kind of fruit there would be 3 more 2-selections: one with two apples, one with two oranges, and one with two pears.

The number of k-combinations from a given set S of n elements is often denoted in elementary combinatorics texts by

[5] (the last form is standard in French, Romanian, Russian, and Chinese texts).

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.

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

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

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

for 0 ≤ k ≤ n. 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:

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

, 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 specific example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:[8]

Using the symmetric formula in terms of factorials without performing simplifications gives a rather extensive calculation:

One can enumerate all k-combinations of a given set S of n elements in some fixed order, which establishes a bijection from an interval of

Assuming S is itself ordered, for instance S = { 1, 2, ..., n }, there are two natural possibilities for ordering its k-combinations: by comparing their smallest elements first (as in the illustrations above) or by comparing their largest elements first.

The latter option has the advantage that adding a new largest element to S will not change the initial part of the enumeration, but just add the new k-combinations of the larger set after the previous ones.

Repeating this process, the enumeration can be extended indefinitely with k-combinations of ever larger sets.

If moreover the intervals of the integers are taken to start at 0, then the k-combination at a given place i in the enumeration can be computed easily from i, and the bijection so obtained is known as the combinatorial number system.

One way is to track k index numbers of the elements selected, starting with {0 .. k−1} (zero-based) or {1 .. k} (one-based) as the first allowed k-combination.

A k-combination with repetitions, or k-multicombination, or multisubset of size k from a set S of size n is given by a set of k not necessarily distinct elements of S, where order is not taken into account: two sequences define the same multiset if one can be obtained from the other by permuting the terms.

a notation that is analogous to the binomial coefficient which counts k-subsets.

This relationship can be easily proved using a representation known as stars and bars.

This identity follows from interchanging the stars and bars in the above representation.

and the last column gives the stars and bars representation of the solutions.

, which is the sum of the nth row (counting from 0) of the binomial coefficients in Pascal's triangle.

Representing these subsets (in the same order) as base 2 numerals: There are various algorithms to pick out a random combination from a given set or list.

One way to select a k-combination efficiently from a population of size n is to iterate across each element of the population, and at each step pick that element with a dynamically changing probability of

The number of ways to put objects into bins is given by the multinomial coefficient

distinct numberings, but many of them are equivalent, because only the set of items in a bin matters, not their order in it.

The binomial coefficient is the special case where k items go into the chosen bin and the remaining