The total number of ways to put $N$ distinct balls into $K$ distinct boxes so that every box has more than one ball (assuming that $N \geqslant 2K$)

So i came across the general combinatoric problem as stated in the title. I have $N$ distinct balls and $K$ distinct boxes $\left( N \geqslant 2K \right)$. I need to find the total number of ways to arrange these balls in these boxes so that every box has more than one ball.

Any help would be greatly appreciated. Thank you.

• did you try to attack it with inclusion-exclusion? if the constraint were "at least one" that would certainly work out (you'd get Stirling numbers of the second kind). This seems at a glance just slightly more complicated. Commented Apr 26, 2017 at 3:24
• The inclusion-exclusion method works well for the case of indistinguishable boxes, but i think this is not the case. Furthermore, "each box has at least one" and "each box has at least two" can be drastically different when all boxes and balls are distinct.
– bui
Commented Apr 26, 2017 at 3:46
• inclusion-exclusion works quite well for distinguishable boxes, i.e. the problem of counting surjective functions. I agree that the "at least one" and "at least two" cases can be drastically different, but here I don't think they are. Commented Apr 26, 2017 at 3:51
• For fixed $K$ the exponential generating function is $(e^x-1-x)^K,$ so the number of ways is equal to the $N^{\text{th}}$ derivative of $(e^x-1-x)^K$ evaluated at $x=0.$
– bof
Commented Apr 26, 2017 at 3:57
• @bof I have tried evaluating your mentioned derivative at $x = 0$ using MATLAB, but the result is always 0 regardless of the order of the derivative
– bui
Commented Apr 26, 2017 at 4:32

Let $P_j^0$ be all ball-box arrangements such that the $jth$ box contains exactly $0$ balls, and let $P_j^1$ be similarly those in which the $jth$ box contains exactly 1 ball.

The total number of ball-box arrangements is $K^N$, so the number you are looking for is $K^N - \big| \bigcup\limits_{j=1}^{K} P_j^0 \cup P_j^1 \big|$. Inclusion exclusion is how you'll approach that big union.

You can attack it straight on because the number of ball-box arrangements having $J$ particular boxes empty and disjoint $I$ particular boxes containing exactly one ball is easily calculated. We pick $I$ of our $N$ balls and permute them into the designated boxes, and then accounting for the $J$ boxes that are off limits, we have $N-I$ balls to put into $K - J - I$ boxes. In other words, if $A_I$ and $A_J$ are disjoint subsets of $[1,\ldots,K]$ with $|A_I| = I$ and $|A_J| = J$, then

$$\big| \bigcap\limits_{j \in A_J} P_j^0 \cap \bigcap\limits_{i \in A_I} P_i^1 \big| = \frac{N!}{(N-I)!} (K - I - J)^{N-I}$$

To account for all of the ways to choose $J$ and $I$ such boxes, you have a multiplicative factor of ${{K} \choose {I}} {{K-I} \choose {J}}$

The theorem of inclusion exclusion gives you that

$$\big| \bigcup\limits_{j=1}^{K} P_j^0 \cup P_j^1 \big| = \sum_{A_I,A_J \subset [1,\ldots,K] \\ A_I \cap A_J = \emptyset} (-1)^{I+J+1} \big| \bigcap\limits_{j \in A_J} P_j^0 \cap \bigcap\limits_{i \in A_I} P_i^1 \big|$$

so with the above observations you should be all set! (we're summing over all ways to pick two disjoint subsets of the boxes.)

This post on Stirling numbers of the second kind may be helpful, since this application of inclusion-exclusion is just a slightly more complicated version of that one.

• Sorry if i misunderstand it, but doesn't your multiplicative term of $\left(K-I-J\right)^{N-I}$ also includes all the cases where each of the remaining $\left(K-J-I\right)$ boxes can contain either 0, 1 or more than 1 ball? If it's so, then the number of single-ball boxes may not be $I$ anymore.
– bui
Commented Apr 26, 2017 at 4:27
• No it's my fault, the notation is too sparse. The number of single ball boxes likely isn't $I$ anymore, nor is the number of empty boxes $J$, I meant to be summing over a particular index set. i'll update for clarity Commented Apr 26, 2017 at 4:37
• I mean that, if you are assuming that there are $I$ single-ball boxes, $J$ no-ball boxes and $K-I-J$ more-than-one-ball boxes, then the new problem is, again, finding the total number of ways to distribute $N' = N-I$ balls into $K' = K-I-J$ boxes so that each box get more than one ball. That is no different from the original problem but just a change in the value of $N$ and $K$.
– bui
Commented Apr 26, 2017 at 4:42
• I'm not assuming anything about the other $K-I-J$ boxes, that's the crux of inclusion-exclusion. All of the overcounting is dealt with by adding/subtracting the number of ball-box arrangements for other sizes of $I,J$ Commented Apr 26, 2017 at 4:45
• Sorry that i took so long to reply. I am not familiar with counting and it took me a while to (intuitively) grasp the inclusion-exclusion method. A small problematic part is that we must also include the sum over all value pair of $\left( I,J \right)$ given that $\left( I + J \right)$ is a fixed value somewhere between $1$ and $K$. I have one more question: should we also count the cases where $I=0$ and/or $J=0$? From my understanding, we should.
– bui
Commented Apr 26, 2017 at 5:47

For Inclusion-Exclusion, let us count the number of ways that $j$ of the $K$ bins have less than $2$ of the $N$ balls. We will break things down into cases where $i$ of the bins have $1$ ball and $j-i$ have $0$ balls:

Choose the $j$ bins to have less than $2$: $\binom{K}{j}$
Choose $i$ of those $j$ bins to have $1$ ball: $\binom{j}{i}$
Choose $i$ of the $N$ balls for those $i$ bins: $\binom{N}{i}$
Choose an order for those $i$ balls: $i!$
Fill in the remaining $K-j$ bins with the remaining $N-i$ balls: $(K-j)^{N-i}$

Therefore, $$N(j)=\sum_{i=0}^j\binom{K}{j}\binom{j}{i}\binom{N}{i}i!(K-j)^{N-i}\tag{1}$$ Thus, \newcommand{\stirtwo}[2]{\left\{#1\atop#2\right\}} \begin{align} \sum_{j=0}^K(-1)^jN(j) &=\sum_{j=0}^K(-1)^j\sum_{i=0}^j\binom{K}{j}\binom{j}{i}\binom{N}{i}i!(K-j)^{N-i}\tag{2}\\ &=\sum_{j=0}^K(-1)^j\sum_{i=0}^j\binom{K}{i}\binom{K-i}{j-i}\binom{N}{i}i!\sum_m\stirtwo{N-i}{m}\binom{K-j}{m}m!\tag{3}\\ &=\sum_{i=0}^K\binom{K}{i}\binom{N}{i}i!\sum_m\stirtwo{N-i}{m}m!\sum_{j=i}^K(-1)^j\binom{K-i}{j-i}\binom{K-j}{m}\tag{4}\\ &=\sum_{i=0}^K\binom{K}{i}\binom{N}{i}i!\sum_m\stirtwo{N-i}{m}m!\sum_{j=i}^K(-1)^j\binom{K-i}{K-j}\binom{K-j}{m}\tag{5}\\ &=\sum_{i=0}^K\binom{K}{i}\binom{N}{i}i!\sum_m\stirtwo{N-i}{m}m!\sum_{j=i}^K(-1)^j\binom{K-i}{m}\binom{K-i-m}{K-j-m}\tag{6}\\ &=\sum_{i=0}^K\binom{K}{i}\binom{N}{i}i!\stirtwo{N-i}{K-i}(K-i)!(-1)^i\tag{7}\\ &=\bbox[5px,border:2px solid #C0A000]{K!\sum_{i=0}^K(-1)^i\binom{N}{i}\stirtwo{N-i}{K-i}}\tag{8} \end{align} Explanation:
$(2)$: Inclusion-Exclusion and $(1)$
$(3)$: $\binom{K}{j}\binom{j}{i}=\binom{K}{i}\binom{K-i}{j-i}$ and $(K-j)^{N-i}=\sum\limits_m\stirtwo{N-i}{m}\binom{K-j}{m}m!$
$(4)$: rearrange terms and order of summation
$(5)$: $\binom{K-i}{j-i}=\binom{K-i}{K-j}$
$(6)$: $\binom{K-i}{K-j}\binom{K-j}{m}=\binom{K-i}{m}\binom{K-i-m}{K-j-m}$
$(7)$: $\sum\limits_{j=i}^K(-1)^j\binom{K-i-m}{K-j-m}=(-1)^i[m=K-i]$
$(8)$: $\binom{K}{i}i!(K-i)!=K!$

where the $\stirtwo{n}{k}$ are the Stirling Numbers of the Second Kind.

• Thank you for your solution. This is another way to interpret the Inclusion-Exclusion method and should yield the same result as in Badam's solution :)
– bui
Commented Apr 26, 2017 at 8:09
• I think that reducing the double sum to a single sum makes the answer a bit more palatable.
– robjohn
Commented Apr 26, 2017 at 8:14
• I like this reduction to a single sum! It's good to show the connection to the Stirling numbers of the second kind. Originally I guessed this was a homework problem so I was trying (in many iterations) not to provide a full answer, but I would definitely prefer to write it this way in the end. The only merit in leaving it as double sum is that it's somewhat "transparent". To solve the problem we had to decompose the $K$ propositions "box j has less than 2 balls" into the $2K$ propositions "...has exactly one..." and "...has exactly 0..." Commented Apr 26, 2017 at 13:56
• For those interested in $(K-j)^{N-i}=\sum\limits_m{N-i\brace m}\binom{K-j}{m}m!$. Commented Jan 14, 2022 at 15:40

The combinatorial species here is the labeled species $\mathfrak{S}_{=K}(\mathfrak{P}_{\ge 2}(\mathcal{Z}))$ which gives the generating function

$$(\exp(z)-z-1)^K.$$

The desired statistic is then given by

$$N! [z^N] (\exp(z)-z-1)^K = N! [z^N] \sum_{q=0}^K {K\choose q} (-1)^q z^q (\exp(z)-1)^{K-q} \\ = N! \sum_{q=0}^K {K\choose q} (-1)^q [z^{N-q}] (\exp(z)-1)^{K-q} \\ = N! K! \sum_{q=0}^K \frac{1}{q!} (-1)^q [z^{N-q}] \frac{(\exp(z)-1)^{K-q}}{(K-q)!} \\= N! K! \sum_{q=0}^K \frac{1}{q! (N-q)!} (-1)^q (N-q)! [z^{N-q}] \frac{(\exp(z)-1)^{K-q}}{(K-q)!} \\= K! \sum_{q=0}^K {N\choose q} (-1)^q {N-q\brace K-q}.$$

This matches the answer by @robjohn.

First find the number of ways to put 2 balls into every box. Since the balls are distinguishable, there are $N\choose{2K}$ ways to pick $2K$ balls, and there are $\frac{(2K)!}{2^K}$ ways to divvy those $2K$ balls into the $K$ distinguishable boxes (think of lining up all $2K$ balls where the first two go into box 1, the next two into box 2, etc. There are $(2K)!$ possible line-ups, but the order of the $K$ pairs does not matter, so we should divide by $2^K$)

Then, for the remaining $N-2K$ balls you have $K^{N-2K}$ options to distribute those.

Now multiply all those together:

$$\frac{{N\choose{2K}}(2K)!K^{N-2K}}{2^K}$$

EDIT

This does NOT work, since it overcounts: I could initially pick a pair of balls A and B to go into some box, and later add ball C, but I could also initially pick pair A and C, and later add B. This ends up with the same balls in that box, but the above calculation counts these as different. :(

I'll leave this flawed formula up here until someone finds the actual correct formula ... Maybe it's still of some use, if only to show what does NOT work!

• But please do note that all the balls and boxes are distinguishable. In that sense, can the way of choosing the 2 balls into every boxes affect the result?
– bui
Commented Apr 26, 2017 at 2:33
• Oh, You should definitely add that to the problem statement! Commented Apr 26, 2017 at 2:34
• The "distinct" property was right there from the beginning, both in my problem statement and the title
– bui
Commented Apr 26, 2017 at 2:35
• @UnknownGuy Quite, my bad! OK, yes, of course that changes the answer ... I updated it Commented Apr 26, 2017 at 2:45
• I think your new solution may overcount the number of possibilities. It is true that the order of the 2-ball pair does not matter. However, it is also true that the order of the balls in a particular boxes also does not matter. Thus, there is a chance that the 2-ball you selected for one box may re-appear in that box in other combinations
– bui
Commented Apr 26, 2017 at 2:54