3
$\begingroup$

Occupancy problem with balls and boxes. Suppose there are $N$ balls and $M$ boxes. The balls are thrown to the boxes at random. What is the probability of $k$ boxes contain exactly $1$ ball? where $k=1,2,...\min(N,M)$

$\endgroup$
  • $\begingroup$ Exactly 1 or at least 1? $\endgroup$ – Henry May 19 '14 at 12:05
  • $\begingroup$ I mean exactly 1 ball $\endgroup$ – robithoh May 19 '14 at 12:20
3
$\begingroup$

What is the chance there are exactly $k$ boxes with a single ball?

For $1\leq i\leq N$, define $A_i$ to be the event that the $i$th box gets exactly one ball. These are exchangeable events whose intersections have multinomial probability $$P(A_1\cdots A_j)={M \choose 1,1,1,\dots,1,M-j}\left({1\over N}\right)^{1}\cdots \left({1\over N}\right)^{1}\left(1-{j\over N}\right)^{M-j}$$ and so by inclusion-exclusion, the probability that there are exactly $k$ boxes with a single ball is $$p(k)=\sum_{j=k}^{\min(M,N)} (-1)^{j-k} {j\choose k}{N\choose j}{M\choose j} \,j! \,\left({1\over N}\right)^j\left(1-{j\over N}\right)^{M-j}.$$

For example, according to this formula with $M=6$ balls and $N=8$ boxes, the chance that exactly six boxes get a single ball is $$p(6)={315\over 4096}={20160\over 8^6}\approx .07690,$$ exactly as in Marko Riedel's answer.

$\endgroup$
  • $\begingroup$ (+1). I had tried inclusion-exclusion but for some reason couldn't get it to work. $\endgroup$ – Marko Riedel Jul 31 '15 at 16:09
  • $\begingroup$ @MarkoRiedel Thanks. I like your approach as well, and I upvoted :) $\endgroup$ – user940 Jul 31 '15 at 16:11
2
$\begingroup$

The interpretation here is that the balls are distinguishable as are the boxes. This gives the combinatorial species

$$\mathfrak{S}_{=M}(\mathcal{E} + \mathcal{U}\mathcal{Z} + \mathfrak{P}_{\ge 2}(\mathcal{Z})).$$

This translates into the bivariate generating function with $z$ representing the number of balls and $u$ the number of boxes with a single occupant:

$$G(z, u) = (\exp(z)-z+uz)^M.$$

Observe that $$N! [z^N] G(z, 1) = N! [z^N] \exp(Mz) = M^N,$$ as it ought to be.

It follows that the count of configurations with $k$ boxes with a single occupant is $$N! [z^N] {M\choose k} z^k (\exp(z)-z)^{M-k} = N! {M\choose k} [z^{N-k}] (\exp(z)-z)^{M-k}$$

for a probability of $$M^{-N} N! {M\choose k} [z^{N-k}] (\exp(z)-z)^{M-k}.$$

The inner term may be re-written with Stirling numbers to get $$N! {M\choose k} [z^{N-k}] \sum_{p=0}^{M-k} {M-k\choose p} (\exp(z)-1)^p (1-z)^{M-k-p} \\ = N! {M\choose k} \sum_{p=0}^{M-k} {M-k\choose p} \times p! \\ \times \sum_{q=0}^{N-k} \frac{1}{(N-k-q)!} {N-k-q\brace p} (-1)^{q} {M-k-p\choose q}.$$

The preceding sum may be subjected to additional algebra but no significant simplification was found by this writer.

The following Maple code was used to compare the results from total enumeration to the formulae presented above.

with(combinat, stirling2);

Q :=
proc(N, M)
    option remember;
    local ind, d, gf, mset, k, p;

    gf := 0;

    for ind from M^N to 2*M^N-1 do
        d := convert(ind, base, M);
        d := [seq(d[q], q=1..N)];

        mset := convert(d, `multiset`);

        k := 0;
        for p in mset do
            if p[2] = 1 then
                k := k + 1;
            fi;
        od;

        gf := gf + u^k;
    od;

    gf;
end;

EX :=
proc(N, M)
    local k, gf;

    gf := 0;

    for k from 0 to min(M,N) do
        gf := gf + u^k *
        N!*binomial(M,k)*coeftayl((exp(z)-z)^(M-k), z=0, N-k)
    od;

    gf;
end;

EX2 :=
proc(N, M)
    local k, gf;

    gf := 0;

    for k from 0 to min(M,N) do
        gf := gf + u^k *
        N!*binomial(M,k)*
        add(binomial(M-k,p)*p!*
            add(1/(N-k-q)!*stirling2(N-k-q,p)*
                (-1)^q*binomial(M-k-p, q), q=0..N-k), p=0..M-k);
    od;

    gf;
end;

For example the distribution of the number of single occupants for six balls in eight boxes is $$20160\,{u}^{6}+100800\,{u}^{4}+33600\,{u}^{3}+80640\,{u}^{2}+20496 \,u+6448.$$

The first coefficient is $20160$ because we must first choose the two boxes that remain empty and distribute a permutation of six distinguishable balls into the remaining six boxes, for a total of $${8\choose 2} \times 6! = 20160.$$

$\endgroup$
0
$\begingroup$

All the option to throw the balls is given by $CC^N _M$ The options in which k boxes contains exactly 1 ball is given by inclusion exclusion formula for the properties: $p_i = $the i'th box contains exactly one ball.

then just divide those to get the probability

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