2.4 Combinations with repetition

Combinations with Repetition

Combinations with repetition let you count the number of ways to choose items from a set when repeats are allowed and order doesn't matter. This comes up constantly in distribution problems, like splitting identical objects among different groups, and it builds directly on the regular combinations you already know.

Concept and Formula

With regular combinations, once you pick an item, it's gone. Combinations with repetition remove that restriction: you can pick the same type of item as many times as you want, and the order of selection still doesn't matter.

The formula is:

${n+r-1 \choose r}$

where n is the number of types (or categories) to choose from, and r is the number of items you're choosing.

Why is the formula structured this way? You're really counting the number of ways to arrange r identical items and n-1 dividers in a row. That total is $r + (n-1) = n+r-1$ positions, and you're choosing which r of them will be items. This is the heart of the stars and bars method (covered below).

Quick comparison to regular combinations: With the same n and r, combinations with repetition always produce at least as many outcomes as combinations without repetition, because you have more freedom in what you can select.

Example: Suppose you're at a bakery with 4 types of donuts and you want to buy 6 donuts total. You can buy multiples of the same type, and the order you pick them doesn't matter. The number of possible selections is:

${4+6-1 \choose 6} = {9 \choose 6} = 84$

Stars and Bars Method

How It Works

Stars and bars is a visual technique that makes combinations with repetition feel concrete. Here's the setup:

• Stars (★) represent the r items you're choosing.
• Bars (|) act as dividers between the n different types. You need exactly n-1 bars to create n categories.

Each arrangement of stars and bars corresponds to exactly one way of distributing the items. Stars to the left of the first bar go to type 1, stars between the first and second bar go to type 2, and so on.

Example: Distributing r = 5 identical balls into n = 3 boxes. You need 5 stars and 2 bars. One possible arrangement:

★★ | ★ | ★★ → Box 1 gets 2, Box 2 gets 1, Box 3 gets 2

Another arrangement:

| ★★★★★ | → Box 1 gets 0, Box 2 gets 5, Box 3 gets 0

The total number of arrangements is ${5+3-1 \choose 5} = {7 \choose 5} = 21$.

Solving Problems Step by Step

1. Identify what's being distributed (these are your stars). Count them to get r.
2. Identify the categories or bins (these determine your bars). Count the categories to get n.
3. Check that order doesn't matter and repetition is allowed. If so, this is a combinations-with-repetition problem.
4. Apply the formula: ${n+r-1 \choose r}$
5. Handle constraints if needed. If each category must receive at least 1 item, first give 1 to each category, then distribute the remaining $r - n$ items freely. The count becomes ${r-1 \choose n-1}$. For upper-bound constraints (e.g., no category gets more than k), use inclusion-exclusion.

Applications of Combinations with Repetition

Distributing Identical Objects

This is the most classic application. You have r identical objects and n distinct containers, and you want to count the number of ways to distribute them.

• n = number of containers (distinct)
• r = number of identical objects

Example: You have 10 identical pencils to distribute among 4 departments. The number of ways is:

${4+10-1 \choose 10} = {13 \choose 10} = 286$

If every department must get at least 1 pencil, give each department 1 first (using up 4 pencils), then distribute the remaining 6 freely:

${4+6-1 \choose 6} = {9 \choose 6} = 84$

Resource Allocation and Scheduling

The same framework applies whenever you're splitting a quantity among categories:

• Allocating a budget of r thousand dollars across n project teams
• Assigning r identical tasks across n time slots
• Distributing r identical products across n warehouses

In each case, map the problem to stars (the quantity being distributed) and bars (the dividers between categories), then apply the formula.

Combinations: With vs. Without Repetition

Formula Comparison

The key structural difference: without repetition, you're choosing r distinct items from n options. With repetition, you're placing n-1 dividers among r identical items.

When to Use Which

A good test: ask yourself, "After I pick an item, can I pick the same type again?" If yes, and order doesn't matter, you're in combinations-with-repetition territory.