Count the number of ways to distribute n identical items into k distinct bins where each bin gets zero or…

Question

Count the number of ways to distribute n identical items into k distinct bins where each bin gets zero or more items (i.e. the number of non-negative integer solutions to x1+...+xk = n). This is the stars-and-bars count C(n+k-1, k-1), taken modulo 10^9+7. Constraints: 0 <= n <= 100000, 1 <= k <= 100000.

Prep Room · Answer

### Intuition The problem maps perfectly to the "stars and bars" combinatorial method. We want to place $N$ identical items into $K$ distinct bins. This is…

Stars and bars