Course contentsShow
← Mathematics
Lesson 2615 of 3,12152. CombinatoricsFree lesson

Relationship to Combinations and Stars-and-Bars

Connect multinomial coefficients to combinations and recognize when to use stars-and-bars versus multinomial counting.

Relationship to Combinations and Stars-and-Bars

What you'll learn: How multinomial coefficients connect to combinations and when to choose stars-and-bars versus multinomial counting for distribution problems.

The Core Connection

Both multinomial coefficients and stars-and-bars solve distribution problems, but they handle different scenarios:

  • Multinomial coefficients count arrangements of distinguishable objects into labeled groups where order within the arrangement matters (like arranging letters in a word).
  • Stars-and-bars counts distributions of indistinguishable objects into distinguishable bins where only the counts matter (like distributing identical candies into boxes).

When to Use Each Method

Use multinomial coefficients when:

  • Objects have distinct identities (different letters, different people)
  • You're arranging them into categories
  • Example: Ways to arrange MISSISSIPPI = 11!/(1!·4!·4!·2!)

Use stars-and-bars when:

  • All objects are identical (same type of item)
  • You only care about how many go in each category
  • Example: Ways to distribute 10 identical cookies among 3 children = C(10+3-1, 3-1) = C(12,2)

The Bridge: Combinations

Both techniques reduce to combinations in special cases:

  • Multinomial with 2 groups: choosing r objects from n is C(n,r) = n!/(r!(n-r)!)
  • Stars-and-bars: distributing n items into k bins uses C(n+k-1, k-1)

Think of it this way: multinomial answers "Which specific items go where?" while stars-and-bars answers "How many items in each place?"

Key Takeaway: Use multinomial coefficients when objects are distinguishable and you're counting arrangements; use stars-and-bars when objects are indistinguishable and you're counting distributions by quantity alone.