Simple combinations count the ways of choosing k distinct elements from n. But many real situations allow the same element to be taken several times: buying 10 ice creams from 4 flavours, distributing 20 identical servers across 3 data centres, putting together an order of 12 items from a catalogue of 5 products. For these cases there is an elegant counting method, called stars and bars, that turns the problem into a simple combination.
The model problem
In how many ways can you choose 10 ice creams from 4 flavours, if all that matters is how many of each flavour you take and not the order?
A choice is described by four non-negative numbers x₁, x₂, x₃, x₄ with
x₁ + x₂ + x₃ + x₄ = 10
So the question is equivalent to: how many non-negative integer solutions does this equation have?
Stars and bars
Represent each ice cream with a star ★ and separate the flavours with 3 bars |. A choice becomes a sequence of 10 stars and 3 bars:
★★★|★★||★★★★★
This sequence means: 3 ice creams of the first flavour, 2 of the second, 0 of the third, 5 of the fourth. Every sequence of 10 stars and 3 bars corresponds to exactly one choice, and vice versa: it is a bijection.
Counting the sequences is easy. They are 13 symbols long, and you just decide which 3 positions hold the bars:
C(13, 3) = 286
The general formula
The number of ways to choose k objects from n types, with repetition and without order, is:
C(n + k − 1, k) = C(n + k − 1, n − 1)
There are k stars and n − 1 bars (n types need n − 1 separators), and you choose the positions of the bars, or equivalently of the stars.
Minimum constraints
If every flavour must be taken at least once, first give one ice cream to each flavour. That leaves 10 − 4 = 6 ice creams to distribute freely across 4 flavours:
C(6 + 3, 3) = C(9, 3) = 84
In general, with the constraint xᵢ ≥ 1, the solutions of x₁ + … + xₙ = k number C(k − 1, n − 1). You can also see it directly: between k stars in a row there are k − 1 gaps, and you must choose n − 1 of them to hold a bar, at most one per gap.
Maximum constraints
Constraints of the form xᵢ ≤ m are trickier and are handled with the inclusion-exclusion principle.
Example: how many solutions does x₁ + x₂ + x₃ = 10 have with 0 ≤ xᵢ ≤ 4?
- Without constraints: C(12, 2) = 66.
- Solutions with x₁ ≥ 5: set y₁ = x₁ − 5 to get y₁ + x₂ + x₃ = 5, with C(7, 2) = 21 solutions. The same for x₂ and x₃: 3 · 21 = 63 in total.
- Solutions with two variables ≥ 5: for example x₁, x₂ ≥ 5 gives y₁ + y₂ + x₃ = 0, with 1 solution. There are 3 pairs, 3 in total.
- Three variables ≥ 5 would need a sum of at least 15: impossible.
Result: 66 − 63 + 3 = 6. Direct check: the solutions are the permutations of (4, 4, 2) and of (4, 3, 3), that is 3 + 3 = 6.
Permutations with repetition
A different but related problem: how many distinct anagrams does a word with repeated letters have? Here order matters, but identical objects cannot be told apart.
For the word MISSISSIPPI, 11 letters with M once, I four times, S four times and P twice, the anagrams number:
11! / (1! · 4! · 4! · 2!) = 34,650
You divide the number of permutations of 11 objects by the ways of permuting identical letters among themselves, which produce no new words. This number is called a multinomial coefficient.
A summary
| Situation | Order | Repetition | Count |
|---|---|---|---|
| Strings of length k over n symbols | yes | yes | nᵏ |
| k-element subsets | no | no | C(n, k) |
| k-element multisets from n types | no | yes | C(n + k − 1, k) |
| Anagrams with repeats | yes | fixed | n! / (k₁! … kᵣ!) |
Where it is used in computing
- Distributing identical resources: the number of ways to split k units of capacity among n services is C(n + k − 1, n − 1). It tells you when an exhaustive search is feasible.
- Histograms and counts: the number of possible count vectors for k observations in n categories is exactly the number of combinations with repetition.
A quick check in code, for small values, always confirms the reasoning:
from itertools import combinations_with_replacement
assert len(list(combinations_with_replacement(range(4), 10))) == 286
In short
- Choosing k objects from n types with repetition is the same as counting solutions of x₁ + … + xₙ = k.
- With stars and bars, the non-negative solutions number C(n + k − 1, k).
- Minimum constraints are handled by subtracting in advance; maximum ones with inclusion-exclusion.
- Anagrams with repeated letters are counted with the multinomial coefficient.
- Always check formulas on small cases with an enumeration.
