Discrete Mathematics and Proof

Combinations with repetition: stars and bars

A box holds twelve donuts and the shop makes five kinds, as many of each as you like. How many different boxes are there, without listing them?

You need

CombinationsAlgebra 2

Where you are 10 in Counting

Probability4

Counting10

Arrangements and factorials Combinations

Combinations with repetition: stars and bars

Inclusion-exclusion for three or more sets, and derangements Probability with counting formulas ▾ Show all 10 (5 more)

When you reach for it

A combination chooses k different objects and ignores their order. Many choices allow repeats instead: a box of donuts may hold three jelly donuts, a basket may hold five apples, a roll of dice may show two sixes. What is chosen is a number of items of each kind, the items of one kind are alike, and only how many of each kind matters, not the order they were picked in.

Such a choice is a selection of k items from n kinds with repeats allowed (also called a multiset of size k). The same count answers questions about equations in natural numbers, nondecreasing sequences, terms of a polynomial and identical dice: each is matched one to one with a row of stars and bars, counted by one binomial coefficient.

Throughout, \mathbb{N} = \{0, 1, 2, \ldots\} is the set of natural numbers, and “positive integers” means 1, 2, 3, \ldots.

The procedure

This lesson takes two days. Day 1 is the stars-and-bars count and why it is true (Examples 1 to 3); Day 2 is lower bounds, other things the same count counts, and choosing among the four basic counts (Examples 4 to 7).

Day 1: from a selection to an equation

Name the kinds 1, 2, \ldots, n. A selection of k items is fixed by how many of each kind it holds: x_1 of kind 1, x_2 of kind 2, and so on. Each x_i is in \mathbb{N} (a kind may be left out) and together they make k. So the selections correspond one to one with the solutions of

x_1 + x_2 + \cdots + x_n = k, \qquad x_1, \ldots, x_n \in \mathbb{N}

and counting either one counts the other.

Day 1: stars and bars

Write a solution as a row of symbols: x_1 stars, then a bar, then x_2 stars, then a bar, and so on, ending with x_n stars. The n - 1 bars separate the kinds; a kind with x_i = 0 shows up as two bars side by side, or a bar at either end. With n = 3 and k = 5, the solution (2, 0, 3) becomes \star\star \mid \mid \star\star\star.

Theorem. Let n \ge 1 and k \ge 0 be integers. The number of solutions of x_1 + \cdots + x_n = k in natural numbers, and so the number of selections of k items from n kinds with repeats allowed, is

\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}

Proof. Let S be the set of solutions (x_1, \ldots, x_n) in \mathbb{N}^n with sum k, and let W be the set of rows of n + k - 1 symbols of which exactly k are stars and the other n - 1 are bars. Define f : S \to W by sending (x_1, \ldots, x_n) to x_1 stars, a bar, x_2 stars, a bar, and so on, ending with x_n stars. The row has x_1 + \cdots + x_n = k stars and n - 1 bars, so it has n + k - 1 symbols and lies in W.

Going back, define g : W \to S as follows. The n - 1 bars of a row cut it into n blocks of stars (before the first bar, between two bars, after the last bar), some of them possibly empty. Let x_i be the number of stars in block i. These are natural numbers that add to k, the number of stars, so g gives an element of S.

The block i of f(x_1, \ldots, x_n) holds exactly x_i stars, so g(f(x_1, \ldots, x_n)) = (x_1, \ldots, x_n). And a row of W is determined by the sizes of its blocks in order, since it is those blocks with a bar between each two, so f(g(w)) = w for every w in W. A function with a two-sided inverse is a bijection (One-to-one, onto and bijective functions), so S and W have the same number of elements.

A row in W is determined by which k of its n + k - 1 positions hold stars, the other positions holding bars. Choosing those positions is choosing a k-element subset of the n + k - 1 positions, which can be done in \binom{n + k - 1}{k} ways. Choosing the n - 1 bar positions instead gives the same number, \binom{n + k - 1}{n - 1}. \square

