Discrete Math › Section D · Counting › Topic D.5
Counting multisets (stars and bars)
Choose five pieces of fruit from three kinds, share identical stickers among children, or count whole-number solutions of an equation: all three ask for unordered selections where repeats are allowed, and one picture of stars and bars counts them all.
The missing case
"Combinations and permutations" sorted selections by two questions: does order matter, and can items repeat? Three of the four cases have formulas already: \(n^k\), \(P(n, k)\) and \(\binom{n}{k}\). The fourth, unordered with repetition, is everywhere. A greengrocer's bag of 5 fruits from apples, bananas and pears is unordered (the bag has no first fruit) and repetitive (three apples is allowed). Multiplying \(3 \cdot 3 \cdot 3 \cdot 3 \cdot 3\) would count ordered sequences, listing the same bag many times, and not the same number of times for every bag. A new idea is needed.
Multisets
A multiset is a collection in which elements may appear more than once but order does not matter. It is written with braces, like a set, but repeats count: \(\{a, a, b\}\) differs from \(\{a, b\}\) and from \(\{a, b, b\}\), while \(\{a, a, b\}\) and \(\{a, b, a\}\) are the same multiset. A multiset is fixed entirely by how many copies it holds of each type. So a bag of 5 fruits is just a triple of counts, such as 2 apples, 0 bananas and 3 pears. The question becomes: how many ways can 5 be split into an ordered list of 3 whole-number counts, each at least 0?
Stars and bars
Draw each fruit as a star and separate the types with bars. The bag with 2 apples, 0 bananas and 3 pears becomes \(\star\star\,|\,|\,\star\star\star\): stars before the first bar are apples, stars between the bars are bananas, and stars after the second bar are pears. Every bag gives exactly one such row of 5 stars and 2 bars, and every row of 5 stars and 2 bars describes exactly one bag. So counting bags means counting rows: 7 positions, of which 2 hold bars. Reading star as 0 and bar as 1, each row is a 7-bit string of weight 2, and there are \(\binom{7}{2} = 21\) of them.
The general formula
To choose a multiset of \(k\) elements from \(n\) types, use \(k\) stars and \(n - 1\) bars to separate the \(n\) types. That is \(k + n - 1\) positions, and choosing which of them hold bars gives
The two forms are equal by symmetry: choosing the bar positions is the same as choosing the star positions. Equivalently, this counts ways to put \(k\) identical objects into \(n\) distinct boxes, empty boxes allowed. Check a small case by listing: 2 items from 3 types gives \(\binom{4}{2} = 6\), namely aa, bb, cc, ab, ac and bc.
Worked example: sharing stickers
A teacher shares 12 identical stickers among 4 children. 1. In how many ways, if a child may get none? Stickers are stars and the 4 children need 3 bars: \(\binom{12 + 3}{3} = \binom{15}{3} = 455\). 2. In how many ways, if every child gets at least one? First hand each child one sticker, which can be done in only one way. That leaves 8 stickers to share freely: \(\binom{8 + 3}{3} = \binom{11}{3} = 165\). 3. Check by reasoning: every sharing with no empty-handed child arises from exactly one free sharing of the 8 leftover stickers, so the two counts must match. A brute-force count of all sharings confirms both 455 and 165.
Whole-number solutions of equations
How many solutions does \(x_1 + x_2 + x_3 = 9\) have in non-negative integers? Each solution splits 9 units among 3 variables, so it is a row of 9 stars and 2 bars: \(\binom{11}{2} = 55\). Lower bounds are handled by paying them first. Suppose \(x_1 \ge 2\) and \(x_3 \ge 1\) while \(x_2 \ge 0\). Substitute \(y_1 = x_1 - 2\) and \(y_3 = x_3 - 1\), giving \(y_1 + x_2 + y_3 = 6\) with every variable at least 0. That has \(\binom{8}{2} = 28\) solutions. Upper bounds, such as \(x_1 \le 4\), are harder and need inclusion-exclusion, as "Advanced counting: derangements and functions" shows.
Worked example: rolling identical dice
Three identical dice are rolled and dropped into a cup, so only the multiset of faces can be seen. How many different results are there? 1. A result is a multiset of size \(k = 3\) from \(n = 6\) face values. 2. Use 3 stars and 5 bars: \(\binom{8}{3} = 56\) results. 3. Compare with distinguishable dice, which give \(6^3 = 216\) ordered results. 4. The ratio is not a whole number, \(216 / 56 \approx 3.9\), confirming that multisets are not repeated a uniform number of times among sequences. The result \(\{1, 1, 1\}\) comes from one ordered roll, while \(\{1, 2, 3\}\) comes from six, so the 56 results are not equally likely.
Non-decreasing sequences
Multisets also count sequences whose order is forced. A sequence of 4 digits from 1 to 5 that never decreases, such as 1 1 3 5, is completely determined by how many of each digit it contains, because the digits must appear in sorted order. So such sequences correspond one-to-one with multisets of size 4 from 5 values: \(\binom{4 + 4}{4} = \binom{8}{4} = 70\). The same reasoning counts ways to buy 4 scoops from 5 ice-cream flavours, or to give 4 identical tasks to 5 workers. Recognising that an apparently ordered problem has only one valid order is often the step that unlocks it.
Common mistakes to avoid
First, using \(n^k\), which counts ordered sequences and lists the same multiset several times. Second, dividing \(n^k\) by \(k!\) to fix this: multisets with repeats are not overcounted \(k!\) times, so the quotient principle does not apply. Third, using \(n\) bars instead of \(n - 1\): separating \(n\) types takes one bar fewer than the number of types. Fourth, forgetting a lower bound: "at least one each" means paying out the minimum first. Fifth, treating the multiset results of identical dice as equally likely when calculating probabilities.
Key takeaways
A multiset is an unordered collection with repeats allowed, fixed by its count of each type. Stars and bars turns a multiset of \(k\) elements from \(n\) types into a row of \(k\) stars and \(n - 1\) bars, giving \(\binom{k + n - 1}{n - 1}\). The same number counts distributions of \(k\) identical objects into \(n\) distinct boxes and non-negative integer solutions of \(x_1 + \cdots + x_n = k\). Lower bounds are paid first; upper bounds need inclusion-exclusion. Multiset outcomes are usually not equally likely.
Flashcards
Flashcard
An unordered collection in which repeats are allowed
Test your understanding
Question 1 of 5
A shop sells 4 kinds of doughnut. How many different boxes of 6 doughnuts can be bought, if any kind can be repeated?
Question 2 of 5
In how many ways can 10 identical coins be shared among 3 people if each person gets at least one coin?
Question 3 of 5
How many solutions in non-negative integers does x + y + z + w = 5 have?
Question 4 of 5
In the stars-and-bars picture for putting 7 identical balls into 5 boxes, what does each row contain?
Question 5 of 5
Three identical dice give 56 possible multisets of faces. Why is the probability of each one not 1/56?
