Number of urns with more than K balls inside

Question

I have a probability problem that I have simplified down to the following:

Given M balls that are thrown randomly (uniformly) into N urns, what is the expected number of urns that have more than K balls inside?

Answer 1

Extending the method given by user Henry in 119076, the probability that each urn has more than $K$ balls inside is

$1-\sum_{i=0}^{K}\frac{M^{i}(N-1)^{M-i}}{N^{M}}$

which means that the number of bins that have more than K balls inside would be $N$ times the probability for a single urn, or

$N(1-\sum_{i=0}^{K}\frac{M^{i}(N-1)^{M-i}}{N^{M}})$

Basically, you calculate the probability that an urn has of having 0, 1, 2, ... K balls inside, and subtract that probability from 1.

Answer 2

Starting with the combinatorial class of sets with size more than $K$ marked we find

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=N}(\textsc{SET}_{\le K}(\mathcal{Z}) +\mathcal{U} \times \textsc{SET}_{\gt K}(\mathcal{Z}))$$

and build the generating function

$$G(z, u) = \left(u \exp(z) + (1-u) \sum_{q=0}^K \frac{z^q}{q!}\right)^N.$$

The expectation is then given by

$$\frac{1}{N^M} M! [z^M] \left. \frac{\partial}{\partial u} G(z, u) \right|_{u=1} \\ = \frac{1}{N^{M-1}} M! [z^M] \left. \left(u \exp(z) + (1-u) \sum_{q=0}^K \frac{z^q}{q!}\right)^{N-1} \left(\exp(z) - \sum_{q=0}^K \frac{z^q}{q!}\right) \right|_{u=1} \\ = \frac{1}{N^{M-1}} M! [z^M] \exp((N-1)z) \left(\exp(z) - \sum_{q=0}^K \frac{z^q}{q!}\right) \\ = \frac{1}{N^{M-1}} M! [z^M] \left(\exp(Nz) - \exp((N-1)z) \sum_{q=0}^K \frac{z^q}{q!}\right).$$

Simplifying,

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

Here we may suppose that $M\gt K$ because we get zero by inspection otherwise. We thus have

$$N - \frac{1}{N^{M-1}} M! \sum_{q=0}^K \frac{1}{q!} \frac{(N-1)^{M-q}}{(M-q)!}$$

or

$$\bbox[5px,border:2px solid #00A000]{ N - \frac{1}{N^{M-1}} \sum_{q=0}^K {M\choose q} (N-1)^{M-q}.}$$

We can verify this formula by enumeration, which is shown below.

with(combinat);

ENUMX :=
proc(N, M, K)
    option remember;
    local res, part, psize, mset, adm;

    res := 0;

    part := firstpart(M);

    while type(part, `list`) do
        psize := nops(part);
        mset := convert(part, `multiset`);

        adm :=
        nops(select(ent -> ent > K, part));

        res := res + adm * binomial(N, psize) *
        M!/mul(p!, p in part) *
        psize!/mul(p[2]!, p in mset);

        part := nextpart(part);
    od;

    res/N^M;
end;

X := (N, M, K)
-> N - 1/N^(M-1)
*add(binomial(M,q)*(N-1)^(M-q), q=0..K);