Day 1: positive solutions

If every kind must appear at least once, every x_i is a positive integer. Give one item of each kind first. What is left to choose is k - n items from the same n kinds, with no condition. In symbols, set y_i = x_i - 1. The map (x_1, \ldots, x_n) \mapsto (y_1, \ldots, y_n) sends positive solutions of x_1 + \cdots + x_n = k to natural-number solutions of y_1 + \cdots + y_n = k - n, and adding 1 back to each coordinate undoes it, so it is a bijection. For k \ge n the theorem then gives

\binom{n + (k - n) - 1}{k - n} = \binom{k - 1}{k - n} = \binom{k - 1}{n - 1}

positive solutions. For k < n there are none, since n positive integers add to at least n. The same count can be read straight off the stars: k stars in a row have k - 1 gaps between neighbors, and a positive solution puts its n - 1 bars in n - 1 different gaps (Exercise 16).

Day 2: lower bounds by substitution

A condition x_i \ge a_i is handled the same way. Give each kind its a_i items first, or in symbols set y_i = x_i - a_i. With A = a_1 + \cdots + a_n, the solutions of x_1 + \cdots + x_n = k with every x_i \ge a_i match one to one the natural-number solutions of y_1 + \cdots + y_n = k - A, so for k \ge A there are

\binom{n + k - A - 1}{n - 1}

of them, and for k < A there are none. The bounds may be any integers, negative ones included; a negative bound adds to what is left to share.

Day 2: the four basic counts

A choice of k from n raises two questions: does order matter, and are repeats allowed? The four answers give four counts (the no-repeat ones need k \le n), and the first step on a counting problem is to say which one it asks for.

	repeats	no repeats
ordered	n^k	P(n, k)
unordered	\dbinom{n + k - 1}{k}	\dbinom{n}{k}

The top row is the counting principle and permutations; the bottom right is combinations. Only the right column is linked by dividing by k!: k different items can be ordered in exactly k! ways. Two jelly donuts and one maple have only 3 orders, not 3! = 6, so n^k / k! is not the bottom left count (Exercise 17).

Worked examples

Example 1

Listing the solutions of a small equation

Find every solution of x_1 + x_2 + x_3 = 4 in natural numbers, and check the count against the theorem.

Solution

Sort by x_1. Once x_1 is fixed, x_2 runs from 0 to 4 - x_1 and x_3 is what is left, so x_1 = 4, 3, 2, 1, 0 allow 1, 2, 3, 4, 5 solutions:

(4, 0, 0);
(3, 1, 0), (3, 0, 1);
(2, 2, 0), (2, 1, 1), (2, 0, 2);
(1, 3, 0), (1, 2, 1), (1, 1, 2), (1, 0, 3);
(0, 4, 0), (0, 3, 1), (0, 2, 2), (0, 1, 3), (0, 0, 4).

That is 1 + 2 + 3 + 4 + 5 = 15 solutions. The theorem with n = 3 and k = 4 gives rows of 6 symbols, 4 stars and 2 bars, and \binom{6}{2} = 15. Three of the matches: (1, 2, 1) is \star \mid \star\star \mid \star, (0, 4, 0) is \mid \star\star\star\star \mid, and (0, 0, 4) is \mid \mid \star\star\star\star.

Example 2

A box of a dozen donuts

Ebo’s donut shop makes five kinds: glazed, chocolate, jelly, cinnamon and maple, and never runs out. How many different boxes of 12 donuts can a customer ask for, if two donuts of the same kind are alike and the order they go into the box does not matter?

Solution

A box is fixed by how many of each kind it holds, so it is a selection of k = 12 items from n = 5 kinds with repeats allowed. As a row it is 12 stars and 4 bars, 16 symbols in all. Figure 1 shows the box with 3 glazed, no chocolate, 4 jelly, 2 cinnamon and 3 maple.

Figure 1The box with 3 glazed, 0 chocolate, 4 jelly, 2 cinnamon and 3 maple donuts as 12 stars and 4 bars. The bars sit in positions 4, 5, 10 and 13.

