Editing Combination (section)

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