In how many ways can $N$ identical balls be distributed among $3$ persons

combinatorics

In how many ways can $N$ identical balls be distributed among $3$ person, where

  1. each of them gets a distinct number of balls,

  2. and each of them must get at least one ball.

Best Answer

We start with Stars and Bars

Ignoring the first condition, we get $\binom {N-1}2$

Now, we need to subtract off the cases in which two of the people got the same number of balls. If we specify the two people, that's $\big \lfloor \frac {N-1}2\big \rfloor$, since the third person has to get at least $1$. Of course, there are $3$ ways to specify two people.

Now, we see that we have subtracted off the case in which all three people get the same number of balls $3$ times and we only meant to subtract it once. Thus, in the case where $3\,|\,N$ we must add $2$.

Finally we see that the answer is $$ \begin{cases} \binom {N-1}2-3\big \lfloor \frac {N-1}2\big \rfloor & \text{if $3\nmid N$} \\\\ \binom {N-1}2-3\big \lfloor \frac {N-1}2\big \rfloor +2& \text{if $3\,|\,N$} \end{cases}$$

Sanity Check: If $N=9$ this gives $18$. Indeed, the possible triples are $(6,2,1)$, $(5,3,1)$, and $(4,3,2)$ plus their permutations.

Related Question