The box is fixed by where the 4 bars go among the 16 positions, here 4, 5, 10, 13, so the number of boxes is

\binom{16}{4} = \frac{16 \cdot 15 \cdot 14 \cdot 13}{4 \cdot 3 \cdot 2 \cdot 1} = 1{,}820

Counting star positions instead gives \binom{16}{12}, the same number by the symmetry \binom{m}{r} = \binom{m}{m - r}.

Example 3

At least one of each kind

How many of the boxes in Example 2 hold at least one donut of every kind? How many positive integer solutions does x_1 + x_2 + x_3 + x_4 + x_5 = 12 have?

Solution

The two questions are the same question, with x_i the number of donuts of kind i.

Put one donut of each kind in the box first. That uses 5 donuts, and the other 7 may be any of the 5 kinds with no condition. So the boxes match the selections of 7 from 5 kinds, which are rows of 7 stars and 4 bars:

\binom{11}{4} = \frac{11 \cdot 10 \cdot 9 \cdot 8}{24} = 330

Check by the gaps: 12 stars in a row have 11 gaps between them, and a box with every kind present is a choice of 4 of those gaps for the bars, at most one bar per gap so that no block is empty. That is again \binom{11}{4} = 330. So 330 of the 1{,}820 boxes contain every kind.

Example 4

A fruit basket with lower bounds

A fruit basket holds 15 pieces chosen from apples, peaches, plums and kiwis, pieces of one kind being alike. (a) How many baskets have at least 2 of each kind? (b) How many have at least 2 of each kind and at least 4 plums?

Solution

Write a, p, m, w for the numbers of apples, peaches, plums and kiwis, so a + p + m + w = 15.

(a) The condition is a, p, m, w \ge 2. Set a' = a - 2 and so on. The new unknowns are natural numbers with

a' + p' + m' + w' = 15 - 8 = 7

and the shift is a bijection, so the number of baskets is the number of rows of 7 stars and 3 bars, \binom{10}{3} = 120. In words: put 2 of each kind in the basket, then choose the other 7 pieces freely.

(b) Now the bounds are 2, 2, 4, 2 with total A = 10, leaving 15 - 10 = 5 pieces to choose from 4 kinds:

\binom{5 + 4 - 1}{3} = \binom{8}{3} = 56

Example 5

Nondecreasing sequences

How many sequences (s_1, s_2, s_3) with terms in \{1, 2, 3, 4, 5\} satisfy s_1 \le s_2 \le s_3? Prove in general that the nondecreasing sequences of length k with terms in \{1, \ldots, n\} number \binom{n + k - 1}{k}.

Solution

Proof. Send a nondecreasing sequence (s_1, \ldots, s_k) to the selection that holds, for each j, as many items of kind j as there are terms equal to j. Going back, list the items of a selection in order of kind, smallest kind first: this gives a nondecreasing sequence, and it is the only nondecreasing arrangement of those items. Listing the selection made from a sequence gives the sequence back, and the selection made from a listing is the selection we started with, so the two maps are inverse bijections. The theorem counts the selections of k from n kinds. \square

With n = 5 and k = 3 there are \binom{7}{3} = 35 such sequences; for instance (2, 2, 5) is the selection with x = (0, 2, 0, 0, 1). For contrast, the strictly increasing ones s_1 < s_2 < s_3 use three different terms, so they are the 3-element subsets of \{1, \ldots, 5\}, and there are \binom{5}{3} = 10.

Example 6

Counting the monomials of a given degree

A monomial in x, y, z is a product x^a y^b z^c with a, b, c in \mathbb{N}, and its degree is a + b + c. How many monomials in x, y, z have degree 6? How many have degree at most 6?

Solution

A monomial of degree 6 is fixed by its exponents, a solution of a + b + c = 6 in natural numbers. So there are

\binom{6 + 3 - 1}{2} = \binom{8}{2} = 28

of them, one for each term of (x + y + z)^6 after like terms are collected.

