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.