1
$\begingroup$

As a part of a greater question, I stumbled upon the following problem:

Let's suppose we have $n$ balls and $k$ bins. Bins are numbered $b_1, b_2, b_3,...b_k$.
Let $N[b_i]$ be the number of balls inside the $i$th bin. In how many ways can I place $n$ balls inside the $k$ bins such as $N[b_1] \geq N[b_2] \geq N[b_3] \geq ... \geq N[b_k]$?

As an example, if we have 4 balls and 3 bins, the possibilities are:
[4,0,0], [3,1,0], [2,2,0], [2,1,1].

Every help is much appreciated.

$\endgroup$
2
$\begingroup$

You seek the number of partitions of $n$ into at most $k$ parts. See here for background. Unfortunately there is no nice closed form, but the answer you seek is $$p_1(n)+p_2(n)+\cdots+p_k(n)$$ where $p_i(m)$ denotes the number of partitions of $m$ into exactly $i$ parts.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.