Combinations with Repetition

Combinatorics · Axiom Academy

LESSON Combinations with Repetition Learn how to count selections when order doesn't matter and items can be chosen multiple times In combinations with repetition, we select r items from n types , where: Order doesn't matter (like regular combinations) Each type can be selected multiple times We're counting multisets, not sets The animation shows selecting 5 items from 3 types with repetition allowed: The number of ways to choose r items from n types with repetition is: Example: Choosing 5 donuts from 3 flavors: Watch the animation to see why we need n+r-1 total positions: 3. Why This Formula Works: Stars and Bars The formula comes from the "stars and bars" method: Stars (): Represent the r items we're selecting Bars (|): Separate the n types (we need n-1 dividers) Example: 5 donuts from 3 flavors can be represented as: 2 bars (n - 1 = 3 - 1 = 2 dividers) Total: 7 positions (n + r - 1 = 3 + 5 - 1 = 7) We choose which r positions are stars (or equivalently, which n-1 positions are bars): Problem: How many ways can we distribute 4 identical prizes to 3 different people? Solution: This is choosing 4 items (prizes) from 3 types (people) with repetition. n = 3 (types: Person A, Person B, Person C) r = 4 (items: 4 identical prizes) Let's visualize some of the 15 possible distributions: 5. Contrast: With vs Without Repetition Let's compare combinations without and with repetition: Without repetition: Each item used at most once (r cannot exceed n)

This is the written version of the interactive lesson above. See the full Combinatorics course.