1. ## Distribution problem

Hi,

I have the following problem, which at first I thought should be really simple, but so far I can't seem to find any solution to this:

Say I have a number of equal items that are to be distributed between a number of bins, like N pieces of cake that are to be distributed between M children. The number of possible distributions for this is (N over (M-1)).

However, let's say I want to limit the number of items per bin to, say, 2? So I want to distribute the N pieces of cake between the M children, without any child getting more than 2 pieces of cake (assuming there are at least N/2 children). Does anyone have any suggestions how I can count the number of possibilities in this case?

Henrik

2. Originally Posted by henrikbe
Say I have a number of equal items that are to be distributed between a number of bins, like N pieces of cake that are to be distributed between M children. The number of possible distributions for this is (N over (M-1)).
I don't agree with that. The number of ways of allocating N identical objects (or cakes) among M distinct bins (or children) is the binomial coefficient $N+M-1\choose N$.

Originally Posted by henrikbe
However, let's say I want to limit the number of items per bin to, say, 2? So I want to distribute the N pieces of cake between the M children, without any child getting more than 2 pieces of cake (assuming there are at least N/2 children). Does anyone have any suggestions how I can count the number of possibilities in this case?
Let K denote the number of children who receive at least one piece of cake. It's clear that at least $\lceil N/2\rceil$ children must receive at least one piece of cake (where $\lceil N/2\rceil$ means the least integer greater than or equal to N/2). The greatest number of children who can receive at least one piece of cake is M or N, whichever is smaller.

Therefore K can be any number between $\lceil N/2\rceil$ and $\min\{M,N\}$. For each such value of K, we can give one piece of cake to each of those K children. There will then be N–K remaining pieces of cake, which allows N–K lucky children to receive a second piece of cake.

There are $M\choose K$ ways of choosing the children who receive at least one piece. For each such choice, there are $K\choose N-K$ ways to choose the lucky children who get 2 pieces. Thus the total number of ways of allocating the cakes is $\boxed{ \sum_{K=\lceil N/2\rceil}^{\min\{M,N\}}{M\choose K}{K\choose N-K}}$. I don't see any way to simplify that answer.