At an ice cream shop with 7 flavors, how many different ways are there to choose 4 scoops, regardless of their order on the cone and allowing the same flavor more than once? This is a problem of combination with repetition.
In the article on arrangements with repetition, we saw that when order matters and repetition is allowed, the count is \(n^r\). Now we reach the last of the six types of grouping in the series: order no longer matters, but repetition is still allowed. The formula changes, and the technique for deriving it is elegant enough to have a name of its own: stars and bars.
Why combinations with repetition? #
Selecting elements with repetition without regard to order is a central operation in computing and statistics:
- Multisets in programming: Python’s
collections.Counterstores multisets, collections where an element can appear more than once, with no regard to order. The number of multisets of size \(r\) over a vocabulary of \(n\) elements is exactly \(CR(n, r)\). - Distribution of identical resources: allocating \(r\) identical tokens, credits, or tasks among \(n\) processes or servers, regardless of the delivery sequence, is a \(CR(n, r)\) problem, the basis of scheduling and load balancing models.
- Histogram analysis: the number of possible histograms with \(r\) samples in \(n\) categories (only the counts per category, without recording which sample fell where) is \(CR(n, r)\).
- Integer programming: counting nonnegative integer solutions of \(x_1 + x_2 + \cdots + x_n = r\) is equivalent to \(CR(n, r)\), a direct connection with optimization problems and state-space analysis.
- Information theory: grouping the sequences of \(r\) symbols from an alphabet of \(n\) by the frequency of each symbol, ignoring positions, we get exactly \(CR(n, r)\) groups, the types of sequence, used in proofs about data compression.
From combination to combination with repetition #
The diagram below completes the decision tree of the series, adding the sixth and last type of classic grouping:
flowchart TD
A["n types of elements"] --> B{"Repetition
allowed?"}
B -->|"No: all distinct"| C{"Use all?"}
C -->|"Yes"| D["Permutation
P_n = n!"]
C -->|"No: choose r"| E{"Does order matter?"}
E -->|"Yes"| F["Arrangement
A(n,r) = n!/(n-r)!"]
E -->|"No"| G["Combination
C(n,r) = n!/(r!(n-r)!)"]
B -->|"Yes: with repetition"| H{"Use all?"}
H -->|"Yes: fixed multiset"| I["Permutation with Repetition
n!/(n₁!·n₂!·…·nₖ!)"]
H -->|"No: choose r"| K{"Does order matter?"}
K -->|"Yes"| J["Arrangement with Repetition
AR(n,r) = nʳ"]
K -->|"No"| L["Combination with Repetition
CR(n,r) = C(n+r-1,r)"]
Combination with Repetition #
A combination with repetition of \(n\) elements taken \(r\) at a time, hereafter denoted \(CR(n,r)\), is a selection of \(r\) elements without regard to order, where each element can appear more than once:
$$CR(n, r) = \binom{n + r - 1}{r} = \binom{n + r - 1}{n - 1}$$Note: unlike the combination without repetition, \(r\) can be greater than \(n\), since we can select more elements than there are types available, simply by repeating some of them.
The Stars and Bars Method #
How do we derive the formula? The idea is to encode each distribution as a sequence of two kinds of symbols, ★ (star) and | (bar), and count those sequences. The method appears in William Feller’s classic probability book, An Introduction to Probability Theory and Its Applications (1950), which helped make it known (see the entry Stars and bars). ★ and | form an alphabet of two symbols, exactly like 1 and 0 in a binary sequence: ★ stands for “one unit allocated” and | stands for “change of box”. In the article on permutations with repetition, we saw that arranging \(k\) symbols of one kind and \(m\) of another produces \(\binom{k+m}{k}\) distinct sequences: that is the result we will use here.
Motivating example: distributing 5 identical balls into 3 numbered boxes. Each distribution corresponds to a sequence of 5 stars (★) and 2 bars (|), where the bars separate the boxes:
$$\underbrace{★★}_{C_1} | \underbrace{★}_{C_2} | \underbrace{★★}_{C_3} \quad\longrightarrow\quad ★ ★ | ★ | ★ ★$$The sequence has 5 stars and 2 bars, 7 symbols in total. Counting the distributions amounts to choosing which 2 positions (among the 7) receive a bar:
$$C(7, 2) = C(5+3-1, 3-1) = \binom{7}{2} = 21$$Generalization: \(r\) stars in \(n\) boxes use \(n-1\) bars, forming a sequence of \(r + n - 1\) symbols. Choosing the \(r\) positions of the stars (or the \(n-1\) of the bars) gives:
$$CR(n, r) = \binom{n + r - 1}{r}$$Three Equivalent Formulations #
The beauty of the stars and bars method is that it reveals that three problems with very different statements are, in fact, the same counting problem:
The three problems below have exactly \(CR(n,r) = \binom{n+r-1}{r}\) solutions:
- Selection with repetition: choosing \(r\) elements from \(n\) types (regardless of order, repetition allowed).
- Distribution of identical objects: placing \(r\) indistinguishable balls into \(n\) distinct boxes (boxes may stay empty).
- Integer equations: nonnegative integer solutions of \(x_1 + x_2 + \cdots + x_n = r\).
The figure below takes the sequence from the motivating example, ★★|★|★★, and reads it in the three ways:
Recognizing which of the three readings fits the statement is the central skill for solving problems with \(CR\).
Worked Examples #
4 scoops from 7 flavors #
Problem: An ice cream shop offers 7 flavors. In how many different ways can you order 4 scoops, regardless of order and allowing the same flavor to repeat?
Solution: The order of the scoops on the cone does not matter (chocolate + strawberry = strawberry + chocolate), and repetition is allowed (four scoops of chocolate is a valid option). We apply the combination with repetition with \(n = 7\) flavors and \(r = 4\) scoops:
$$CR(7, 4) = \binom{7 + 4 - 1}{4} = \binom{10}{4} = \mathbf{210}$$Back to the opening example: there are \(\mathbf{210}\) possible distinct orders.
Python: itertools.combinations_with_replacement
itertools.combinations_with_replacement
Python directly offers the function that generates combinations with
repetition, itertools.combinations_with_replacement(iterable, r):
from itertools import combinations_with_replacement
from math import comb
flavors = ["chocolate", "strawberry", "vanilla", "lemon",
"passion fruit", "grape", "coconut"] # 7 flavors
# Generates all orders of 4 scoops
orders = list(combinations_with_replacement(flavors, 4))
print(len(orders)) # 210 = CR(7, 4)
print(orders[0]) # ('chocolate', 'chocolate', 'chocolate', 'chocolate')
print(orders[-1]) # ('coconut', 'coconut', 'coconut', 'coconut')
# Check with the formula
print(comb(7 + 4 - 1, 4)) # 210Note that combinations_with_replacement returns each tuple with the
flavors in the order they appear in the input list: that is why the first
order is all chocolate and the last, all coconut. This canonical order is
what guarantees that two orders with the same flavors in a different sequence
show up as a single tuple.
5 balls in 3 boxes #
Problem: In how many ways can 5 identical balls be distributed into 3 distinct boxes (boxes may stay empty)?
Solution: Identical balls in distinct boxes is the second reading of the classic equivalences, with \(n = 3\) boxes and \(r = 5\) balls.
$$CR(3, 5) = \binom{3 + 5 - 1}{5} = \binom{7}{5} = \binom{7}{2} = \mathbf{21}$$The stars and bars method confirms it: 5 stars and 2 bars, choosing 2 positions among 7.
The connection becomes clear when we name the boxes of the previous example with variables. Let \(x_1\) be the number of balls in box 1, \(x_2\) the number in box 2, and \(x_3\) the number in box 3. Each valid distribution is exactly one nonnegative integer solution of:
$$x_1 + x_2 + x_3 = 5, \quad x_i \geq 0$$For example, the distribution ★★ | ★ | ★★ corresponds to the solution \((x_1, x_2, x_3) = (2, 1, 2)\). The sequence of stars and bars ★ ★ | ★ | ★ ★ and the equation \(2 + 1 + 2 = 5\) carry the same information: they are two notations for the same object.
This generalizes immediately: nonnegative integer solutions of \(x_1 + x_2 + \cdots + x_n = r\) are the same as distributions of \(r\) balls into \(n\) boxes, and are therefore counted by \(CR(n, r)\). The variable \(x_i\) is the “counter” of box \(i\); the equation is just the requirement that the total number of balls be \(r\).
Likewise, the ice cream example can be written with variables: if \(s_i\) is the number of scoops of flavor \(i\) ordered, counting orders of 4 scoops from 7 flavors is the same as counting solutions of \(s_1 + s_2 + \cdots + s_7 = 4\) with \(s_i \geq 0\), and the result is \(CR(7, 4) = 210\), as we have already seen.
Integer solutions of \(x + y + z + w = 9\) #
Problem: How many nonnegative integer solutions does the equation \(x + y + z + w = 9\) have?
Solution: We have \(n = 4\) variables (equivalent to 4 boxes) and \(r = 9\) (equivalent to 9 balls to distribute):
$$CR(4, 9) = \binom{4 + 9 - 1}{9} = \binom{12}{9} = \binom{12}{3} = \mathbf{220}$$Solutions of \(x_1 + x_2 + x_3 = 10\) with \(x_2 \geq 4\) #
Problem: How many nonnegative integer solutions does \(x_1 + x_2 + x_3 = 10\) have with the restriction \(x_2 \geq 4\)?
Solution: The restriction \(x_2 \geq 4\) is handled by substitution: we define \(y_2 = x_2 - 4 \geq 0\), which “absorbs” the required minimum of \(x_2\). The equation becomes:
$$x_1 + (y_2 + 4) + x_3 = 10 \implies x_1 + y_2 + x_3 = 6$$Now we have \(n = 3\) variables and \(r = 6\), all nonnegative:
$$CR(3, 6) = \binom{3 + 6 - 1}{6} = \binom{8}{6} = \binom{8}{2} = \mathbf{28}$$Solutions of \(x + y + z + w \leq 5\) #
Problem: How many nonnegative integer solutions does \(x + y + z + w \leq 5\) have?
Solution (Method 1, direct sum by cases): we split by total value \(k = 0, 1, \ldots, 5\) and apply the sum rule:
$$\sum_{k=0}^{5} CR(4, k) = \binom{3}{0} + \binom{4}{1} + \binom{5}{2} + \binom{6}{3} + \binom{7}{4} + \binom{8}{5} = 1 + 4 + 10 + 20 + 35 + 56 = 126$$Solution (Method 2, slack variable): we introduce \(f = 5 - (x+y+z+w) \geq 0\), which turns the inequality into an equality:
$$x + y + z + w + f = 5 \implies CR(5, 5) = \binom{9}{5} = \mathbf{126} \checkmark$$The slack variable method is more elegant: instead of adding up 6 terms, it is solved with a single application of the formula.
Summary Table #
The table below gathers all six types of grouping in the series and the central result of this article:
| Without repetition | With repetition | |
|---|---|---|
| Uses all \(n\) elements | Permutation: \(n!\) | Permutation w/ Repetition: \(\dfrac{n!}{n_1!\cdots n_k!}\) |
| Chooses \(r\), order matters | Arrangement: \(\dfrac{n!}{(n-r)!}\) | Arrangement w/ Repetition: \(n^r\) |
| Chooses \(r\), order does not matter | Combination: \(\dfrac{n!}{r!(n-r)!}\) | Combination w/ Repetition: \(\dbinom{n+r-1}{r}\) |
Specific results of this article:
| Result | Formula |
|---|---|
| Combination with repetition | \(CR(n,r) = \dbinom{n+r-1}{r}\) |
| Equivalence with distribution of identical objects | \(r\) balls in \(n\) boxes → \(CR(n,r)\) |
| Equivalence with nonnegative integer solutions | \(x_1 + \cdots + x_n = r, x_i \geq 0\) → \(CR(n,r)\) |
| Inequality: \(x_1 + \cdots + x_n \leq r, x_i \geq 0\) via slack variable | \(CR(n+1, r)\) |
Exercises #
The exercises below go through the three equivalent formulations of \(CR(n,r)\): selection with repetition, distribution of identical objects, and solutions of equations with restrictions. They are ordered from simplest to most complex.
Exercise 1: Distributing oranges
In how many ways can we distribute 6 identical oranges among 2 people (each person may end up with no oranges)?
Solution
The oranges are identical (their order does not matter) and each person can receive any amount, including zero. This is equivalent to counting nonnegative integer solutions of \(a + b = 6\), with \(n = 2\) and \(r = 6\):
$$CR(2, 6) = \binom{7}{6} = \binom{7}{1} = \mathbf{7}$$The distributions are: (0,6), (1,5), (2,4), (3,3), (4,2), (5,1), (6,0). Exactly 7. ✓
Exercise 2: Party sweets
A candy shop offers 8 varieties of sweets. In how many ways can you buy 12 sweets, repeating varieties allowed and regardless of order?
Solution
Selection with repetition: \(n = 8\) varieties, \(r = 12\) sweets:
$$CR(8, 12) = \binom{8 + 12 - 1}{12} = \binom{19}{12} = \binom{19}{7} = \mathbf{50{,}388}$$Here \(r = 12\) is greater than \(n = 8\), something the combination with repetition allows, as we saw in the note right after the definition: just repeat varieties.
Exercise 3: Balls in nonempty boxes
In how many ways can 20 identical balls be placed into 5 distinct boxes with no box left empty?
Solution
The restriction “no empty box” means each box receives at least 1 ball. We make the substitution \(x_i^\ast = x_i - 1 \geq 0\), which absorbs the minimum of 1 per box. The total sum decreases by 5:
$$x_1 + \cdots + x_5 = 20, x_i \geq 1 \implies x_1^* + \cdots + x_5^* = 15, x_i^* \geq 0$$$$CR(5, 15) = \binom{5 + 15 - 1}{15} = \binom{19}{15} = \binom{19}{4} = \mathbf{3{,}876}$$
Exercise 4: Sum of digits
How many integers between 1 and 100,000 have digit sum equal to 6?
Solution
Every integer in this range can be represented as a sequence of 5 digits \(d_1 d_2 d_3 d_4 d_5\) with \(d_i \geq 0\) (including leading zeros: 6 becomes 00006). The number 100,000 has digit sum 1, so it is not counted. We want nonnegative integer solutions of \(d_1 + d_2 + d_3 + d_4 + d_5 = 6\). Since the sum is 6 and no digit can exceed 9, the restriction \(d_i \leq 9\) is satisfied automatically:
$$CR(5, 6) = \binom{5 + 6 - 1}{6} = \binom{10}{6} = \binom{10}{4} = \mathbf{210}$$
Exercise 5: Positive integer solutions with an inequality
How many positive integer solutions (\(x, y, z \geq 1\)) does \(x + y + z < 10\) have?
Solution
Step 1 (eliminate the \(\geq 1\)): let \(x^\ast = x - 1, y^\ast = y - 1, z^\ast = z - 1 \geq 0\). The inequality becomes \(x^\ast + y^\ast + z^\ast < 7\), that is, \(\leq 6\).
Step 2 (turn the inequality into an equality): we introduce a slack variable \(u = 6 - (x^\ast + y^\ast + z^\ast) \geq 0\):
$$x^* + y^* + z^* + u = 6, \quad x^*, y^*, z^*, u \geq 0$$Now we have \(n = 4\) variables and \(r = 6\):
$$CR(4, 6) = \binom{4 + 6 - 1}{6} = \binom{9}{6} = \binom{9}{3} = \mathbf{84}$$Next steps #
The combination with repetition completes the triad of groupings with repetition and closes the picture of six types of counting in the series. The limitation of all these tools is that they work with simple counts: how many are there? The natural next step is to understand how these coefficients relate to one another: the identities that connect them, such as Pascal’s rule and the binomial theorem, topics of the next articles in the series.
