ROUGH DRAFT authorea.com/100430
Main Data History
Export
Show Index Toggle 0 comments

Multichoosing

How many ways can you distribute \(20\) identical cupcakes to \(8\) hungry children? How many ways can you give out \(15\) identical cookies to \(4\) children if each child must have at least \(3\) cookies?

All of these questions revolve around the topic of multichoosing. Multichoosing in discrete mathematics is another counting problem. In multichoose problems, order is not important and repetition is allowed. Multichoosing is denoted \(\left(\binom{n}{k}\right)\) where \(\left(\binom{n}{k}\right)\) means the amount of ways to choose length \(k\) multisets from a set of \(n\) objects. In general \(\left(\binom{n}{k}\right)\) is where we may say “\(n\) multichoose \(k\).” Notice this is a resembalance with the binomial coefficient \(\binom{n}{k}.\) 

\(\left(\binom{n}{k}\right)\) is shown by the formula: 

Notice that \(\left(n-1,k\right)!\) is the multinomial coefficient. 

Multichoose problems are also referred to as the “stars and bars” method. In general “stars and bars” means the number of ways we can separate \(k\) stars within \(n-1\) bars.

There are a few identities of the stars and bars method:

  • In general \(n\) objects can share \(k\) identical objects in \(\left(\binom{n}{k}\right)\) ways.
  • If each object, well say a candy jar for instance needed at least one candy, the problem changes because we would have to distribute \(k-n\) candies to \(n\) jars and this is shown by: