Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Combination
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== 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 –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'' = 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 <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'' = 4 and ''k'' = 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, 5, ..., 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> -->
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)