Editing Combination

{{About|the mathematics of selecting part of a collection}}
{{Redirect|COMBIN|other uses|Combin (disambiguation)}}
{{Short description|Selection of items from a set}}
{{Use dmy dates|date=April 2022}}
In [[mathematics]], a '''combination''' is a selection of items from a [[set (mathematics)|set]] that has distinct members, such that the order of selection does not matter (unlike [[permutation]]s). 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 ''k''-combination of a set ''S'' is a subset of ''k'' distinct elements of ''S''. So, two combinations are identical [[if and only if]] each combination has the same members. (The arrangement of the members in each set does not matter.) If the set has ''n'' elements, the number of ''k''-combinations, denoted by <math>C(n,k)</math> or <math>C^n_k</math>, is equal to the [[binomial coefficient]]

<math display="block"> \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1},</math>

which can be written using [[factorial]]s as <math>\textstyle\frac{n!}{k!(n-k)!}</math> whenever <math>k\leq n</math>, and which is zero when <math>k>n</math>. This formula can be derived from the fact that each ''k''-combination of a set ''S'' of ''n'' members has <math>k!</math> permutations so <math>P^n_k = C^n_k \times k!</math> or <math>C^n_k = P^n_k / k!</math>.<ref>{{Cite book|last=Reichl|first=Linda E.|title=A Modern Course in Statistical Physics|publisher=WILEY-VCH|year=2016|isbn=978-3-527-69048-0|pages=30|chapter=2.2. Counting Microscopic States}}</ref> The set of all ''k''-combinations of a set ''S'' is often denoted by <math>\textstyle\binom Sk</math>.

A combination is a selection of ''n'' things taken ''k'' at a time ''without repetition''. To refer to combinations in which repetition is allowed, the terms ''k''-combination with repetition, ''k''-[[multiset]],<ref>{{harvnb|Mazur|2010|loc=p. 10}}</ref> or ''k''-selection,<ref>{{harvnb|Ryser|1963|loc=p. 7}} also referred to as an ''unordered selection''.</ref> are often used.<ref>When the term ''combination'' is used to refer to either situation (as in {{harv|Brualdi|2010}}) care must be taken to clarify whether sets or multisets are being discussed.</ref> 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.

