The number of identical objects to distribute
The number of distinct groups to distribute into
Result
C(n+k-1,k-1)
=
-
About Stars and Bars
The Stars and Bars method (also known as combinations with repetition) is used to solve problems involving the distribution of identical objects into distinct groups.
Formula
The number of ways to distribute n identical objects into k distinct groups is:
\[C(n+k-1,k-1) = \binom{n+k-1}{k-1} = \binom{n+k-1}{n}\]
Example
For n=5 objects and k=3 groups:
- We calculate C(7,2) = C(7,5) = 21
- This means there are 21 different ways to distribute 5 identical objects into 3 distinct groups
- For instance: (5,0,0), (4,1,0), (3,2,0), (2,3,0), (1,4,0), (0,5,0), etc.
Applications
- Distributing identical items among distinct containers
- Finding non-negative integer solutions to equations like x₁ + x₂ + ... + xₖ = n
- Calculating multiset combinations
- Solving problems in probability and statistics
Method Explanation
The method gets its name from representing the problem using:
- Stars (★): representing the identical objects
- Bars (|): separating the distinct groups
For example, with n=5 and k=3:
★★★|★★| represents (3,2,0)
★|★★★★| represents (1,4,0)
Note: For large values of n or k, the result can be a very large number.