Sections 6.1 – 6.3
What Repetition Means and How It Changes the Count
Why Repetition Matters · Ordered Sequences · Unordered Selections
Section 6.1
Why Repetition Changes Counting
In Chapter 3, when you counted permutations, each element of the set appeared at most once in any arrangement. Choosing the first position excluded that element from all later positions. In Chapter 4, when you counted combinations, a subset could not contain any element more than once — a subset either includes an element or it does not. In both cases, repetition was implicitly forbidden.
Many real situations work differently. When you choose a 4-digit PIN, the digits 0 through 9 are all available at every position, so a PIN like 7775 is perfectly valid. When a bakery fills a mixed-dozen box, a customer might choose 4 croissants, 4 muffins, and 4 scones — the same type repeated multiple times. When a network transmits a data packet of 32 bits, each bit is independently 0 or 1, and either value can appear in any position any number of times.
In each of these settings, the same object or type can be selected more than once. This is called selection with repetition allowed, or simply repetition-allowed selection. The counting methods change significantly when repetition is allowed, and the change goes in the direction you might expect: more arrangements or selections become available, so the count is typically larger.
The key question at the start of any counting problem is always: does the situation allow the same item to be chosen more than once? The answer determines which method applies. This chapter develops the tools for the repetition-allowed case.
| Setting | Repetition? | Method | Count (choosing 3 from 4 types) |
|---|
| Ordered, no repetition | No | Permutation | \(P(4,3) = 24\) |
| Ordered, repetition allowed | Yes | Product rule | \(4^3 = 64\) |
| Unordered, no repetition | No | Combination | \(\binom{4}{3} = 4\) |
| Unordered, repetition allowed | Yes | Combinations with repetition | \(\binom{6}{3} = 20\) |
The Four Cases of Selection
Every selection problem falls into one of four cases based on two binary questions: Does order matter? and Is repetition allowed? The table above summarizes all four. Knowing which case applies is always the first step in any counting problem.
Section 6.2
Selecting with Repetition — Ordered Sequences
The simplest repetition-allowed case involves ordered sequences. When you form a sequence of \(k\) positions and each position can be filled with any of \(n\) types independently — including the same type as another position — the count follows directly from the product rule: there are \(n\) choices for the first position, \(n\) for the second, and so on through the \(k\)-th. The total count is \(n^k\).
This is already familiar from Chapter 2. When you counted passwords with repetition allowed, or counted binary strings, you used \(n^k\). The new content in this chapter is the corresponding unordered version — counting selections where order does not matter but repetition is still allowed.
Ordered Selection with Repetition
The number of ordered sequences of length \(k\) chosen from \(n\) types, with repetition allowed, is \(n^k\).
Example 6.2.1
Counting PINs and passwords
- ProblemA 4-digit PIN uses digits 0 through 9. How many PINs are possible if digits may repeat?
- ThinkEach of the 4 positions has 10 choices independently. The positions are ordered (1234 is different from 4321), and repetition is allowed.
- Count10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000
- CheckPINs range from 0000 to 9999. There are 10,000 values. ✓
- InterpretThere are 10,000 possible 4-digit PINs when repetition is allowed. Compare this with no-repetition: \(P(10,4) = 5{,}040\). Repetition roughly doubles the count here.
Answer: \(10^4 = 10{,}000\) PINs.
Example 6.2.2
Ice cream scoops in a cone — ordered
- ProblemAn ice cream shop has 6 flavors. A triple-scoop cone has 3 scoops, ordered from bottom to top. Repetition is allowed. How many triple-scoop cones are possible?
- ThinkEach scoop is chosen independently from 6 flavors. The positions are distinct (bottom, middle, top), so order matters. Repetition is allowed.
- Count6^3 = 216
- InterpretThere are 216 ordered triple-scoop cones. A cone with chocolate on bottom, vanilla in the middle, and chocolate on top is different from one with vanilla on bottom, chocolate in the middle, and chocolate on top.
Answer: \(6^3 = 216\) ordered triple-scoop cones.
- A combination lock has 3 wheels, each showing digits 0–9. How many combinations are possible?
- A license plate has 3 letters followed by 3 digits. How many plates are possible if repetition is allowed?
- A binary string of length 10 is a sequence of 0s and 1s. How many such strings exist?
- A quiz has 5 true/false questions. How many answer sequences are possible?
- A restaurant offers 4 soups. How many ordered sequences of 3 soups (a soup course for 3 days) are possible, with repetition allowed?
- Compare the count for Problem 5 with the count if repetition is not allowed.
Section 6.3
Combinations with Repetition
Now suppose order does not matter, but repetition is still allowed. You are choosing a multiset of \(k\) objects from \(n\) types: a collection in which elements may repeat, and in which two collections are the same if they contain exactly the same elements with exactly the same multiplicities, regardless of the order in which they were chosen.
The ice cream example illustrates this: a bowl with 2 chocolate scoops and 1 vanilla scoop is the same bowl regardless of which order the scoops were placed in the bowl. You want to count how many bowls are possible — not sequences, but unordered collections.
The formula for this count is:
Combinations with Repetition (Multiset Formula)
The number of unordered selections of size \(k\) from \(n\) types, with repetition allowed, is:
\[\binom{n + k - 1}{k}\]
This is sometimes written as \(\binom{n+k-1}{n-1}\) (equivalent by symmetry). It is also called the number of multisets of size \(k\) from \(n\) types.
The derivation of this formula is the subject of Section 6.4, where stars and bars makes the reasoning transparent. For now, it is worth noting that the formula outputs a binomial coefficient — specifically, a combination from a set of size \(n + k - 1\), choosing \(k\) — even though the problem looks quite different from a simple subset problem. Understanding why the formula takes this form is the central insight of this chapter.
Example 6.3.1
Counting ice cream bowls — unordered
- ProblemAn ice cream shop has 6 flavors. A bowl contains 4 scoops, chosen with repetition allowed and without regard to order. How many bowls are possible?
- RepresentHere \(n = 6\) (types) and \(k = 4\) (scoops). The selection is unordered with repetition.
- Count\binom{6 + 4 - 1}{4} = \binom{9}{4} = 126
- CheckWith no repetition: \(\binom{6}{4} = 15\). With repetition, 126 is plausibly larger. ✓
- InterpretThere are 126 different 4-scoop bowls (unordered, repetition allowed) from 6 flavors. Compare with 15 bowls if no flavor can repeat.
Answer: \(\binom{9}{4} = 126\) bowls.
Example 6.3.2
Opening question — muffins
- ProblemA bakery offers 5 types of muffins. You buy a bag of 8, choosing with repetition allowed and without regard to order. How many different bags are possible?
- Represent\(n = 5\) types, \(k = 8\) muffins. Unordered, repetition allowed.
- Count\binom{5 + 8 - 1}{8} = \binom{12}{8} = \binom{12}{4} = 495
- InterpretThere are 495 different bags of 8 muffins. This resolves the opening question of the chapter.
Answer: \(\binom{12}{8} = 495\) bags.
Student Warning — Which \(n\) and \(k\)?
In the formula \(\binom{n+k-1}{k}\), the variable \(n\) is the number of types (flavors, categories, options) and \(k\) is the number of objects being selected. A common error is swapping these. Always identify: How many types? How many items chosen? Then apply the formula carefully.
- Choose 3 items from 5 types, unordered, repetition allowed.
- Choose 6 items from 4 types, unordered, repetition allowed.
- A candy store has 8 types of candy. You buy a bag of 5. How many bags?
- A bookstore has 3 genres. You choose 4 books, repetition of genre allowed. How many genre combinations?
- Verify Example 6.3.1 by listing all 4-scoop bowls from 2 flavors (A, B). Then apply the formula with \(n=2, k=4\).
- Compare \(\binom{n+k-1}{k}\) and \(\binom{n}{k}\) for \(n=5, k=3\). Which is larger? Why does this make sense?
Sections 6.4 – 6.8
Stars and Bars: Encoding Repetition as a Combinatorial Structure
Stars and Bars · Nonnegative Solutions · Positive Solutions · Minimums · Upper Bounds
Section 6.4
Stars and Bars
The formula \(\binom{n+k-1}{k}\) appears by magic if you only read Section 6.3. Stars and bars makes it inevitable. The idea is to represent any unordered selection with repetition as a sequence of symbols — stars and bars — and then count how many distinct sequences are possible.
Imagine you are distributing \(k\) identical objects (the "stars," written ★) among \(n\) labeled categories (such as flavors, types, or groups). You will represent the distribution by listing the stars for each category in order, and placing \(n - 1\) vertical bars (the "bars," written |) between the categories to show where one category ends and the next begins.
Diagram Description — Stars and Bars Encoding
To illustrate a distribution of \(k\) stars among \(n\) categories, draw a row of stars and bars on a single line. The bars divide the row into \(n\) sections — one section per category. The number of stars in each section is the count assigned to that category. For example, with \(n = 3\) categories and \(k = 5\) objects:
★ ★ | ★ | ★ ★ means: Category 1 gets 2, Category 2 gets 1, Category 3 gets 2.
Any arrangement of \(k\) stars and \(n-1\) bars in a row of \(k + n - 1\) positions represents a valid distribution. Counting these arrangements is the same as counting which \(k\) of the \(k + n - 1\) positions are stars — a combination problem.
The key observation is: every distribution corresponds to exactly one sequence of stars and bars, and every sequence of stars and bars corresponds to exactly one distribution. This one-to-one correspondence means the number of distributions equals the number of distinct sequences.
A sequence consists of \(k\) stars and \(n-1\) bars arranged in a row of \(k + (n-1) = n + k - 1\) positions. The sequence is completely determined by choosing which \(k\) of the \(n + k - 1\) positions are stars (the bars fill the rest). The number of ways to choose those positions is:
Stars and Bars Formula — Derived
The number of ways to distribute \(k\) identical objects among \(n\) labeled categories (with any category possibly receiving zero objects) is:
\[\binom{n + k - 1}{k} = \binom{n+k-1}{n-1}\]
This is exactly the combinations-with-repetition formula. Stars and bars is not a separate technique — it is the explanation of why the formula is a binomial coefficient.
Example 6.4.1
Encoding a selection as stars and bars
- ProblemYou are choosing 5 muffins from 3 types (blueberry, bran, chocolate). List all stars-and-bars sequences and count them.
- Represent\(k = 5\) stars, \(n = 3\) categories means \(n - 1 = 2\) bars. Each sequence has \(5 + 2 = 7\) positions. The sequence is determined by placing the 2 bars among the 7 positions.
- Count\binom{7}{2} = 21
- VerifyBy formula: \(\binom{3+5-1}{5} = \binom{7}{5} = \binom{7}{2} = 21\). ✓
- InterpretSome example encodings: ★★★★★ | | means (5,0,0) — five blueberry, none of the others. ★★ | ★ | ★★ means (2,1,2). | ★★★★★ | means (0,5,0).
Answer: 21 different selections of 5 muffins from 3 types.
Example 6.4.2
Translating a word problem into stars and bars
- ProblemA teacher wants to distribute 7 identical gold star stickers among 4 students. Each student may receive any number of stickers, including zero. How many distributions are possible?
- RepresentThe stickers are identical (stars), the students are distinct categories (labels). \(k = 7\) stickers, \(n = 4\) students.
- Count\binom{4 + 7 - 1}{7} = \binom{10}{7} = \binom{10}{3} = 120
- InterpretThere are 120 ways to distribute 7 identical stickers among 4 students, allowing any student to receive zero or more stickers.
Answer: \(\binom{10}{3} = 120\) distributions.
How to Set Up Stars and Bars
Step 1: Identify \(k\) (the total number of objects to distribute or choose) and \(n\) (the number of categories or types). Step 2: Confirm that the categories are distinct (labeled) and that each may receive zero or more objects. Step 3: Apply \(\binom{n+k-1}{k}\). If minimum requirements apply, reduce to this form first using the method in Section 6.7.
- Draw all stars-and-bars sequences for distributing 4 identical items among 2 categories. Verify the count with the formula.
- A vending machine has 5 product slots. A distributor loads 10 identical bottles among the 5 slots (any slot may be empty). How many load arrangements are possible?
- A teacher distributes 6 identical bookmarks among 3 students. How many ways?
- How many ways can you place 8 identical marbles into 4 distinct jars, with no restriction on how many go in each jar?
- Explain in your own words why the number of stars-and-bars sequences for \(k\) stars and \(n-1\) bars equals \(\binom{n+k-1}{k}\).
Section 6.5
Nonnegative Integer Solutions
Stars and bars has a direct algebraic translation. Distributing \(k\) identical objects among \(n\) distinct categories is the same as counting the number of nonnegative integer solutions to the equation:
\(x_1 + x_2 + \cdots + x_n = k\), where each \(x_i \geq 0\).
Here \(x_i\) is the number of objects in category \(i\). The requirement \(x_i \geq 0\) means each category may receive zero or more. This is the stars-and-bars setup with no minimum restrictions.
Counting Nonnegative Integer Solutions
The number of nonnegative integer solutions to \(x_1 + x_2 + \cdots + x_n = k\) is:
\[\binom{n + k - 1}{k}\]
Example 6.5.1
Counting nonnegative solutions to a sum equation
- ProblemHow many solutions in nonnegative integers does \(x_1 + x_2 + x_3 = 10\) have?
- Represent\(n = 3\) variables, \(k = 10\). Each variable is a nonnegative integer. Stars and bars applies directly.
- Count\binom{3 + 10 - 1}{10} = \binom{12}{10} = \binom{12}{2} = 66
- CheckSome solutions: (10,0,0), (0,10,0), (0,0,10), (5,5,0), (3,3,4), and so on. Each is a valid nonnegative solution and is counted once. ✓
Answer: 66 nonnegative integer solutions.
Example 6.5.2
A data allocation problem
- ProblemA server has 12 identical memory units to allocate to 4 processes. Each process may receive any nonnegative number of units. How many allocations are possible?
- RepresentThis is equivalent to counting nonnegative integer solutions to \(x_1 + x_2 + x_3 + x_4 = 12\). Here \(n = 4\) and \(k = 12\).
- Count\binom{4 + 12 - 1}{12} = \binom{15}{12} = \binom{15}{3} = \frac{15 \cdot 14 \cdot 13}{6} = 455
Answer: 455 allocations.
- \(x_1 + x_2 = 8\), \(x_i \geq 0\)
- \(x_1 + x_2 + x_3 = 6\), \(x_i \geq 0\)
- \(x_1 + x_2 + x_3 + x_4 = 5\), \(x_i \geq 0\)
- \(a + b + c + d + e = 9\), each \(\geq 0\)
- Distribute 10 identical pens among 3 teachers, with each teacher possibly receiving zero pens.
- How many ways can a total score of 15 points be achieved by 5 players if each player's score is a nonnegative integer?
Section 6.6
Positive Integer Solutions
When every variable must be at least 1 — that is, every category must receive at least one object — the nonnegative-solution formula no longer applies directly. The modified condition is:
\(x_1 + x_2 + \cdots + x_n = k\), where each \(x_i \geq 1\).
The strategy is a substitution. Let \(y_i = x_i - 1\) for each \(i\). Since \(x_i \geq 1\), we have \(y_i \geq 0\). Substituting:
\((y_1 + 1) + (y_2 + 1) + \cdots + (y_n + 1) = k\)
\(y_1 + y_2 + \cdots + y_n = k - n\)
This is now a nonnegative-solution equation with the same number of variables, but with a reduced right-hand side of \(k - n\). The number of solutions is \(\binom{n + (k-n) - 1}{k - n} = \binom{k - 1}{k - n} = \binom{k-1}{n-1}\).
Counting Positive Integer Solutions
The number of positive integer solutions (each variable \(\geq 1\)) to \(x_1 + x_2 + \cdots + x_n = k\) is:
\[\binom{k - 1}{n - 1}\]
This also counts the number of ways to write \(k\) as an ordered sum of \(n\) positive integers — called the number of compositions of \(k\) into \(n\) parts.
Example 6.6.1
Counting positive integer solutions
- ProblemHow many solutions in positive integers does \(x_1 + x_2 + x_3 = 10\) have?
- ThinkEach variable must be at least 1. Substitute \(y_i = x_i - 1\). The equation becomes \(y_1 + y_2 + y_3 = 7\) with each \(y_i \geq 0\).
- Count\binom{3 + 7 - 1}{7} = \binom{9}{7} = \binom{9}{2} = 36Or directly: \(\binom{k-1}{n-1} = \binom{9}{2} = 36\).
- CheckCompare with Example 6.5.1: 66 nonnegative solutions vs. 36 positive solutions. Requiring each variable to be at least 1 reduces the count. ✓
Answer: 36 positive integer solutions.
Example 6.6.2
Compositions of an integer
- ProblemIn how many ways can 8 be written as an ordered sum of 3 positive integers?
- ThinkAn ordered sum of 3 positive integers summing to 8 is a solution to \(x_1 + x_2 + x_3 = 8\) with each \(x_i \geq 1\). This is a composition of 8 into 3 parts.
- Count\binom{8 - 1}{3 - 1} = \binom{7}{2} = 21
- InterpretSome examples: \(1+1+6\), \(1+6+1\), \(6+1+1\) are three distinct compositions. \(3+3+2\) and \(2+3+3\) are different. There are 21 in total.
Answer: \(\binom{7}{2} = 21\) compositions.
- \(x_1 + x_2 = 9\), each \(x_i \geq 1\)
- \(x_1 + x_2 + x_3 = 7\), each \(x_i \geq 1\)
- \(x_1 + x_2 + x_3 + x_4 = 12\), each \(x_i \geq 1\)
- How many compositions of 10 into 4 parts exist?
- A principal distributes 9 achievement awards among 3 classes, ensuring each class gets at least 1. How many distributions?
- Explain why the formula for positive solutions is \(\binom{k-1}{n-1}\) and not \(\binom{k-1}{n}\).
Section 6.7
Minimum Requirements
Problems often specify that each variable must be at least some number greater than 0 or 1. For example: "each team must receive at least 2 players," or "each variable is at least 3." This is a minimum requirement, and it is handled by the same substitution idea as Section 6.6 — but generalized to arbitrary minimums.
Suppose the constraint is \(x_i \geq m_i\) for each \(i\), where \(m_i\) is the minimum for variable \(i\). Let \(y_i = x_i - m_i\), so \(y_i \geq 0\). Substituting into \(x_1 + x_2 + \cdots + x_n = k\) gives:
\(y_1 + y_2 + \cdots + y_n = k - (m_1 + m_2 + \cdots + m_n)\)
If the right-hand side is nonnegative, this is a standard nonnegative-solution problem and stars and bars applies. If the right-hand side is negative, there are no solutions (the minimums exceed the total).
Minimum Requirements — Strategy
Given \(x_1 + x_2 + \cdots + x_n = k\) with each \(x_i \geq m_i\):
1. Substitute \(y_i = x_i - m_i\) for each \(i\). Now each \(y_i \geq 0\).
2. The equation becomes \(y_1 + y_2 + \cdots + y_n = k - M\), where \(M = \sum m_i\).
3. If \(k - M \geq 0\), apply stars and bars: the count is \(\binom{n + (k-M) - 1}{k-M}\).
4. If \(k - M < 0\), there are no solutions.
Example 6.7.1
Distribution with minimum requirements
- ProblemA committee must consist of 12 people divided among 4 departments, with each department represented by at least 2 people. How many distributions are possible?
- RepresentEquation: \(x_1 + x_2 + x_3 + x_4 = 12\), each \(x_i \geq 2\). Let \(y_i = x_i - 2\), so each \(y_i \geq 0\).
- Reducey_1 + y_2 + y_3 + y_4 = 12 - 4(2) = 12 - 8 = 4
- Count\binom{4 + 4 - 1}{4} = \binom{7}{4} = \binom{7}{3} = 35
- CheckWithout the minimum-2 constraint, the count would be \(\binom{4+12-1}{12} = \binom{15}{12} = 455\). With the constraint, 35 is plausibly smaller. ✓
Answer: 35 distributions.
Example 6.7.2
Different minimums for each variable
- ProblemCount nonnegative integer solutions to \(x_1 + x_2 + x_3 = 15\) where \(x_1 \geq 3\), \(x_2 \geq 1\), and \(x_3 \geq 0\).
- RepresentLet \(y_1 = x_1 - 3\), \(y_2 = x_2 - 1\), \(y_3 = x_3 - 0 = x_3\). Each \(y_i \geq 0\).
- Reducey_1 + y_2 + y_3 = 15 - 3 - 1 - 0 = 11
- Count\binom{3 + 11 - 1}{11} = \binom{13}{11} = \binom{13}{2} = 78
Answer: 78 solutions.
- \(x_1 + x_2 + x_3 = 12\), each \(x_i \geq 2\)
- \(a + b + c + d = 20\), each variable \(\geq 3\)
- \(x_1 + x_2 + x_3 = 10\), \(x_1 \geq 4\), \(x_2 \geq 2\), \(x_3 \geq 0\)
- Distribute 15 identical prizes among 5 winners so each receives at least 1. How many ways?
- A store must stock at least 3 units of each of its 4 products. If 20 units are available total, how many stocking arrangements are possible?
- Why does the minimum-requirement strategy fail if the total of the minimums exceeds \(k\)?
Section 6.8
Upper Bounds and Restrictions
Sometimes a constraint works in the opposite direction: each variable may receive at most some number of objects. For example: "no player can be on more than 3 teams," or "each bin can hold at most 4 items." These are upper-bound constraints, and they are harder to handle directly than lower-bound constraints.
The standard approach for upper bounds is complementary counting: count all solutions without the upper-bound constraint, then subtract the solutions that violate the constraint. This is a preview of inclusion-exclusion, which Chapter 7 develops in full generality. For now, the approach works cleanly when at most one variable can violate the bound at a time.
Example 6.8.1
Upper bound on one variable
- ProblemCount the number of nonnegative integer solutions to \(x_1 + x_2 + x_3 = 10\) with \(x_1 \leq 4\).
- ThinkUse complementary counting: count all nonnegative solutions, then subtract those where \(x_1 \geq 5\).
- All solutions\binom{3 + 10 - 1}{10} = \binom{12}{10} = 66
- Violating solutionsIf \(x_1 \geq 5\), let \(y_1 = x_1 - 5 \geq 0\). The equation becomes \(y_1 + x_2 + x_3 = 5\):\binom{3 + 5 - 1}{5} = \binom{7}{5} = 21
- Subtract66 - 21 = 45
- InterpretThere are 45 nonnegative solutions with \(x_1 \leq 4\).
Answer: 45 solutions.
Student Warning — Upper Bounds Require Inclusion-Exclusion
When multiple variables have upper bounds and both can be violated simultaneously, simple complementary counting can over-subtract. For example, if \(x_1 \leq 3\) and \(x_2 \leq 3\), solutions where both \(x_1 \geq 4\) and \(x_2 \geq 4\) are subtracted twice. The fix is inclusion-exclusion, which adds back what was subtracted twice. Chapter 7 covers this case in full. For this chapter, problems with a single upper-bound variable are handled with the complementary counting approach above.
- \(x_1 + x_2 + x_3 = 8\), \(x_1 \leq 3\), all \(x_i \geq 0\)
- \(x_1 + x_2 + x_3 + x_4 = 15\), \(x_1 \leq 6\), all \(x_i \geq 0\)
- Distribute 12 identical books among 3 shelves, with the first shelf holding at most 4 books.
- A teacher assigns 10 identical gold stars to 3 students, with one student allowed to receive at most 3. How many ways?
Sections 6.9 – 6.12
Distribution Problems: Objects, Boxes, and Real-World Models
Identical Objects · Distinct Objects · Boxes and Language · Applications
Section 6.9
Distributing Identical Objects
The distribution framework generalizes the stars-and-bars setting. In a distribution problem, you have a collection of objects and a set of groups (bins, boxes, or categories), and you want to count the number of ways to place the objects into the groups. The count depends critically on two factors: whether the objects are identical or distinct, and whether the groups are identical or distinct.
The simplest case — identical objects into distinct bins — is exactly what stars and bars computes. The objects are indistinguishable (like identical balls), and the bins are labeled (distinct). The count of distributions is the count of nonnegative integer solutions to a sum equation, which equals \(\binom{n+k-1}{k}\).
| Setting | Formula | Example |
|---|
| Identical objects, distinct bins, any bin may be empty | \(\binom{n+k-1}{k}\) | 12 identical coins into 4 labeled jars |
| Identical objects, distinct bins, no bin may be empty | \(\binom{k-1}{n-1}\) | 12 identical coins into 4 jars, each with at least 1 |
| Identical objects, identical bins | Partition numbers (beyond this chapter) | 12 coins into 4 unlabeled piles |
Example 6.9.1
Identical objects, distinct bins — both cases
- Problem(a) In how many ways can 9 identical apples be placed in 4 labeled baskets, with any basket possibly empty? (b) In how many ways if each basket must have at least 1 apple?
- Part (a)Nonnegative solutions to \(x_1+x_2+x_3+x_4 = 9\):\binom{4+9-1}{9} = \binom{12}{9} = \binom{12}{3} = 220
- Part (b)Positive solutions to \(x_1+x_2+x_3+x_4 = 9\):\binom{9-1}{4-1} = \binom{8}{3} = 56
- Check56 < 220. Requiring each basket to have at least one apple reduces the count. ✓
Answer: (a) 220 ways. (b) 56 ways.
Section 6.10
Distributing Distinct Objects — An Introduction
When the objects are distinguishable — each one is different — the count changes dramatically. Now it matters not only how many objects go into each bin, but which specific objects they are. For distinct objects into distinct bins, the count of distributions is found by assigning each object independently to one of the \(n\) bins. Since each of the \(k\) objects has \(n\) choices, the total count is:
Distinct Objects into Distinct Bins
The number of ways to distribute \(k\) distinct objects among \(n\) distinct bins (any bin may be empty) is \(n^k\).
This is the same as the count of functions from a set of \(k\) elements to a set of \(n\) elements — each object is mapped to a bin.
Example 6.10.1
Assigning students to project groups
- ProblemA class of 6 students is to be assigned to 3 distinct project groups. Any group may have any number of students (including zero). How many assignments are possible?
- ThinkThe students are distinct (each is a different person). The groups are distinct (labeled Group 1, 2, 3). Each student independently chooses a group.
- Count3^6 = 729
- InterpretThere are 729 ways. Compare this with distributing 6 identical objects among 3 bins: \(\binom{8}{6} = 28\). The distinctness of the students increases the count enormously.
Answer: \(3^6 = 729\) assignments.
Student Warning — Identical vs. Distinct Objects
The difference between identical and distinct objects is the most common source of error in distribution problems. Ask: would swapping two objects create a different distribution? If yes (the objects are distinct), use \(n^k\) or a related method. If no (the objects are identical), use stars and bars or \(\binom{n+k-1}{k}\). Never mix these methods.
Section 6.11
Boxes and Objects Language
Distribution problems can be confusing because the same situation can be described using many different words: bins, boxes, groups, categories, slots, teams, shelves, jars, piles. The key is not the vocabulary but the structure: what matters is whether objects are identical or distinct, and whether bins are identical or distinct. Together, these two binary questions produce four cases.
| Objects | Bins | Method | Count |
|---|
| Identical | Distinct | Stars and bars | \(\binom{n+k-1}{k}\) (any bin may be empty) |
| Identical | Identical | Integer partitions | Partition numbers (beyond this chapter) |
| Distinct | Distinct | Product rule (functions) | \(n^k\) |
| Distinct | Identical | Set partitions / Stirling numbers | Stirling numbers (beyond this chapter) |
This chapter focuses on the two tractable cases with non-calculus tools: identical objects into distinct bins (stars and bars), and distinct objects into distinct bins (\(n^k\)). The other two cases involve partition numbers and Stirling numbers of the second kind, which are topics in advanced combinatorics. They are mentioned here so students understand the full landscape of distribution problems, even if the tools to count them fully appear later.
How to Classify a Distribution Problem
Step 1 — Objects: Would swapping two objects create a new distribution? Yes → distinct objects. No → identical objects.
Step 2 — Bins: Would moving an object from one bin to another create a new distribution? Yes → distinct bins. No → identical bins.
Step 3 — Choose the method from the table above.
Section 6.12
Distribution Problems in Scheduling, Inventory, and Data
Distribution problems appear throughout applied mathematics, computer science, operations research, and data management. Recognizing a real-world situation as a distribution problem — and identifying the correct model — is the central skill of this section.
Example 6.12.1
Scheduling — assigning tasks to workers
- ProblemA project manager has 8 distinct tasks to assign to 3 distinct team members. Each task goes to exactly one member. How many assignments are possible?
- ClassifyTasks are distinct. Team members are distinct. Any member may receive any number of tasks (including zero).
- Count3^8 = 6{,}561
Answer: 6,561 possible assignments.
Example 6.12.2
Inventory — stocking identical items
- ProblemA warehouse receives 20 identical boxes of the same product and must distribute them among 5 labeled storage bays, with each bay receiving at least 2 boxes. How many distributions are possible?
- ClassifyBoxes are identical. Bays are distinct (labeled). Each bay must receive at least 2.
- ReduceLet \(y_i = x_i - 2\) for each bay. Then \(y_1 + y_2 + y_3 + y_4 + y_5 = 20 - 10 = 10\), each \(y_i \geq 0\).
- Count\binom{5 + 10 - 1}{10} = \binom{14}{10} = \binom{14}{4} = 1{,}001
Answer: 1,001 distributions.
Example 6.12.3
Data allocation — memory pages
- ProblemAn operating system allocates 16 identical memory pages among 3 processes. Each process must receive at least 1 page. How many allocations are possible?
- ClassifyPages are identical. Processes are distinct. Minimum 1 per process.
- Count\binom{16-1}{3-1} = \binom{15}{2} = 105
Answer: 105 allocations.
- A coach must assign 10 identical practice sessions among 3 players, with each player receiving at least 2 sessions. How many schedules are possible?
- A database has 5 distinct queries to route to 4 distinct servers. Any server may handle any query. How many routing schemes are there?
- A grocery store restocks 15 identical cans of soup on 4 labeled shelves, with each shelf holding at least 1. How many arrangements?
- A grant of $12,000 (in units of $1,000) is distributed among 3 research teams, each receiving between $2,000 and $5,000. How many distributions are possible? (Count solutions to \(x_1+x_2+x_3 = 12\) with \(2 \leq x_i \leq 5\).)
- An event planner assigns 9 distinct decorating tasks among 3 identical work crews. Explain why the counting is more difficult than assigning them among 3 distinct crews.
Sections 6.13 – 6.14
Common Mistakes and the Road Ahead
Repetition and Distribution Errors · Bridge to Inclusion-Exclusion
Section 6.13
Common Repetition and Distribution Mistakes
Mistake 1 — Confusing ordered and unordered selection
Choosing 3 flavors from 5 with repetition: \(5^3 = 125\) (wrong for unordered)
Correct: If order does not matter, use \(\binom{5+3-1}{3} = \binom{7}{3} = 35\). The count \(5^3 = 125\) is for ordered sequences where every distinct ordering counts separately.
Mistake 2 — Applying stars and bars to distinct objects
Distributing 5 distinct prizes among 3 people: \(\binom{3+5-1}{5} = 21\) (wrong)
Correct: Distinct objects go to distinct bins by the product rule: \(3^5 = 243\). Stars and bars counts distributions of identical objects, not distinct ones. Swapping which specific prizes two people receive creates a new arrangement when prizes are distinct.
Mistake 3 — Swapping \(n\) and \(k\) in the formula
"Choose 4 from 6 types" computed as \(\binom{4+6-1}{6} = \binom{9}{6}\)
Correct: \(n\) is the number of types (6) and \(k\) is the number chosen (4). The formula is \(\binom{6+4-1}{4} = \binom{9}{4} = 126\). Always identify: types = \(n\), items selected = \(k\), then compute \(\binom{n+k-1}{k}\).
Mistake 4 — Forgetting to subtract the minimum before applying the formula
Solving \(x_1 + x_2 + x_3 = 12\) with \(x_i \geq 2\): answer is \(\binom{14}{12}\)
Correct: First substitute \(y_i = x_i - 2\) to get \(y_1 + y_2 + y_3 = 6\). Then \(\binom{3+6-1}{6} = \binom{8}{6} = 28\). Failing to subtract the minimums counts solutions that violate the constraint.
Mistake 5 — Treating an upper bound like a lower bound
For \(x_1 \leq 4\), substituting \(y_1 = x_1 - 4\) to "reduce" the problem
Correct: Upper bounds are handled by complementary counting (or inclusion-exclusion), not by substitution. Substituting \(y_1 = x_1 - 4\) would give a negative-valued variable, which makes no sense. Instead: count all solutions, then subtract solutions where \(x_1 \geq 5\).
Mistake 6 — Ignoring the "at least one per bin" condition
Using \(\binom{n+k-1}{k}\) when each bin must be nonempty
Correct: When each bin must receive at least 1, first give 1 to each bin (reducing \(k\) by \(n\)), then apply stars and bars. The formula for positive-integer solutions is \(\binom{k-1}{n-1}\), not \(\binom{n+k-1}{k}\).
Mistake 7 — Confusing compositions and subsets
"Compositions of 8 into 3 parts": answer is \(\binom{8}{3}\)
Correct: The number of compositions of 8 into 3 positive integer parts is \(\binom{8-1}{3-1} = \binom{7}{2} = 21\). The formula \(\binom{8}{3}\) counts 3-element subsets of an 8-element set — a completely different problem.
Mistake 8 — Assuming identical bins when bins are labeled
A teacher distributes 10 books among Class A, Class B, and Class C. "Since they're all classes, the bins are identical."
Correct: Classes A, B, and C are distinct (labeled). Sending 7 books to A, 2 to B, 1 to C is different from sending 1 to A, 2 to B, 7 to C. Labeled bins are always distinct bins, regardless of whether the label is a name, a number, or a role.
- A student computes the number of ways to choose 3 books from 7 types with repetition, unordered, as \(7^3 = 343\). What error was made? What is the correct answer?
- A student distributes 8 distinct cards among 4 labeled envelopes and uses \(\binom{4+8-1}{8} = \binom{11}{8} = 165\). What is wrong? What is correct?
- A student solves \(x_1 + x_2 + x_3 = 15\), each \(x_i \geq 3\), and gets \(\binom{3+15-1}{15} = \binom{17}{15}\). Identify the error and correct it.
- A student says compositions of 9 into 2 parts and 2-element subsets of a 9-element set are the same count. Are they? Explain.
Section 6.14
Preparing for Inclusion-Exclusion and Partitions
This chapter has developed the core tools for counting selections and distributions when repetition is allowed and when minimum requirements apply. The method of complementary counting appeared in Section 6.8 as a way to handle upper-bound constraints: count all solutions, then subtract the violating ones. This is a preview of the central theme of Chapter 7.
Chapter 7 develops inclusion-exclusion systematically. When multiple constraints can be violated simultaneously, simple subtraction over-corrects — it subtracts solutions that violate both constraints twice instead of once. Inclusion-exclusion fixes this by adding back what was subtracted too many times. The two-set and three-set cases are derived carefully, and the general principle is introduced. Distribution problems with multiple upper bounds, restrictions on several variables at once, and arrangements with forbidden positions are all handled there.
Beyond Chapter 7, the study of distributions continues. Chapter 10 introduces recurrence relations, which describe distributions that build from smaller distributions — for example, counting distributions into \(n\) bins from distributions into \(n-1\) bins. Chapter 11 introduces generating functions, which encode the number of distributions with a given total as a coefficient in a formal polynomial. These tools handle far more complex restrictions, including upper bounds on every variable, without needing to enumerate cases.
The conceptual framework built in this chapter — representing a distribution as an integer solution to a sum equation, applying substitutions to handle constraints, and identifying whether objects and bins are identical or distinct — is the foundation for all of these later developments. Students who internalize these ideas will find Chapter 7 and beyond much more accessible.
Bridge to Chapter 7
Chapter 7 asks: what happens when you want to count elements that belong to one set or another, but the sets overlap? This is the inclusion-exclusion problem. Many distribution problems with upper bounds on multiple variables require exactly this tool — Section 6.8 gave a single-variable preview. In Chapter 7, the method extends to two and three simultaneous constraints, and then to the general principle that handles any number of overlapping conditions.
Chapter 6 — Back Matter
Chapter Summary
- Sec 6.1Repetition changes the counting model. When the same object or type can be chosen more than once, neither permutations nor standard combinations apply. The four cases of selection are: ordered with/without repetition, and unordered with/without repetition.
- Sec 6.2Ordered selection with repetition: \(n^k\) sequences of length \(k\) from \(n\) types. Follows directly from the product rule. Applies to passwords, binary strings, and any ordered sequence where each position is freely chosen.
- Sec 6.3Unordered selection with repetition (multisets): \(\binom{n+k-1}{k}\) ways to choose \(k\) items from \(n\) types when order does not matter and repetition is allowed. The formula is a binomial coefficient whose derivation requires stars and bars.
- Sec 6.4Stars and bars: encode a distribution of \(k\) identical objects among \(n\) categories as a sequence of \(k\) stars and \(n-1\) bars. Counting distinct sequences equals \(\binom{n+k-1}{k}\) — choosing which positions are stars.
- Sec 6.5Nonnegative integer solutions to \(x_1 + x_2 + \cdots + x_n = k\): \(\binom{n+k-1}{k}\). Stars and bars directly counts these solutions, since each solution corresponds to a unique sequence of stars and bars.
- Sec 6.6Positive integer solutions (each \(x_i \geq 1\)): substitute \(y_i = x_i - 1\) to reduce to nonnegative form. The count is \(\binom{k-1}{n-1}\). Also counts compositions of \(k\) into \(n\) positive integer parts.
- Sec 6.7Minimum requirements (\(x_i \geq m_i\)): substitute \(y_i = x_i - m_i\) to reduce to nonnegative form with total \(k - \sum m_i\). Apply stars and bars to the reduced equation.
- Sec 6.8Upper bounds (\(x_i \leq u_i\)): use complementary counting — count all solutions, subtract solutions that violate the bound. When multiple bounds can be violated simultaneously, inclusion-exclusion is needed (Chapter 7).
- Sec 6.9Identical objects into distinct bins: stars and bars. With no empty bins, \(\binom{k-1}{n-1}\). With empty bins allowed, \(\binom{n+k-1}{k}\).
- Sec 6.10Distinct objects into distinct bins: \(n^k\). Each of the \(k\) distinct objects independently chooses one of \(n\) bins. This counts functions from a \(k\)-element set to an \(n\)-element set.
- Sec 6.11Four cases of distribution: identical/distinct objects crossed with identical/distinct bins. Stars and bars and \(n^k\) handle the two tractable cases in this chapter. Integer partitions and Stirling numbers handle the others.
- Sec 6.12Real-world applications include task scheduling, inventory allocation, data distribution, grant allocation, and memory management. The key skill is translating the situation into the correct model by identifying objects, bins, and constraints.
- Sec 6.13Eight common mistakes: confusing ordered and unordered selection; applying stars and bars to distinct objects; swapping \(n\) and \(k\); forgetting to subtract minimums; mishandling upper bounds; mixing positive and nonnegative formulas; confusing compositions with subsets; treating labeled bins as identical.
- Sec 6.14Chapter 7 develops inclusion-exclusion for overlapping constraints. Chapter 10 introduces recurrences that describe distributions built from smaller ones. Chapter 11 uses generating functions to encode and solve distribution problems with complex restrictions.
Skill Practice
For each scenario, identify: (i) ordered or unordered? (ii) repetition allowed? (iii) which formula applies?
- Forming a 4-character password from 26 letters, letters may repeat.
- Choosing 5 flavors from 12 for an ice cream sampler (same flavor can appear multiple times, order of flavors in the list doesn't matter).
- Distributing 10 identical tokens among 4 players, any player may receive zero.
- Assigning 7 distinct tasks to 3 distinct employees, any employee may receive any number of tasks.
- Choosing 4 movies to watch this week from 20 available, order of viewing matters, you may rewatch.
- \(\binom{7+4-1}{4}\)
- \(\binom{10-1}{5-1}\)
- Nonneg. solutions: \(x_1+x_2+x_3=8\)
- Positive solutions: \(x_1+x_2+x_3+x_4=11\)
- Multisets of size 6 from 4 types
- Multisets of size 2 from 8 types
- Ordered sequences of length 5, 3 types
- Distinct objects in distinct bins: \(k=4,n=3\)
- \(x_1+x_2+x_3=15\), each \(\geq 3\)
- \(x_1+x_2+x_3+x_4=9\), each \(\geq 1\)
- \(a+b+c=12\), \(a \geq 2, b \geq 3, c \geq 0\)
- \(x_1+x_2+x_3=10\), \(x_1 \leq 4\), each \(\geq 0\)
- Compositions of 9 into 3 parts
- Compositions of 12 into 4 parts
Word Problems
For each problem: identify the model, set up the equation or formula, compute the answer, and interpret it in context.
- A juice bar offers 7 types of fruit. A smoothie contains exactly 4 pieces of fruit (repetition allowed, order doesn't matter). How many smoothie recipes are possible?
- A library has 6 copies of the same novel to lend to 4 book clubs, each club receiving at least 1 copy. How many lending distributions are possible?
- A software company distributes 15 identical server credits among 5 clients, each client receiving at least 2 credits. How many distributions are there?
- A teacher forms 3 quiz groups from 10 distinct students (any group may have any number of students, including zero). How many group assignments are possible?
- A fundraiser must allocate $18,000 (in $1,000 units) among 3 programs, with the arts program receiving between $3,000 and $8,000, and no restriction on the others. How many allocations satisfy the arts constraint? (Hint: complementary counting.)
- A bakery has 4 types of bread. A customer orders a mixed dozen (12 loaves), choosing freely from all 4 types with repetition. How many different orders are possible?
- How many ways can a total of 20 points be scored by 5 players in a game if each player's score is a nonnegative integer?
- A networking team must assign 9 distinct servers to 3 data centers, with each data center receiving at least 2 servers. Set up the counting argument and compute the answer. (Hint: for distinct objects with a lower bound per bin, use inclusion-exclusion or direct case analysis — this is a challenge problem.)
Error Analysis
Problem 1
How many multisets of size 4 from 5 types? Student answers: \(5^4 = 625\).
What error was made? What is the correct answer and method?
Problem 2
Nonnegative solutions to \(x_1+x_2+x_3=10\) with \(x_i \geq 2\): Student computes \(\binom{3+10-1}{10} = \binom{12}{2} = 66\).
Identify the error and correct it.
Problem 3
Distributing 6 distinct books among 4 identical shelves: Student applies \(\binom{4+6-1}{6} = \binom{9}{3} = 84\).
What is wrong? Explain why the formula used is inappropriate here.
Problem 4
Positive integer solutions to \(x_1+x_2+x_3 = 9\): Student writes \(\binom{3+9-1}{9} = \binom{11}{9} = 55\).
Identify the error. What formula applies here, and what is the correct count?
Proof and Reasoning Problems
- Prove that the number of nonnegative integer solutions to \(x_1 + x_2 + \cdots + x_n = k\) equals \(\binom{n+k-1}{k}\) by explaining the stars-and-bars bijection in your own words. Your argument should describe what stars and bars represent, establish the one-to-one correspondence, and identify the resulting combination count.
- The formula for positive integer solutions, \(\binom{k-1}{n-1}\), can also be interpreted as placing \(n-1\) dividers among the gaps between \(k\) stars (where the \(k\) stars are already placed in a row without bars at the ends). Explain this alternative picture and verify it gives the same formula.
- Show that the number of compositions of \(k\) into exactly \(n\) positive integer parts equals the number of ways to insert \(n-1\) dividers among the \(k-1\) gaps between \(k\) items arranged in a row.
- Prove algebraically that \(\binom{n+k-1}{k} = \binom{n+k-1}{n-1}\) and explain what each side counts in the context of stars and bars.
Challenge and Extension
- How many solutions in nonnegative integers does \(x_1 + x_2 + x_3 + x_4 = 20\) have if \(x_1 \leq 8\), \(x_2 \leq 8\), with no restriction on \(x_3\) and \(x_4\)? Use inclusion-exclusion (or preview Chapter 7 to handle the two simultaneous upper bounds).
- A vending machine has 6 slots, each holding exactly 1 item type, and a total of 24 identical items to stock. Each slot must have between 2 and 6 items. How many stocking arrangements are possible? (Handles both lower and upper bounds.)
- The number of compositions of \(k\) into any number of positive integer parts (not a fixed number of parts) is \(2^{k-1}\). Verify this for \(k = 4\) by listing all compositions, then prove it by thinking about which of the \(k-1\) gaps between \(k\) items to place a divider.
Chapter 6 Checkpoint
Chapter 6 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 6
Part A — Vocabulary and Concepts
- State the four cases of selection in a table, showing whether order matters and whether repetition is allowed, and giving the count formula for each.
- Explain in your own words what a multiset is and give an example with 3 types and 4 chosen items.
- Describe the stars-and-bars technique. What do the stars represent? What do the bars represent? What count does the technique produce?
- What is the difference between a nonnegative integer solution and a positive integer solution to a sum equation? How does the counting method differ?
Part B — Computing Counts
- How many multisets of size 5 can be chosen from 4 types?
- How many nonnegative integer solutions does \(x_1 + x_2 + x_3 + x_4 = 8\) have?
- How many positive integer solutions does \(x_1 + x_2 + x_3 = 12\) have?
- How many solutions does \(x_1 + x_2 + x_3 = 18\) have with each \(x_i \geq 4\)?
- How many nonnegative solutions does \(x_1 + x_2 + x_3 = 14\) have with \(x_1 \leq 5\)?
Part C — Distribution Problems
- A coach distributes 12 identical training sessions among 4 athletes. Each athlete must receive at least 1 session. How many distributions are possible?
- An office manager assigns 8 distinct tasks to 3 distinct employees. How many assignments are possible?
- A baker puts 15 identical cookies into 5 labeled bags (some bags may be empty). How many ways?
Part D — Classifying Models
- For each scenario below, identify whether objects are identical or distinct, whether bins are identical or distinct, and which formula (or which case from the four-case table) applies.
(a) Distributing 10 identical red chips among 4 labeled boxes.
(b) Distributing 5 distinct numbered tiles among 3 labeled bags.
(c) Distributing 6 identical coins among 3 indistinguishable envelopes.
(d) Distributing 4 distinct colored cards among 2 indistinguishable piles.
Part E — Error Analysis
- A student solves "distribute 9 identical items among 3 distinct bins, each bin receiving at least 1" with \(\binom{3+9-1}{9} = \binom{11}{9} = 55\). What is the error? What is correct?
- A student says: "Choosing 3 items from 5 types with repetition, unordered, is the same as \(5 \times 4 \times 3 / 6 = 10\), because it's like \(\binom{5}{3}\)." Explain the error fully and give the correct count.
Part F — Proof and Justification
- Give a brief combinatorial justification (not just a formula) for why the number of ways to distribute \(k\) identical objects among \(n\) distinct bins equals the number of nonnegative integer solutions to \(x_1 + x_2 + \cdots + x_n = k\).
- Explain why the substitution \(y_i = x_i - m_i\) converts a minimum-requirement problem into a nonnegative-solution problem, and why this is valid.
Looking Ahead
Chapter 7: Inclusion-Exclusion and Overlapping Structures
Chapter 6 showed how to count distributions under lower-bound constraints by substitution, and previewed upper-bound constraints using complementary counting. But when multiple upper bounds apply simultaneously, subtracting violating solutions overcounts — solutions that violate two constraints at once are subtracted twice. Chapter 7 introduces inclusion-exclusion: a systematic correction method that adds back what was subtracted too many times. You will count unions of overlapping sets, apply inclusion-exclusion to arrangements with forbidden positions, count derangements (permutations with no fixed points), and apply the principle to probability problems. The conceptual skill of correcting overcounting, which appeared briefly in Chapter 6, becomes a full counting strategy in Chapter 7.
MGU Library Connection
- Combinatorics Formula Sheet — Stars and Bars Reference (Appendix I of this textbook)
- Combinatorics Formula Sheet — Permutation and Combination Reference (Appendices E and F)
- Discrete Mathematics, Chapter 6: Integer Sequences and Recurrences — background on compositions and integer solutions
- Probability and Statistics, Chapter 5: Discrete Distributions — the multinomial distribution uses distribution counting directly
- Algorithms, Chapter 4: Combinatorial Optimization — distribution problems appear in bin packing and resource allocation algorithms
- MGU Dictionary entries: multiset, composition, stars and bars, distribution problem, nonnegative integer solution, Stirling number