Although the set of three fruits was small enough to write a complete list of combinations, this becomes impractical as the size of the set increases. For example, a [[Hand (poker)|poker hand]] can be described as a 5-combination (''k''&nbsp;=&nbsp;5) of cards from a 52 card deck (''n''&nbsp;=&nbsp;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&nbsp;1&nbsp;/&nbsp;2,598,960.

== Number of ''k''-combinations ==
{{main|Binomial coefficient}}
{{Redirect|COMBIN|other uses|Combin (disambiguation)}}
[[File:Combinations without repetition; 5 choose 3.svg|thumb|3-element subsets of a 5-element set]]
The number of ''k''-combinations from a given set ''S'' of ''n'' elements is often denoted in elementary combinatorics texts by <math>C(n,k)</math>, or by a variation such as <math>C^n_k</math>,  <math>{}_nC_k</math>, <math>{}^nC_k</math>, <math>C_{n,k}</math> or even <math>C_n^k</math><ref>{{harvnb|Uspensky|1937|p=18}}</ref> (the last form is standard in French, Romanian, Russian, and Chinese texts).<ref>{{cite book |title = High School Textbook for full-time student (Required) Mathematics Book II B| edition=2nd | location = China|language = zh |date=June 2006| publisher = People's Education Press| pages = 107–116 | isbn = 978-7-107-19616-4 }}</ref><ref>{{cite book |url=http://www.shuxue9.com/pep/gzxuanxiu23/ebook/31.html|title=人教版高中数学选修2-3 | trans-title=Mathematics textbook, volume 2-3, for senior high school, People's Education Press | publisher =People's Education Press | page=21 | archive-url=https://web.archive.org/web/20230407124424/http://www.shuxue9.com/pep/gzxuanxiu23/ebook/31.html | archive-date=2023-04-07 | url-status=live}}</ref>  The same number however occurs in many other mathematical contexts, where it is denoted by <math>\tbinom nk</math> (often read as "''n'' choose ''k''"); notably it occurs as a coefficient in the [[binomial formula]], hence its name binomial coefficient. One can define <math>\tbinom nk</math> for all natural numbers ''k'' at once by the relation

<math display="block">(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,</math>

from which it is clear that

<math display="block">\binom{n}{0} = \binom{n}{n} = 1,</math>

and further

<math display="block">\binom{n}{k} = 0</math>

for <math>k>n</math>.

To see that these coefficients count ''k''-combinations from ''S'', one can first consider a collection of ''n'' distinct variables ''X''<sub>''s''</sub> labeled by the elements ''s'' of ''S'', and expand the [[Multiplication|product]] over all elements of&nbsp;''S'':

<math display="block">\prod_{s\in S}(1+X_s);</math>

it has 2<sup>''n''</sup> distinct terms corresponding to all the subsets of ''S'', each subset giving the product of the corresponding variables ''X''<sub>''s''</sub>. Now setting all of the ''X''<sub>''s''</sub> equal to the unlabeled variable ''X'', so that the product becomes {{nowrap|(1 + ''X'')<sup>''n''</sup>}}, the term for each ''k''-combination from ''S'' becomes ''X''<sup>''k''</sup>, 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 {{nowrap|(1 + ''X'')<sup>''n''</sup>}}, one can use (in addition to the basic cases already given) the recursion relation

<math display="block">\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k},</math>

for 0 < ''k'' < ''n'', which follows from {{nowrap|(1 + ''X'')<sup>''n''</sup> }}={{nowrap| (1 + ''X'')<sup>''n'' − 1</sup>(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

<math display="block">\binom nk = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.</math>

The [[numerator]] gives the number of [[Permutation#k-permutations of n|''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

<math display="block"> \binom nk = \binom n{n-k},</math>

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 (set theory)|complement]] of such a combination, which is an {{nowrap|(''n'' − ''k'')}}-combination.

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

<math display="block"> \binom nk = \frac{n!}{k!(n-k)!},</math>

where ''n''<nowiki>!</nowiki> denotes the [[factorial]] of ''n''. It is obtained from the previous formula by multiplying denominator and numerator by {{nowrap|(''n'' − ''k'')}}!, so it is certainly computationally less efficient than that formula.

The last formula can be understood directly, by considering the ''n''<nowiki>!</nowiki> 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''&nbsp;&minus;&nbsp;''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:

<math display="block">
\binom nk =
\begin{cases}
\displaystyle \binom n{k-1} \frac {n-k+1}k &\quad \text{if } k > 0 \\
\displaystyle \binom {n-1}k \frac n{n-k} &\quad \text{if } k < n \\
\displaystyle \binom {n-1}{k-1} \frac nk &\quad \text{if } n, k > 0
\end{cases}.
</math>

Together with the basic cases <math>\tbinom n0=1=\tbinom nn</math>, 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 {{nowrap|''n'' − ''k''}}.

=== Example of counting combinations ===
As a specific example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:<ref>{{harvnb|Mazur|2010|loc=p. 21}}</ref>

<math display="block"> \binom{52}{5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311{,}875{,}200}{120} = 
2{,}598{,}960.</math>

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:
<math display="block">\begin{alignat}{2}
  \binom{52}{5}
    &= \frac{52!}{5!47!} \\[5pt]
    &= \frac{52\times51\times50\times49\times48\times\cancel{47!}}{5\times4\times3\times2\times\cancel{1}\times\cancel{47!}} \\[5pt]
    &= \frac{52\times51\times50\times49\times48}{5\times4\times3\times2} \\[5pt]
    &= \frac{(26\times\cancel{2})\times(17\times\cancel{3})\times(10\times\cancel{5})\times49\times(12\times\cancel{4})}{\cancel{5}\times\cancel{4}\times\cancel{3}\times\cancel{2}} \\[5pt]
    &= {26\times17\times10\times49\times12} \\[5pt]
    &= 2{,}598{,}960.
\end{alignat}</math>

Another alternative computation, equivalent to the first, is based on writing

<math display="block"> \binom{n}{k} = \frac { ( n - 0 ) }1 \times \frac { ( n - 1 ) }2 \times \frac { ( n - 2 ) }3 \times \cdots \times \frac { ( n - (k - 1) ) }k,</math>

which gives

<math display="block"> \binom{52}{5} = \frac{52}1 \times \frac{51}2 \times \frac{50}3 \times \frac{49}4 \times \frac{48}5 = 2{,}598{,}960.</math>

When evaluated in the following order, {{math|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:

<math display="block">
\begin{align}
 \binom{52}{5} &= \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} \\[6pt]
&= \tfrac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\[6pt]
&= 2{,}598{,}960.
\end{align}</math>

=== Enumerating ''k''-combinations ===

One can [[enumeration|enumerate]] all ''k''-combinations of a given set ''S'' of ''n'' elements in some fixed order, which establishes a [[bijection]] from an interval of <math>\tbinom nk</math> integers with the set of those ''k''-combinations. 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&nbsp;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]]. It is also known as "rank"/"ranking" and "unranking" in computational mathematics.<ref>{{cite web|url=http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-date=2022-10-09 |url-status=live |title=Generating Elementary Combinatorial Objects |author=Lucia Moura |website=Site.uottawa.ca |access-date=2017-04-10}}</ref><ref>{{cite web|url=http://www.sagemath.org/doc/reference/sage/combinat/subset.html |format=PDF |title=SAGE : Subsets |website=Sagemath.org |access-date=2017-04-10}}</ref>

There are many ways to enumerate ''k'' combinations. 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. Then, repeatedly move to the next allowed ''k''-combination by incrementing the smallest index number for which this would not create two equal index numbers, at the same time resetting all smaller index numbers to their initial values.

== Number of combinations with repetition ==
{{See also|Multiset coefficient}}

A ''k''-'''combination with repetitions''', or ''k''-'''multicombination''', or '''[[multiset|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. In other words, it is a sample of ''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 <math>x_i</math> 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 (so allowing zero) solutions of the [[Diophantine equation]]:<ref>{{harvnb|Brualdi|2010|loc=p. 52}}</ref>

<math display="block">x_1 + x_2 + \ldots + x_n = k.</math>

If ''S'' has ''n'' elements, the number of such ''k''-multisubsets is denoted by

<math display="block">\left(\!\!\binom{n}{k}\!\!\right),</math>

a notation that is analogous to the [[binomial coefficient]] which counts ''k''-subsets. This expression, ''n'' multichoose ''k'',<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 70}}</ref> can also be given in terms of binomial coefficients:

<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.</math>

This relationship can be easily proved using a representation known as [[Stars and bars (combinatorics)|stars and bars]].<ref>In the article [[Stars and bars (combinatorics)]] the roles of {{mvar|n}} and {{mvar|k}} are reversed.</ref> 
{{Hidden begin |showhide=left|title=Proof|titlestyle = background:lightgray;}}
A solution of the above Diophantine equation can be represented by <math>x_1</math> ''stars'', a separator (a ''bar''), then <math>x_2</math> 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 a separation into n parts needs n-1 separators). Thus, a string of ''k'' + ''n'' - 1 (or ''n'' + ''k'' - 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 {{nobreak|''k'' + ''n'' − 1}} positions to place stars and filling the remaining positions with bars. For example, the solution <math>x_1 = 3, x_2 = 2, x_3 = 0, x_4 = 5</math> of the equation <math> x_1 + x_2 + x_3 + x_4 = 10</math> (''n'' = 4 and ''k'' = 10) can be represented by<ref>{{harvnb|Benjamin|Quinn|2003|loc=pp. 71 &ndash;72}}</ref>

<math display="block">\bigstar \bigstar \bigstar | \bigstar \bigstar | | \bigstar \bigstar \bigstar \bigstar \bigstar.</math>

The number of such strings is the number of ways to place 10 stars in 13 positions, <math display="inline">\binom{13}{10} = \binom{13}{3} = 286,</math> which is the number of 10-multisubsets of a set with 4 elements.
{{Hidden end}}

[[File:Combinations with repetition; 5 multichoose 3.svg|thumb|370px|[[Bijection]] between 3-subsets of a 7-set (left) and 3-multisets with elements from a 5-set (right).<br />This illustrates that <math display="inline"> \binom{7}{3} = \left(\!\! \binom{5}{3}\!\!\right)</math>.]]

As with binomial coefficients, there are several relationships between these multichoose expressions. For example, for <math> n \ge 1, k \ge 0</math>,

<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).</math>
This identity follows from interchanging the stars and bars in the above representation.<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 72 (identity 145)}}</ref>
<!--(the case where both ''r'' and ''k'' are zero is special; the correct value 1 (for the empty 0-multicombination) is given by left hand side <math>\tbinom{-1}0</math>, but not by the right hand side <math>\tbinom{-1}{-1}</math>). This follows from a clever representation of such combinations with just two symbols (see [[Stars and bars (combinatorics)]]). -->

=== Example of counting multisubsets ===
For example, if you have four types of donuts (''n''&nbsp;=&nbsp;4) on a menu to choose from and you want three donuts (''k''&nbsp;=&nbsp;3), the number of ways to choose the donuts with repetition can be calculated as

<math display="block">\left(\!\!\binom{4}{3}\!\!\right) = \binom{4+3-1}3 = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20.</math>

This result can be verified by listing all the 3-multisubsets of the set ''S'' = {1,2,3,4}. This is displayed in the following table.<ref>{{harvnb|Benjamin|Quinn|2003|loc=p. 71}}</ref> The second column lists the donuts you actually chose, the third column shows the nonnegative integer solutions <math>[x_1,x_2,x_3,x_4]</math> of the equation <math>x_1 + x_2 + x_3 + x_4 = 3</math> and the last column gives the stars and bars representation of the solutions.<ref>{{harvnb|Mazur|2010|loc=p. 10}} where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.</ref>

{| class="wikitable" style="margin-left: auto; margin-right: auto; border; none"
|-
! No.!! 3-multiset!! Eq. solution!! Stars and bars
|-
| 1 || {1,1,1} || [3,0,0,0] || <math>\bigstar \bigstar \bigstar |||</math>
|-
| 2 || {1,1,2} || [2,1,0,0] || <math>\bigstar \bigstar | \bigstar ||</math>
|-
| 3 || {1,1,3} || [2,0,1,0] || <math>\bigstar \bigstar ||\bigstar|</math>
|-
| 4 || {1,1,4} || [2,0,0,1] || <math>\bigstar \bigstar |||\bigstar</math>
|-
| 5 || {1,2,2} || [1,2,0,0] || <math>\bigstar |\bigstar \bigstar ||</math>
|-
| 6 || {1,2,3} || [1,1,1,0] || <math>\bigstar |\bigstar |\bigstar|</math>
|-
| 7 || {1,2,4} || [1,1,0,1] || <math>\bigstar |\bigstar ||\bigstar</math>
|-
| 8 || {1,3,3} || [1,0,2,0] || <math>\bigstar || \bigstar \bigstar |</math>
|-
| 9 || {1,3,4} || [1,0,1,1] || <math>\bigstar ||\bigstar|\bigstar</math>
|-
| 10 || {1,4,4} || [1,0,0,2] || <math>\bigstar |||\bigstar \bigstar</math>
|-
| 11 || {2,2,2} || [0,3,0,0] || <math>|\bigstar \bigstar \bigstar ||</math>
|-
| 12 || {2,2,3} || [0,2,1,0] || <math>|\bigstar \bigstar | \bigstar|</math>
|-
| 13 || {2,2,4} || [0,2,0,1] || <math>|\bigstar \bigstar ||\bigstar</math>
|-
| 14 || {2,3,3} || [0,1,2,0] || <math>|\bigstar |\bigstar \bigstar |</math>
|-
| 15 || {2,3,4} || [0,1,1,1] || <math>|\bigstar | \bigstar | \bigstar</math>
|-
| 16 || {2,4,4} || [0,1,0,2] || <math>|\bigstar ||\bigstar \bigstar</math>
|-
| 17 || {3,3,3} || [0,0,3,0] || <math>||\bigstar \bigstar \bigstar |</math>
|-
| 18 || {3,3,4} || [0,0,2,1] ||<math>||\bigstar \bigstar |\bigstar</math>
|-
| 19 || {3,4,4} || [0,0,1,2] || <math>||\bigstar |\bigstar \bigstar</math>
|-
| 20 || {4,4,4} || [0,0,0,3] || <math>|||\bigstar \bigstar \bigstar</math>
|}
<!--The analogy with the ''k''-combination case can be stressed by writing the numerator as a rising power

<math display="block">\binom{n + k - 1}{k} =  \frac{n(n+1)\cdots(n+k-1)}{k!}.</math>

There is an easy way to understand the above result. Label the elements of ''S'' with numbers 0, 1, ..., {{nowrap|''n'' − 1}}, and choose a ''k''-combination from the set of numbers { 1, 2, ..., {{nowrap|''n'' + ''k'' − 1}} } (so that there are {{nowrap|''n'' − 1}} ''unchosen'' numbers). Now change this ''k''-combination into a ''k''-multicombination of ''S'' by replacing every (chosen) number ''x'' in the ''k''-combination by the element of ''S'' labeled by the ''number of unchosen numbers'' less than ''x''. This is always a number in the range of the labels, and it is easy to see that every ''k''-multicombination of ''S'' is obtained for one choice of a ''k''-combination.

A concrete example may be helpful. Suppose there are 4 types of fruits (apple, orange, pear, banana) at a grocery store, and you want to buy 12 pieces of fruit. So ''n''&nbsp;=&nbsp;4 and ''k''&nbsp;=&nbsp;12. Use label 0 for apples, 1 for oranges, 2 for pears, and 3 for bananas. A selection of 12 fruits can be translated into a selection of 12 distinct numbers in the range 1,...,15 by selecting as many consecutive numbers starting from 1 as there are apples in the selection, then skip a number, continue choosing as many consecutive numbers as there are oranges selected, again skip a number, then again for pears, skip one again, and finally choose the remaining numbers (as many as there are bananas selected). For instance for 2 apples, 7 oranges, 0 pears and 3 bananas, the numbers chosen will be 1, 2, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15. To recover the fruits, the numbers 1, 2 (not preceded by any unchosen numbers) are replaced by apples, the numbers 4,&nbsp;5,&nbsp;...,&nbsp;10 (preceded by one unchosen number: 3) by oranges, and the numbers 13, 14, 15 (preceded by three unchosen numbers: 3, 11, and 12) by bananas; there are no chosen numbers preceded by exactly 2 unchosen numbers, and therefore no pears in the selection. The total number of possible selections is

<math display="block">\binom{4+12-1}{12} = \left(\!\!\!\binom{4}{12}\!\!\!\right) = \binom{15}{12} = \left(\!\!\!\binom{13}{3}\!\!\!\right) = \binom{15}{3} = \frac{13\times14\times15}{1\times2\times3} = 455. </math>
-->

== Number of ''k''-combinations for all ''k'' ==
{{See also|Binomial coefficient#Sum of coefficients row}}

The number of ''k''-combinations 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<sup>''n''</sup>. In terms of combinations, <math display="inline">\sum_{0\leq{k}\leq{n}}\binom n k = 2^n</math>, which is the sum of the ''n''th row (counting from 0) of the [[Binomial coefficient#Sum of coefficients row|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<sup>''n''</sup>&nbsp;−&nbsp;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]]:

<math display="block">| \{ \{\}  ;  \{1\}  ;  \{2\}  ;  \{1, 2\} ; \{3\}  ;  \{1, 3\}  ;  \{2, 3\}  ;  \{1, 2, 3\} \}| = 2^3 = 8</math>

Representing these subsets (in the same order) as base 2 numerals:

*0 – 000
*1 – 001
*2 – 010
*3 – 011
*4 – 100
*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 ''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 <math display="inline">\frac{k-\#\text{samples chosen}}{n- \#\text{samples visited}}</math> (see [[Reservoir sampling]]). Another is to pick a random non-negative integer less than <math>\textstyle\binom nk</math> and convert it into a combination using the [[combinatorial number system]].

== Number of ways to put objects into bins ==

A combination can also be thought of as a selection of ''two'' sets of items: those that go into the chosen bin and those that go into the unchosen bin. This can be generalized to any number of bins with the constraint that every item must go to exactly one bin. The number of ways to put objects into bins is given by the [[Multinomial theorem#Ways to put objects into bins|multinomial coefficient]]

<math display="block"> \binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!},</math>

where ''n'' is the number of items, ''m'' is the number of bins, and <math>k_i</math> is the number of items that go into bin ''i''.

One way to see why this equation holds is to first number the objects arbitrarily from ''1'' to ''n'' and put the objects with numbers <math>1, 2, \ldots, k_1</math> into the first bin in order, the objects with numbers <math>k_1+1, k_1+2, \ldots, k_2</math> into the second bin in order, and so on. There are <math>n!</math> distinct numberings, but many of them are equivalent, because only the set of items in a bin matters, not their order in it. Every combined permutation of each bins' contents produces an equivalent way of putting items into bins. As a result, every equivalence class consists of <math>k_1!\, k_2! \cdots k_m!</math> distinct numberings, and the number of equivalence classes is <math>\textstyle\frac{n!}{k_1!\, k_2! \cdots k_m!}</math>.

The binomial coefficient is the special case where ''k'' items go into the chosen bin and the remaining <math>n-k</math> items go into the unchosen bin:

<math display="block"> \binom nk = \binom{n}{k, n-k} = \frac{n!}{k!(n-k)!}. </math>

==See also==
{{Portal|Mathematics}}
{{div col|colwidth=30em}}
* [[Binomial coefficient]]
* [[Combinatorics]]
* [[Block design]]
* [[Kneser graph]]
* [[List of permutation topics]]
* [[Multiset]]
* [[Probability]]
{{div col end}}

==Notes==
{{Reflist|30em}}

==References==
* {{citation | first1 = Arthur T. | last1 = Benjamin | author1-link = Arthur T. Benjamin | first2 = Jennifer J. | last2 = Quinn | author2-link = Jennifer Quinn | title = Proofs that Really Count: The Art of Combinatorial Proof | title-link = Proofs That Really Count | year = 2003 | series = The Dolciani Mathematical Expositions 27 | publisher = The Mathematical Association of America | isbn = 978-0-88385-333-7 }}
* {{citation|first=Richard A.|last=Brualdi|author-link=Richard A. Brualdi|year=2010|title=Introductory Combinatorics|edition=5th|publisher=Pearson Prentice Hall|isbn=978-0-13-602040-0}}
* [[Erwin Kreyszig]], ''Advanced Engineering Mathematics'', John Wiley & Sons, INC, 1999.
* {{citation|first=David R.|last= Mazur|title=Combinatorics: A Guided Tour|year= 2010|publisher=Mathematical Association of America|isbn=978-0-88385-762-5}}
* {{citation|first= Herbert John|last=Ryser|author-link=H. J. Ryser|year=1963|title=Combinatorial Mathematics|publisher=Mathematical Association of America|series=The Carus Mathematical Monographs 14}}
* {{citation| first=James|last=Uspensky|author-link=J. V. Uspensky|title=Introduction to Mathematical Probability|year=1937|publisher=McGraw-Hill|url=https://archive.org/details/in.ernet.dli.2015.263184/page/n25/mode/2up}}

==External links==
* [https://www.topcoder.com/community/data-science/data-science-tutorials/basics-of-combinatorics/ Topcoder tutorial on combinatorics  ]
* [http://mathforum.org/library/drmath/sets/high_perms_combs.html Many Common types of permutation and combination math problems, with detailed solutions]
* [http://www.murderousmaths.co.uk/books/unknownform.htm The Unknown Formula] For combinations when choices can be repeated and order does ''not'' matter
* [http://www.lucamoroni.it/the-dice-roll-sum-problem/ The dice roll with a given sum problem] An application of the combinations with repetition to rolling multiple dice

[[Category:Combinatorics]]