STEP-BY-STEP LESSON · §9.6
r-Combinations with Repetition Allowed
Count choices of quantities of each type.
Before you begin
Choosing an unordered subset
C(n,r)=n!/[r!(n−r)!] counts r-element subsets of n distinct objects for integers 0≤r≤n. Divide the ordered count by r! because all orders of the same members represent one subset.
Nonnegative integer quantities
A nonnegative integer is one of 0, 1, 2, … . A quantity may be zero unless the problem requires each type to occur. Positive integers start at 1.
Symbols
- x₁+…+x_k=r
- r identical units distributed among k types
- k,r
- k≥1 distinct types; r≥0 identical units to distribute, both integers
Definitions and notation for this topic
Combinations with repetition
x₁+…+x_k=r; C(r+k−1,r)
For integers k≥1 and r≥0, the number of unordered selections of r items from k types, with unlimited repetition, is C(r+k−1,r). Equivalently, count integer x_i≥0 summing to r.
A separator construction uses r identical stars and k−1 separators; the stars in compartment i give x_i. A positive minimum or an upper bound per type changes the model.
Separate glossary example
Four scoops from three flavours, order ignored and flavours reusable, give C(6,4)=15 choices.
Step by step
Step 1 / 6
Identify what is distinct
Candies of one flavor are indistinguishable; flavors are distinct. A result specifies the quantity of each flavor.
This prevents counting the order in which candies are handed out.
Worked example
How many ways are there to choose 4 candies from three flavors with unlimited supply?
- A selection is completely determined by three quantities; exchanging identical candies changes nothing.
- Count x₁+x₂+x₃=4 with xᵢ≥0.
- Four stars and two separators give 6 positions. Choose 2: C(6,2)=15.
Optional self-check
How many positive integer solutions satisfy x+y+z=5? Explain the shift.
Show answer
Reserve one for each variable. The remaining nonnegative amounts sum to 2, so the count is C(4,2)=6.