Editing Combination (section)

== 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.