In mathematics, a combination is a way of selecting members from a grouping, such that (unlike permutations) the order of selection does not matter. In smaller cases it is possible to count the number of combinations. For example given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a kcombination of a set S is a subset of k distinct elements of S. If the set has n elements, the number of kcombinations is equal to the binomial coefficient
which can be written using factorials as whenever , and which is zero when . The set of all kcombinations of a set S is sometimes denoted by .
Combinations refer to the combination of n things taken k at a time without repetition. To refer to combinations in which repetition is allowed, the terms kselection,kmultiset, or kcombination with repetition are often used. If, in the above example, it was possible to have two of any one kind of fruit there would be 3 more 2selections: one with two apples, one with two oranges, and one with two pears.
With large sets, it becomes necessary to use more sophisticated mathematics to find the number of combinations. For example, a poker hand can be described as a 5combination (k = 5) of cards from a 52 card deck (n = 52). The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and the chance of drawing any one hand at random is 1 / 2,598,960.
Number of kcombinations
The number of kcombinations 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 was standard in French, Russian, Chinese 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 a 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 kcombinations 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 2^{n} 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 kcombination from S becomes X^{k}, so that the coefficient of that power in the result equals the number of such kcombinations.
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 kpermutations of n, i.e., of sequences of k distinct elements of S, while the denominator gives the number of such kpermutations that give the same kcombination 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 kcombinations 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 kcombination 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 kcombinations of sets of growing sizes, and of combinations with a complement of fixed size n − k.
Example of counting combinations
As a concrete example, one can compute the number of fivecard hands possible from a standard fiftytwo card deck as:
Alternatively one may use the formula in terms of factorials and cancel the factors in the numerator against parts of the factors in the denominator, after which only multiplication of the remaining factors is required:
Another alternative computation, equivalent to the first, is based on writing
which gives
When evaluated in the following order, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, this can be computed using only integer arithmetic. The reason is that when each division occurs, the intermediate result that is produced is itself a binomial coefficient, so no remainders ever occur.
Using the symmetric formula in terms of factorials without performing simplifications gives a rather extensive calculation:
Enumerating kcombinations
One can enumerate all kcombinations of a given set S of n elements in some fixed order, which establishes a bijection from an interval of integers with the set of those kcombinations. Assuming S is itself ordered, for instance S = {1,2, ...,n}, there are two natural possibilities for ordering its kcombinations: 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 kcombinations of the larger set after the previous ones. Repeating this process, the enumeration can be extended indefinitely with kcombinations of ever larger sets. If moreover the intervals of the integers are taken to start at 0, then the kcombination 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. It is also known as "rank"/"ranking" and "unranking" in computational mathematics.
There are many ways to enumerate k combinations. One way is to visit all the binary numbers less than . Chose those numbers having k nonzero bits. The positions of these 1 bits in such a number is a specific kcombination of the set {1,...,n}.
Number of combinations with repetition
A kcombination with repetitions, or kmulticombination, or multisubset of size k from a set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account: two sequences of which one can be obtained from the other by permuting the terms define the same multiset. In other words, the number of ways to sample k elements from a set of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). Associate an index to each element of S and think of the elements of S as types of objects, then we can let denote the number of elements of type i in a multisubset. The number of multisubsets of size k is then the number of nonnegative integer solutions of the Diophantine equation:
If S has n elements, the number of such kmultisubsets is denoted by,
a notation that is analogous to the binomial coefficient which counts ksubsets. This expression, n multichoose k, is also given by a binomial coefficient:
This relationship can be easily seen using a representation known as stars and bars. A solution of the above Diophantine equation can be represented by stars, a separator (a bar), then more stars, another separator, and so on. The total number of stars in this representation is k and the number of bars is n  1 (since no separator is needed at the very end). Thus, a string of k + n  1 symbols (stars and bars) corresponds to a solution if there are k stars in the string. Any solution can be represented by choosing k out of k + n  1 positions to place stars and filling the remaining positions with bars. For example, the solution of the equation can be represented by
The number of such strings is the number of ways to place 10 stars in 13 positions, which is the number of 10multisubsets of a set with 4 elements.
As with binomial coefficients, there are several relationships between these multichoose expressions. For example, for ,
This identity follows from interchanging the stars and bars in the above representation.
Example of counting multisubsets
For example, if you have four types of donuts (n = 4) on a menu to choose from and you want three donuts (k = 3), the number of ways to choose the donuts with repetition can be calculated as
This result can be verified by listing all the 3multisubsets of the set S = {1,2,3,4}. This is displayed in the following table. The second column shows the nonnegative integer solutions of the equation and the last column gives the stars and bars representation of the solutions.
No.  3Multiset  Eq. Solution  Stars and Bars 

1  {1,1,1}  [3,0,0,0]  
2  {1,1,2}  [2,1,0,0]  
3  {1,1,3}  [2,0,1,0]  
4  {1,1,4}  [2,0,0,1]  
5  {1,2,2}  [1,2,0,0]  
6  {1,2,3}  [1,1,1,0]  
7  {1,2,4}  [1,1,0,1]  
8  {1,3,3}  [1,0,2,0]  
9  {1,3,4}  [1,0,1,1]  
10  {1,4,4}  [1,0,0,2]  
11  {2,2,2}  [0,3,0,0]  
12  {2,2,3}  [0,2,1,0]  
13  {2,2,4}  [0,2,0,1]  
14  {2,3,3}  [0,1,2,0]  
15  {2,3,4}  [0,1,1,1]  
16  {2,4,4}  [0,1,0,2]  
17  {3,3,3}  [0,0,3,0]  
18  {3,3,4}  [0,0,2,1]  
19  {3,4,4}  [0,0,1,2]  
20  {4,4,4}  [0,0,0,3] 
Number of kcombinations for all k
The number of kcombinations for all k is the number of subsets of a set of n elements. There are several ways to see that this number is 2^{n}. In terms of combinations, , which is the sum of the nth row (counting from 0) of the binomial coefficients in Pascal's triangle. These combinations (subsets) are enumerated by the 1 digits of the set of base 2 numbers counting from 0 to 2^{n}  1, where each digit position is an item from the set of n.
Given 3 cards numbered 1 to 3, there are 8 distinct combinations (subsets), including the empty set:
Representing these subsets (in the same order) as base 2 numbers:

 0  000
 1  001
 2  010
 4  100
 3  011
 5  101
 6  110
 7  111
Probability: sampling a random combination
There are various algorithms to pick out a random combination from a given set or list. Rejection sampling is extremely slow for large sample sizes. One way to select a kcombination 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 . (see reservoir sampling).
See also
 Binomial coefficient
 Combinatorial number system
 Combinatorics
 Kneser graph
 List of permutation topics
 Multiset
 Pascal's triangle
 Permutation
 Probability
 Subset
Notes
References
 Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 9780883853337
 Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pearson Prentice Hall, ISBN 9780136020400
 Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
 Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 9780883857625
 Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America
External links
 For combinations when choices can be repeated and order does NOT matter