2
$\begingroup$

So I was trying to find the number of ways to distribute $N$ dinstinct balls into $K$ distinct boxes so that exactly $I$ out of $K$ boxes have exactly one ball in each $\left( I \geq 0 \right)$. I know that there is already a similar question which was solved using the Generating Function method. However, without using the Generating Function, I tried to solve it as follows:

Assume that there are $J$ multiple-balls boxes. The constraints on the variables are then:

  • $0 \leq J \leq \left \lfloor{\frac{N-I}{2}}\right \rfloor $ (since each of the $J$ boxes must contain at least 2 balls)

  • If $N \leq K$ and $J = 0$, then $I$ must equal $N$

  • If $N < K$, then $I \neq N-1$ or else there is a case where we are left with one ball that cannot be placed in any box

  • $I + J \leq K$

  • $(I ,J) \neq (0,0)$

  • If $N > K$, then $I \leq K-1$ (in this case there can be, at most, $K-1$ single-ball boxes)

With those lengthy constraints out of the way, i try to follow these steps:

  1. Number of ways to pick $I$ single-ball boxes: $K \choose I$
  2. Number of ways to pick $I$ balls from $N$ balls and permute them inside the $I$ boxes: $\frac{N!}{\left( N-I \right)!}$
  3. Number of ways to pick $J$ multiple-balls boxes: ${K-I \choose J}$
  4. Number of ways to distribute $N-I$ balls into $J$ boxes so that each of the $J$ boxes has multiple (more than one) balls: Let's assume that we know it and denote it by $f(N-I,J)$. Actually, this is a question that i asked recently

The total number of ways is then: \begin{equation} \displaystyle{\sum_{J}}{K \choose I}{K-I \choose J}\frac{N!}{(N-I)!}f(N-I,J), \end{equation} where all variables are subjected to aforementioned constraints. For simplicity, let's assume the case of $N < K$ first. With that, this equation becomes:

\begin{equation} \displaystyle{N!{K \choose N}+\sum_{J=1}^{\left \lfloor{\frac{N-I}{2}}\right \rfloor}}{K \choose I}{K-I \choose J}\frac{N!}{(N-I)!}f(N-I,J) \end{equation}

When summing this equation over all values of $I$ (from $0$ to $N$), I should always be getting the total number of ways to distribute $N$ distinct balls into $K$ distinct boxes i.e., $K^N$. However, when I tried it with different $N$ (where $N < K$), sometime I get the correct result while sometime I don't. For example, at $K=18$, I got correct result until $N$ reaches 15.

I want to ask about the flaws of this approach. Any help would be greatly appreciated. Thank you.

Edit: I also tested the solution given by N. Shales in this, which is:

$$\text{desired count}=\left[\frac{x^N}{N!}\right]f(x)= \begin{cases} \displaystyle\binom{K}{I}N!\sum_{j=\max(0,K-N)}^{K-I}(-1)^{K-I-j}\binom{K-I}{j}\frac{j^{N-K+j}}{(N-K+j)!}&,\, N\ge I\\ 0&,\, \text{else}. \end{cases} $$

However, his solution is also only accurate up to a certain value of $N$ (with fixed $K$). For example, at $K = 18$ and $N = 10$, the sum of his solution over all possible values of $I$ does not equal $K^N$. I am not sure if there is a GENERAL solution for this kind of problem?

$\endgroup$
0
$\begingroup$

It took me a while to figure out what's wrong, and why does it only works for a limited number of cases although my solution and the solutions using Generating Function method produce the same result. Turned out that maybe the culprit is the precision limit of MATLAB (which i used to check the correctness of the answers). The factorial and binomial coefficients (given $K$ and $N$ are big enough) are too big to fit in standard integer types supported by MATLAB. I am trying to find another way to exactly calculate the numbers (one possible option is using symbols instead of numbers).

$\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.