Combinations with Repetition

Calculate multiset combinations (Stars and Bars method)

Multiset coefficient: Number of ways to choose k objects from n with repetition allowed

Multiset Calculator

Combinations with Repetition

Calculates ((n,k)) - the number of ways to choose k objects from n with repetition allowed, without regard to order.

Number of different object types
Number of objects to choose (k can be > n)
Calculation Result
((n,k)) =

Multiset Example

Default Example: ((3,2))
Object types: n = 3
Selection: k = 2
Result: ((3,2)) = 6
6 different 2-element multisets from 3 object types
Concrete Example: Objects {A, B, C}

Possible 2-element combinations with repetition:

{A,A} {A,B} {A,C} {B,B} {B,C} {C,C}

((3,2)) = 6 multisets

Stars and Bars Visualization

k=2 stars, n-1=2 separator bars:

**|·|· *|*|· *|·|* ·|**|· ·|*|* ·|·|**

6 arrangements of 2 stars and 2 bars

Stars and Bars Method

The Stars and Bars method is the classic method for calculating combinations with repetition:

Stars
\[\text{k stars = k objects to select}\]

Each star represents one selected object

Bars
\[\text{(n-1) bars = separation between n object types}\]

Bars separate the different object categories

Multiset Formulas and Examples

Multiset Coefficient Formula
\[\left(\binom{n}{k}\right) = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k! \cdot (n-1)!}\]

Number of k-multisets of an n-set (with repetition)

Step-by-Step Calculation: ((3,2))

Given: n = 3 object types, k = 2 selection

1. Apply multiset formula:

\[\left(\binom{3}{2}\right) = \binom{3+2-1}{2} = \binom{4}{2}\]

2. Calculate binomial coefficient:

\[\binom{4}{2} = \frac{4!}{2! \cdot (4-2)!} = \frac{4!}{2! \cdot 2!}\]

3. Substitute factorials:

\[\binom{4}{2} = \frac{4 \times 3 \times 2!}{2! \times 2!} = \frac{4 \times 3}{2 \times 1} = \frac{12}{2} = 6\]
Stars and Bars Interpretation

Problem: Distribute 2 stars among 3 categories

Solution: 2 stars + 2 separator bars = 4 positions

Calculation: C(4,2) ways to choose 2 positions for stars

Possible arrangements:

**|·|· *|*|· *|·|* ·|**|· ·|*|* ·|·|**

Interpretation: {A,A}, {A,B}, {A,C}, {B,B}, {B,C}, {C,C}

Additional Calculation Examples
Calculate ((4,3)):
\[\left(\binom{4}{3}\right) = \binom{4+3-1}{3} = \binom{6}{3} = 20\]
Calculate ((2,5)):
\[\left(\binom{2}{5}\right) = \binom{2+5-1}{5} = \binom{6}{5} = 6\]
((n,1)) - Special case:
\[\left(\binom{n}{1}\right) = n\]
((1,k)) - Special case:
\[\left(\binom{1}{k}\right) = 1\]
Comparison: With vs. Without Repetition
Without Repetition

C(n,k) = n!/(k!(n-k)!)

Example: C(3,2) = 3

{A,B}, {A,C}, {B,C}

With Repetition

((n,k)) = (n+k-1)!/(k!(n-1)!)

Example: ((3,2)) = 6

{A,A}, {A,B}, {A,C}, {B,B}, {B,C}, {C,C}

Multiset Reference

Default Example
((3,2)) = 6 C(4,2) = 6 12/2 = 6
Special Values

((n,0)) = 1: Empty selection

((n,1)) = n: Single selection

((1,k)) = 1: Only one object type

((n,2)) = n(n+1)/2: Pairs with rep.

Stars and Bars

Stars: k objects to distribute

Bars: (n-1) separators

Positions: k + (n-1) = n+k-1

Selection: C(n+k-1, k)

Applications

Distribution: Objects to containers

Polynomials: Terms with repetition

Probability: Drawing with replacement

Partitions: Number decompositions

Combinations with Repetition - Detailed Description

Multisets and Repetition

Combinations with repetition extend the classic combination problem by allowing the same element to be chosen multiple times. The result are multisets - sets where elements can occur multiple times.

Characteristics:
• Order is irrelevant: {A,B,A} = {A,A,B}
• Repetition allowed: Elements can be chosen multiple times
• k can be greater than n
• Multiset coefficient as mathematical representation

Stars and Bars Method

The Stars and Bars method is an elegant combinatorial approach: k identical objects (stars) are distributed into n different categories (separated by n-1 bars). This leads to the formula C(n+k-1, k).

Visualization

**|*|· means: 2 objects of type A, 1 object of type B, 0 objects of type C
Total k+n-1 positions, from which k are chosen for stars

Practical Applications

Multiset combinations are essential for distribution problems: from dividing identical objects among different containers to analyzing probability distributions with replacement.

Typical Scenarios:
• Distributing candy to children
• Coin flips with repetition
• Inventory distribution problems
• Polynomial coefficients

Comparison to Regular Combinations

The main difference lies in allowing repetition: While C(n,k) only allows different elements, ((n,k)) allows arbitrary repetitions, leading to larger results, especially when k > n.

Mathematical Intuition

The transformation to C(n+k-1, k) "expands" the original set by k-1 additional elements to account for the repetitions.

Practical Examples and Applications

Candy Distribution

Problem: 5 candies to 3 children

Calculation: ((3,5))

Result: C(7,5) = 21 possibilities

Meaning: Fair distribution options

Coin Flip Sequences

Problem: 4 flips, heads/tails

Calculation: ((2,4))

Result: C(5,4) = 5 combinations

Meaning: Different H/T distributions

Polynomial Coefficients

Problem: (x+y+z)³ terms

Calculation: ((3,3))

Result: C(5,3) = 10 terms

Meaning: Multinomial expansion

Multiset vs. Other Counting Principles
  • Multiset: ((n,k)) - Order irrelevant, with repetition
  • Combinations: C(n,k) - Order irrelevant, without repetition
  • Variations with rep.: n^k - Order matters, with repetition
  • Urn model: Drawing with replacement, order irrelevant
  • Partitions: Decomposing numbers into summands
  • Multinomial: (a₁+a₂+...+aₙ)^k coefficients


Other Combinatorics Functions

Combinations with Repetition  •  Combinations without Repetition  •  Permutations  •  Rule of Product  •  Variations with Repetition  •  Variations without Repetition  •  Activity Selection Problem  •