Krdytkyu

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?

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

$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{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 $Mgt 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 {Mchoose 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);

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.