stars and bars variation - lower bound constraints

Topics

• combinatorics

In standard stars and bars method, we distribute n identical objects into k distinct bins. The formula comes out to be: comb(n+k-1, k-1). A variation of this problem can be:

Minimum Constraints (At Least One in Each Bin)

What if each bin (kid) must get at least one object?

• Instead of distributing n objects, first give 1 to each bin
• We now have n-k objects left to distribute freely

Modified formula:

$$\text{Ways}=\left(\genfrac{}{}{0ex}{}{(n-k)+k-1}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$$

Note

This can be generalized to atleast $a_i$ objects for kid $a$. In this case, give min items to each kid ⇒ remainder is $n-{\sum }_i{a}_i$ which needs to be distributed to the kids.

Related