Permutations and Combinations with Repetition

Master multisets, stars and bars, and counting with indistinguishable objects or repeated selections.

23 min read
Intermediate

Introduction

So far, we've counted arrangements and selections of distinct objects. But what if objects can repeat? How many ways can you distribute 10 identical candies to 4 children? How many words can you make from "MISSISSIPPI"? This lesson explores counting with repetition.

Learning Objectives:

  • Count permutations when objects are indistinguishable
  • Apply the stars and bars method for distributing identical objects
  • Solve multiset problems
  • Calculate anagrams of words with repeated letters

Permutations with Repetition

If you have nn total objects where:

  • Type 1 appears n1n_1 times
  • Type 2 appears n2n_2 times
  • ...
  • Type kk appears nkn_k times

The number of distinct permutations is:

n!n1!⋅n2!⋅…⋅nk!\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}

Why? We divide by each ni!n_i! to account for indistinguishable arrangements within each type.

Example 1: Anagrams of MISSISSIPPI

The word "MISSISSIPPI" has 11 letters:

  • M: 1 time
  • I: 4 times
  • S: 4 times
  • P: 2 times

Solution:

11!1!⋅4!⋅4!⋅2!=39,916,8001⋅24⋅24⋅2=39,916,8001,152=34,650\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39,916,800}{1 \cdot 24 \cdot 24 \cdot 2} = \frac{39,916,800}{1,152} = 34,650

There are 34,650 distinct anagrams of MISSISSIPPI.

python
import math
from collections import Counter

def multiset_permutations(word):
    """Count distinct permutations of a word with repeated letters"""
    n = len(word)
    letter_counts = Counter(word)

    # Calculate n!
    numerator = math.factorial(n)

    # Calculate product of factorials of counts
    denominator = 1
    for count in letter_counts.values():
        denominator *= math.factorial(count)

    return numerator // denominator

# Anagrams of MISSISSIPPI
word = "MISSISSIPPI"
result = multiset_permutations(word)

print(f"Word: {word}")
print(f"Length: {len(word)}")
print(f"\nLetter frequencies:")
for letter, count in sorted(Counter(word).items()):
    print(f"  {letter}: {count}")

print(f"\nDistinct anagrams: {result:,}")

# Verify calculation
n = 11
denominator = math.factorial(1) * math.factorial(4) * math.factorial(4) * math.factorial(2)
print(f"\nCalculation: {n}! / (1! × 4! × 4! × 2!) = {math.factorial(n):,} / {denominator:,} = {result:,}")