For degree at most 6, the condition a + b + c \le 6 is not an equation. Add a slack variable d = 6 - (a + b + c), the amount by which the degree falls short of 6. Then d \in \mathbb{N} and a + b + c + d = 6, and each solution with a + b + c \le 6 gives exactly one d, while dropping d goes back. So the count is

\binom{6 + 4 - 1}{3} = \binom{9}{3} = 84

Check by adding over the degrees 0 to 6, using the first part with 6 replaced by each degree: 1 + 3 + 6 + 10 + 15 + 21 + 28 = 84.

Example 7

Four dice and the four counts

Four standard dice are rolled. Count (a) the outcomes when the dice are identical, so only the faces shown count; (b) the outcomes when the dice are red, blue, green and white; (c) the outcomes of (a) with four different faces; (d) the outcomes of (b) with four different faces.

Solution

The items are the k = 4 dice and the kinds are the n = 6 faces.

(a) With identical dice an outcome is how many dice show each face, so order is ignored and faces may repeat. It is a selection of 4 from 6 kinds:

\binom{6 + 4 - 1}{4} = \binom{9}{4} = 126

(b) Coloring the dice puts them in an order (red first, blue second, and so on), and faces may repeat, so each die has 6 faces: 6^4 = 1{,}296 outcomes.

(d) Order matters, no repeats: P(6, 4) = 6 \cdot 5 \cdot 4 \cdot 3 = 360.

These fill the table of four counts with n = 6, k = 4. In the right column 360 = 15 \cdot 4!, but 1{,}296 / 4! = 54 is not 126: \{1, 1, 1, 1\} comes from one colored roll, \{1, 2, 3, 4\} from 24.

Boundaries

Items of one kind are alike, and the kinds are told apart. If the k items are themselves different (twelve named customers each picking a kind), an outcome assigns a kind to each item and the count is n^k. If the kinds are not told apart (splitting 12 into parts with no labels on the parts), the count is a different one, of partitions of an integer, and stars and bars does not give it.

The supply must not run out. The theorem assumes at least k items of every kind are on hand, so that no x_i is capped. If the shop has only 3 jelly donuts, that is an upper bound, and upper bounds are the subject of the Inclusion-exclusion for three or more sets, and derangements.

Lower bounds need room. The shifted count \binom{n + k - A - 1}{n - 1} holds for k \ge A. For k < A there are no solutions, and the formula must not be used: its top entry n + k - A - 1 is then less than n - 1, and for A - k \ge n it is negative, which is not a count.

Equal counting is not equal likelihood. The 126 outcomes of Example 7 (a) are not equally likely; probabilities come from the 1{,}296 equally likely colored rolls.

Where this goes next

Upper bounds lead to the Inclusion-exclusion for three or more sets, and derangements, the next lesson. Identities such as \binom{n + k - 1}{k} = \binom{n + k - 2}{k} + \binom{n + k - 2}{k - 1} (the last kind used or not) are proved by counting one set in two ways in Combinatorial proof: counting one set two ways, after pascals-triangle-recurrence. The monomials of Example 6 are the terms of the multinomial expansion, which extends the binomial theorem.

Exercises

Day 1: stars and bars

Count the selections of k items from n kinds with repeats allowed for (a) n = 3, k = 7; (b) n = 6, k = 2; (c) n = 1, k = 9; (d) n = 4, k = 0.
Write the solution (2, 0, 3, 1) of x_1 + x_2 + x_3 + x_4 = 6 as stars and bars. Which solution of x_1 + x_2 + x_3 + x_4 = 5 is the row \mid \star\star\star \mid \mid \star\star?
List every selection of 2 items from the kinds p, q, r with repeats allowed, and compare with the theorem.
How many different half-dozen boxes (6 donuts) can be filled from 8 kinds of donut?
How many solutions in natural numbers does x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 5 have?
How many positive integer solutions does x_1 + x_2 + x_3 + x_4 + x_5 = 11 have?
How many fruit baskets of 12 pieces chosen from apples, peaches and plums contain all three kinds?

