Distributing $x$ identical balls into $p$ distinct boxes, what is the probability that there are at most $n$ balls in any of the boxes?

Question

I'm trying to figure out this problem when distributing $x$ identical balls randomly into $p$ distinct boxes. How can we compute the number of ways that there are at most $n$ balls in any of the boxes?

It seems that if $n <= x/2$, I cannot simply calculating the solution by putting $n$ balls in some box and calculate $\binom{x - n + p - 1}{p - 1} * p$.

For example, if $x=8, p=4, n=3$, $\binom{8}{3} * 4$ = 224, but the total number of ways is $\binom{8+4-1}{4-1} = \binom{11}{3} = 165$. It seems that some of the combinations are double counted, but I can't figure out a simple formula for solving this problem. Can anyone help?

Answer 1

Suppose we are distributing $n$ balls into $p$ bins with a maximum of $m$ balls per bin. For the case with no maximum we get

$$[z^n] \frac{1}{(1-z)^p} = {n+p-1\choose p-1},$$

which is stars-and-bars. With the restriction we get

$$[z^n] (1+z+\cdots+z^m)^p = [z^n] \frac{(1-z^{m+1})^p}{(1-z)^p} \\ = \sum_{q=0}^{\lfloor n/(m+1) \rfloor} {p\choose q} (-1)^q [z^{n-q(m+1)}] \frac{1}{(1-z)^p} \\ = \sum_{q=0}^{\lfloor n/(m+1) \rfloor} {p\choose q} (-1)^q {n+p-1-q(m+1) \choose p-1}.$$

The probability is then given by

$$\bbox[5px,border:2px solid #00A000]{ {n+p-1\choose p-1}^{-1} \sum_{q=0}^{\lfloor n/(m+1) \rfloor} {p\choose q} (-1)^q {n+p-1-q(m+1) \choose p-1}.}$$

This closed form was verified with an enumeration routine, which helps to clarify the problem definition that was used.

with(combinat);

ENUM :=
proc(n,p,m)
option remember;
local perm, pos, len, src, res;

    res := 0;
    src := [B$n, S$(p-1)];

    for perm in permute(src) do
        len := 0;

        for pos to n+p-1 do
            if perm[pos] = S then
                if len > m then
                    break
                else
                    len := 0;
                fi;
            else
                len := len + 1;
            fi;
        od;

        if pos = n+p then
            if perm[pos-1] = S or len <= m then
                res := res + 1;
            fi;
        fi;
    od;

    res;
end;

CFX := (n,p,m) ->
add(binomial(p,q)*(-1)^q*binomial(n+p-1-q*(m+1),p-1),
    q=0..floor(n/(m+1)));