Intuition: If all letters were distinct, we'd have 11!11! permutations. But since I's are indistinguishable, we divide by 4!4! (the 4 I's can be rearranged without creating a new word). Same for S's and P's.

Stars and Bars Method

The number of ways to distribute nn identical objects into kk distinct bins is:

(n+k−1k−1)=(n+k−1n)\binom{n+k-1}{k-1} = \binom{n+k-1}{n}

Visualization: Represent nn objects as stars (★) and k−1k-1 dividers as bars (|). Arrange them in a line.

Example: Distributing 5 objects to 3 bins: ★★|★|★★ means (2, 1, 2).

Example 2: Distributing Candies

Distribute 10 identical candies to 4 children. How many ways?

Solution: We need to place 10 stars and 3 bars (to create 4 bins):

(10+4−14−1)=(133)=13×12×113×2×1=1,7166=286\binom{10+4-1}{4-1} = \binom{13}{3} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = \frac{1,716}{6} = 286

Interpretation: We're choosing 3 positions out of 13 for the bars (or equivalently, 10 positions for the stars).

python
from scipy.special import comb

def distribute_identical_objects(n_objects, k_bins):
    """Count ways to distribute n identical objects into k distinct bins"""
    return int(comb(n_objects + k_bins - 1, k_bins - 1, exact=True))

# Distribute 10 candies to 4 children
n = 10  # candies
k = 4   # children

result = distribute_identical_objects(n, k)

print(f"Distributing {n} identical candies to {k} children")
print(f"\nFormula: C({n}+{k}-1, {k}-1) = C({n+k-1}, {k-1})")
print(f"Result: {result:,} ways")

# Show some example distributions
print(f"\nExample distributions (child1, child2, child3, child4):")
examples = [
    (10, 0, 0, 0),
    (7, 1, 1, 1),
    (4, 3, 2, 1),
    (3, 3, 2, 2),
    (5, 5, 0, 0)
]
for i, dist in enumerate(examples, 1):
    print(f"  {i}. {dist} → Sum: {sum(dist)}")

Combinations with Repetition

What if we want to select kk objects from nn types, allowing repetition?

Example 3: Ice Cream Scoops

An ice cream shop has 5 flavors. You want to buy 3 scoops (order doesn't matter, repetition allowed). How many combinations?

Solution: This is equivalent to distributing 3 identical objects (scoops) into 5 bins (flavors):

(3+5−15−1)=(74)=(73)=35\binom{3+5-1}{5-1} = \binom{7}{4} = \binom{7}{3} = 35

Examples:

  • (Vanilla, Vanilla, Vanilla)
  • (Chocolate, Strawberry, Vanilla)
  • (Mint, Mint, Chocolate)
python
from scipy.special import comb
import itertools

def combinations_with_repetition(n_types, k_selections):
    """Count combinations of k selections from n types (with repetition)"""
    return int(comb(k_selections + n_types - 1, n_types - 1, exact=True))

# Ice cream problem
n_flavors = 5
k_scoops = 3

result = combinations_with_repetition(n_flavors, k_scoops)

print(f"Selecting {k_scoops} ice cream scoops from {n_flavors} flavors")
print(f"(Repetition allowed, order doesn't matter)")
print(f"\nFormula: C({k_scoops}+{n_flavors}-1, {n_flavors}-1) = C({k_scoops+n_flavors-1}, {n_flavors-1})")
print(f"Result: {result} combinations")

# Enumerate all combinations using Python
flavors = ['V', 'C', 'S', 'M', 'B']  # Vanilla, Chocolate, Strawberry, Mint, Banana
all_combos = list(itertools.combinations_with_replacement(flavors, k_scoops))

print(f"\nVerification by enumeration: {len(all_combos)} combinations")
print(f"\nFirst 10 combinations:")
for i, combo in enumerate(all_combos[:10], 1):
    print(f"  {i}. {combo}")

Integer Partitions and Equations

Stars and bars can solve non-negative integer solutions to equations.

Example 4: Solutions to x1+x2+x3=10x_1 + x_2 + x_3 = 10

How many non-negative integer solutions exist for x1+x2+x3=10x_1 + x_2 + x_3 = 10?

Solution: This is distributing 10 identical objects (the sum) into 3 bins (the variables):

(10+3−13−1)=(122)=12×112=66\binom{10+3-1}{3-1} = \binom{12}{2} = \frac{12 \times 11}{2} = 66

What if each xi≥1x_i \geq 1? Give each variable 1 unit first, leaving 10−3=710-3=7 to distribute:

(7+3−13−1)=(92)=36\binom{7+3-1}{3-1} = \binom{9}{2} = 36

python
from scipy.special import comb

# Non-negative solutions to x1 + x2 + x3 = 10
target_sum = 10
n_variables = 3

# Case 1: x_i >= 0
result_nonneg = int(comb(target_sum + n_variables - 1, n_variables - 1, exact=True))
print(f"Non-negative integer solutions to x1 + x2 + x3 = {target_sum}:")
print(f"  C({target_sum}+{n_variables}-1, {n_variables}-1) = C({target_sum+n_variables-1}, {n_variables-1}) = {result_nonneg}")

# Case 2: x_i >= 1 (positive integers)
# Give each variable 1, then distribute remaining
remaining = target_sum - n_variables
result_positive = int(comb(remaining + n_variables - 1, n_variables - 1, exact=True))
print(f"\nPositive integer solutions (each x_i ≥ 1):")
print(f"  Remaining after giving 1 to each: {remaining}")
print(f"  C({remaining}+{n_variables}-1, {n_variables}-1) = C({remaining+n_variables-1}, {n_variables-1}) = {result_positive}")

# Verify by enumeration (non-negative case)
count = 0
solutions = []
for x1 in range(target_sum + 1):
    for x2 in range(target_sum + 1 - x1):
        x3 = target_sum - x1 - x2
        if x3 >= 0:
            count += 1
            if count <= 8:
                solutions.append((x1, x2, x3))

print(f"\nVerification by enumeration: {count} solutions")
print(f"\nFirst 8 solutions (x1, x2, x3):")
for i, sol in enumerate(solutions, 1):
    print(f"  {i}. {sol} → sum = {sum(sol)}")

Key Takeaways

  1. Multiset permutations: n!n1!⋅n2!⋅…⋅nk!\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!} for objects with repetition
  2. Stars and bars: (n+k−1k−1)\binom{n+k-1}{k-1} for distributing nn identical objects into kk bins
  3. Combinations with repetition: Same formula as stars and bars
  4. Integer equations: Use stars and bars for non-negative integer solutions
  5. Constraints: For xi≥1x_i \geq 1, give each variable 1 first, then distribute remaining

Next Lesson: The Inclusion-Exclusion Principle for counting with overlapping constraints!

Problem Type
Formula
Example
Multiset permutations$\frac{n!}{n_1! n_2! \cdots n_k!}$MISSISSIPPI: $\frac{11!}{1!4!4!2!}$
Stars and bars$\binom{n+k-1}{k-1}$10 candies, 4 kids: $\binom{13}{3}$
Combinations w/ repetition$\binom{k+n-1}{n-1}$3 scoops, 5 flavors: $\binom{7}{4}$
Integer solutions$\binom{n+k-1}{k-1}$$x_1+x_2+x_3=10$: $\binom{12}{2}$
🎲

Combinatorics and Probability: From Counting to Inference

Master the mathematical foundations of counting, probability, and randomness. This comprehensive course bridges pure combinatorics with computational probability, covering everything from basic counting principles to advanced probabilistic methods, limit theorems, and real-world applications in algorithms, finance, and data science.