Day 2: bounds, other settings and the four counts

How many solutions does x_1 + x_2 + x_3 + x_4 + x_5 = 18 have with every x_i \ge 2?
How many integer solutions does x + y + z + w = 4 have with x, y, z, w \ge -2?
How many fruit baskets of 12 pieces chosen from apples, peaches and plums have at least 3 apples and at least 1 plum?
How many monomials of degree 4 are there in the five variables x_1, \ldots, x_5?
Three identical standard dice are rolled. How many outcomes are there? Sort them into those with all faces the same, exactly two the same, and all different, and check that the three counts add up.
How many strings of 4 digits, each from 0 to 9, have nondecreasing digits (such as 0337)? How many have strictly increasing digits?
Ebo’s shop now makes 9 kinds of donut. Say which of the four counts each question asks for, and answer it. (a) Buying one donut on each of Monday, Tuesday and Wednesday, how many records of which kind was bought on which day are possible? (b) How many tasting plates of 3 different kinds? (c) How many boxes of 3 donuts? (d) In how many ways can a customer rank a first, second and third favorite kind?
How many solutions in natural numbers does x_1 + x_2 + x_3 \le 10 have?

Reasoning

Prove that the positive integer solutions of x_1 + \cdots + x_n = k, for k \ge n \ge 1, match one to one the ways to choose n - 1 of the k - 1 gaps between k stars in a row. Conclude that there are \binom{k - 1}{n - 1} of them.
Explain why n^k / k! is not the number of selections of k from n kinds with repeats allowed, using n = 2, k = 2 and also n = 3, k = 2.
Prove that the number of selections of k from n kinds equals the number of selections of n - 1 from k + 1 kinds, by swapping the roles of stars and bars. Check it with n = 3 and k = 5.
Three fair standard dice are rolled. Find the probability that the faces shown are \{1, 1, 1\}, \{1, 1, 2\} and \{1, 2, 3\}, and explain why none of them is \displaystyle \frac{1}{56}, though Exercise 12 found 56 outcomes.
For a nondecreasing sequence (s_1, \ldots, s_k) with terms in \{1, \ldots, n\}, set t_i = s_i + (i - 1). Prove that this is a bijection onto the strictly increasing sequences of length k with terms in \{1, \ldots, n + k - 1\}, and use it to give a second proof of the theorem. Show the pairing for n = 3, k = 2.
Find the number of solutions of x_1 + x_2 + x_3 = k in integers with each x_i \ge 5, as a formula in k, and say for which k it holds. Evaluate it for k = 20 and k = 12.

Answers

