How many ways can N items be shared by 3 anonymous people

227 Views Asked by At

I will use a specific example to demonstrate my question.

Take 9 items, they can be shared by 3 anonymous people in the following ways:

One person has 9 the other two have none
One person has 8 one has 1 and the other has none
One person has 7 another has 2 and the other has none
One person has 7 and the other 2 have 1
One person has 6 one has 2 and the other has 1
One person has 6 one has 3 and the other has none
One person has 5 one has 3 and the other has 1
One person has 5 and the other two have 2
One person has 5 one has 4 and the other has none
One person has 4 one has 3 and the other has 2
Two people have 4 and the other has 1
All three people have 3

So there are 12 ways of sharing 9 items between 3 people

I believe this equates to the number of distinct coefficients on layer 9 of pascals pyramid.

Is there a formula for N items?

1

There are 1 best solutions below

2
On BEST ANSWER

We are told to count the number $s(n)$ of partitions of $n$ into $\leq3$ nonempty parts. Then $s(1)=1$, $s(2)=2$, $s(3)=3$; and we have the following recursion: $$s(n)=s(n-3)+\left\lfloor{n\over2}\right\rfloor+1\qquad(n\geq4)\ .$$ Proof. An admissible partition $P$ of $n\geq4$ can consist of three parts, two parts, or one part. If it consists of three parts we can take one ball away from each part and obtain an admissible partition of $n-3$. If $P$ consists of two parts there are $\left\lfloor{n\over2}\right\rfloor$ possibilities for the smaller part, hence for $P$.

One obtains the sequence $$(s_n)_{n\geq1}=(1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33, 37, 40, 44,\ldots)\ .$$ This is sequence A001399 at OEIS, where you may find further information.