Editing Combination (section)

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