(a) \binom{9}{7} = 36. (b) \binom{7}{2} = 21. (c) \binom{9}{9} = 1: all nine items are of the one kind. (d) \binom{3}{0} = 1: the empty selection.
\star\star \mid \mid \star\star\star \mid \star. The row has blocks of 0, 3, 0 and 2 stars, so it is (0, 3, 0, 2).
pp, pq, pr, qq, qr, rr: six selections, and \binom{3 + 2 - 1}{2} = \binom{4}{2} = 6.
k = 6, n = 8: \binom{13}{6} = 1{,}716.
\binom{5 + 6 - 1}{5} = \binom{10}{5} = 252.
Give one to each, leaving 6 for 5 unknowns: \binom{10}{4} = 210, which is \binom{k - 1}{n - 1} with k = 11, n = 5.
One of each kind first leaves 9 pieces from 3 kinds: \binom{11}{2} = 55.
Giving 2 to each uses 10, leaving 8: \binom{8 + 4}{4} = \binom{12}{4} = 495.
Set x' = x + 2 and so on. Then x', y', z', w' \in \mathbb{N} and x' + y' + z' + w' = 4 + 8 = 12, so there are \binom{15}{3} = 455.
Bounds 3, 0, 1 use 4 pieces, leaving 8 from 3 kinds: \binom{10}{2} = 45.
Exponents with e_1 + \cdots + e_5 = 4: \binom{8}{4} = 70.
\binom{8}{3} = 56. All the same: 6. Exactly two the same: 6 choices of the pair’s face and 5 of the other, 6 \cdot 5 = 30. All different: \binom{6}{3} = 20. And 6 + 30 + 20 = 56.
A nondecreasing string is a selection of 4 from the 10 digits, listed in order: \binom{13}{4} = 715. A strictly increasing one is a 4-element set of digits: \binom{10}{4} = 210.
(a) Order matters (the days differ), repeats allowed: 9^3 = 729. (b) Order ignored, no repeats: \binom{9}{3} = 84. (c) Order ignored, repeats allowed: \binom{11}{3} = 165. (d) Order matters, no repeats: 9 \cdot 8 \cdot 7 = 504.
A slack variable x_4 = 10 - (x_1 + x_2 + x_3) in \mathbb{N} turns it into x_1 + x_2 + x_3 + x_4 = 10: \binom{13}{3} = 286.
Send a positive solution to the set of gaps that get a bar when x_1 stars, a bar, x_2 stars and so on are written: the bars fall after star x_1, after star x_1 + x_2, ..., after star x_1 + \cdots + x_{n-1}. These are n - 1 different gaps, because each x_i \ge 1 makes the partial sums strictly increase, and they lie between 1 and k - 1. Conversely, n - 1 chosen gaps cut the k stars into n blocks, none empty, and the block sizes form a positive solution. The two maps undo each other, so this is a bijection, and the gaps can be chosen in \binom{k - 1}{n - 1} ways.
With n = 2, k = 2 it gives 4/2 = 2, but there are 3 selections: aa, ab, bb. With n = 3, k = 2 it gives 9/2, not even an integer, against the true 6. Dividing by k! assumes each selection appears in exactly k! orders, which holds only when its items are all different: ab has two orders but aa has one.
A selection of k from n kinds is a row of k stars and n - 1 bars. Swapping every star for a bar and every bar for a star is its own inverse, so it is a bijection onto rows of n - 1 stars and k bars, which are the selections of n - 1 from k + 1 kinds. With n = 3, k = 5: \binom{7}{5} = 21 and \binom{6 + 2 - 1}{2} = \binom{7}{2} = 21.
Tell the dice apart by color; the 6^3 = 216 colored rolls are equally likely. \{1, 1, 1\} comes from 1 of them, so \displaystyle \frac{1}{216}; \{1, 1, 2\} from 3 (the 2 on any one of the three dice), so \displaystyle \frac{3}{216} = \frac{1}{72}; \{1, 2, 3\} from 3! = 6, so \displaystyle \frac{6}{216} = \frac{1}{36}. The 56 unordered outcomes come from different numbers of rolls, so they are not equally likely.
Since s_{i+1} \ge s_i, t_{i+1} = s_{i+1} + i \ge s_i + i > t_i, and 1 \le t_i \le n + (k - 1), so t is strictly increasing in \{1, \ldots, n + k - 1\}. Conversely, for strictly increasing t, set s_i = t_i - (i - 1): then s_{i+1} - s_i = t_{i+1} - t_i - 1 \ge 0, s_1 = t_1 \ge 1 and s_k = t_k - k + 1 \le n. The maps undo each other. Strictly increasing sequences are k-element subsets of \{1, \ldots, n + k - 1\}, so there are \binom{n + k - 1}{k}, and Example 5 matches these sequences with the selections. For n = 3, k = 2: (1,1), (1,2), (1,3), (2,2), (2,3), (3,3) go to (1,2), (1,3), (1,4), (2,3), (2,4), (3,4), six of each, and \binom{4}{2} = 6.
Giving 5 to each leaves k - 15, so for k \ge 15 there are \binom{k - 15 + 2}{2} = \binom{k - 13}{2} solutions. For k \le 14 there are none, since the sum is at least 15. For k = 20: \binom{7}{2} = 21. For k = 12: 0.