MATC44H3 Chap.11 Stars and Bars for Selections with Repetition
Stars and Bars for Selections with Repetition
The entry that needed a proof
The selection table of week 2 lists C(n + k − 1, k) as the count of selections of k objects drawn from n types when order does not matter and repetition is allowed, and marks that entry as requiring a proof. The course schedule places stars and bars in week 4 together with the binomial theorem and Pascal's triangle.
Stars and bars is the proof.
The bijection
A selection with repetition is determined by how many objects of each type it contains. Write those counts as stars, with bars separating consecutive types. With n types there are n − 1 bars, so every selection of k objects becomes a string of k stars and n − 1 bars, and every such string can be read back as a selection.
Choosing which of the n + k − 1 positions hold stars fixes the string, which gives C(n + k − 1, k) selections, or equivalently C(n + k − 1, n − 1).
Equations and lower bounds
The same count gives the number of solutions of x1 + x2 + ⋯ + xn = k in nonnegative integers.
When each variable must be at least some value, subtract that value from each variable first; the new variables are nonnegative and add to a smaller total, and stars and bars applies to them. The method counts identical objects. Distinct objects shared among people are counted by functions, as in the chapter on the multiplication principle.
What this chapter covers
- 01
Unordered selections with repetition
- 02
Stars, bars and the bijection
- 03
Solutions of x1 + ⋯ + xn = k
- 04
Substitutions for lower bounds
- 05
Identical versus distinct objects
- 06
Checking against the selection table
Worked example · free
Choosing a dozen pastries
- 1This is an unordered selection of 12 objects from 5 types with repetition.
- 1Encode it as 12 stars and 4 bars in 16 positions.
- 2Choose the 4 bar positions: C(16, 4) = 1,820.
Key terms
- Selection With Repetition
- A selection with repetition is an unordered choice of objects in which a type may be chosen more than once.
- Star Pattern
- A star pattern is a string of stars and bars that records how many objects of each type a selection contains.
- Nonnegative Solution
- A nonnegative solution of an equation is one in which every variable is zero or a positive integer.
- Variable Shift
- A variable shift replaces each variable by itself minus a lower bound so that the new variables start at zero.
Stars and Bars for Selections with Repetition FAQ
Why are there n − 1 bars for n types?
Bars separate consecutive types, and n types need only n − 1 separators: the stars before the first bar belong to type 1, the stars between the first and second bars to type 2, and so on, with the stars after the last bar belonging to type n.
How do I handle a condition that every type appears at least once?
Put one object of each type into the selection first. That uses n of the k objects, and the remaining k − n can be chosen freely with repetition, giving C(k − 1, n − 1) selections. This is the same substitution as subtracting 1 from every variable in the equation version.
When does stars and bars not apply?
It does not apply when the objects are distinct, because then it matters which particular object goes where. Sharing distinct gifts among people is a function count, and arranging objects in a line is a permutation count. Stars and bars counts how many of each type, nothing more.
How is stars and bars related to the selection table?
It proves the table's entry for unordered selections with repetition, the one the week 2 lecture marks as needing a proof. Each selection becomes a string of stars and bars, and counting the strings by choosing the star positions gives C(n + k − 1, k).
Exam move
Prove the selection table entry from memory by writing the bijection in both directions. Then solve three problems: an unrestricted selection, an equation with lower bounds, and a distinct-object version of the same story, and explain why the third needs a different formula.
Working through Stars and Bars for Selections with Repetition in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 Stars and Bars for Selections with Repetition question and get a clear, step-by-step explanation grounded in how MATC44H3 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
