Number of urns with more than K balls inside 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?
 A: 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.
A: 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);

