Picking a sample of N numbered balls

Question

An urn contains $nr$ balls numbered $1,2..,n$ in such a way that $r$ balls bear the same number $i$ for each $i=1,2,...n$. $N$ balls are drawn at random without replacement. Find the probability that exactly $m$ of the numbers will appear in the sample.

Any hints would be great, I tried solving it, finally relented and checked the solution given in the text, I can't seem to understand the working though I get the idea that inclusion-exclusion is the key to solving the problem.

Answer 1

We use the notation from the following MSE link where there are $n$ types of coupons with $j$ instances of each and $m$ coupons being drawn without replacement. We get from first principles for all sequences of draws the mixed generating function

$$\left(\sum_{k=0}^j \frac{j!}{(j-k)!} \frac{z^k}{k!} \right)^n.$$

Here we are partitioning the draws into $n$ sets, one for each type, with $z^k/k!$ representing the size of the set and $j!/(j-k)!$ the weight according to probability. We get for the sum of all weights the closed form

$$m! [z^m] \left(\sum_{k=0}^j \frac{j!}{(j-k)!} \frac{z^k}{k!} \right)^n = m! [z^m] (1+z)^{nj} = m! \times {nj\choose m}.$$

Note also that $(nj)^{\underline{m}}$ gives the denominators of the probabilities while $j^{\underline{k}}$ gives the numerators corresponding to a set of size $k.$

We are interested in the probability that $q$ different types are seen, which gives the marked generating function

$$\left(1 + u\sum_{k=1}^j \frac{j!}{(j-k)!} \frac{z^k}{k!} \right)^n.$$

We thus have for the probability of $q$ different types

$$\frac{1}{m!} {nj\choose m}^{-1} \times m! [z^m] [u^q] \left(1 + u\sum_{k=1}^j \frac{j!}{(j-k)!} \frac{z^k}{k!} \right)^n \\ = \frac{1}{m!} {nj\choose m}^{-1} \times m! [z^m] {n\choose q} \left(\sum_{k=1}^j \frac{j!}{(j-k)!} \frac{z^k}{k!} \right)^q \\ = {nj\choose m}^{-1} [z^m] {n\choose q} \left(-1 + (1+z)^j\right)^q \\ = {nj\choose m}^{-1} [z^m] {n\choose q} \sum_{p=0}^q {q\choose p} (-1)^{q-p} (1+z)^{jp}.$$

We conclude that the desired probability is given by

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

Observing that

$${nj\choose m}^{-1} {jp\choose m} = \frac{(jp)! \times (nj-m)!}{(jp-m)! \times (nj)!}$$

we get the alternate form

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

E.g. for $15$ draws from $10$ types of coupons with $3$ instances of each we obtain the PGF

$${\frac {7\,{u}^{5}}{4308820}}+{\frac {945\,{u}^{6}}{861764}} +{\frac {16191\,{u}^{7}}{430882}} \\ +{\frac {112023\,{u}^{8}}{430882}}+{\frac {416745\,{u}^{9}}{861764}} +{\frac {938223\,{u}^{10}}{4308820}},$$

a result that is not accessible by enumeration, which was nonetheless implemented as a sanity check in the following Maple code, where it was found to match the two closed forms on the values that were examined.

ENUM :=
proc(n, j, m)
option remember;
local src, recurse, gf;

    src := [seq(j, q=1..n)];

    gf := 0;

    recurse :=
    proc(prob, sofar, rest, drawn)
    local remain, choice, chinst;

        if drawn = m then
            gf := gf +
            prob*u^nops(convert(sofar, `multiset`));
            return;
        fi;

        remain := n*j-drawn;

        for choice to n do
            chinst := op(choice, rest);

            if chinst > 0 then
                recurse(prob*chinst/remain,
                        [op(sofar), choice],
                        subsop(choice=chinst-1, rest),
                        drawn+1);
            fi;
        od;
    end;

    recurse(1, [], src, 0);
    gf;
end;

gfA :=
proc(n, j, m)

    if m > n*j then return 0 fi;

    add(binomial(n*j,m)^(-1)*binomial(n,q)*
        add(binomial(q,p)*(-1)^(q-p)*binomial(j*p,m),
            p=0..q)*u^q, q=0..n);
end;

gfB :=
proc(n, j, m)

    if m > n*j then return 0 fi;

    add(binomial(n,q)*
        add(binomial(q,p)*(-1)^(q-p)*
            binomial(n*j, p*j)^(-1)*binomial(n*j-m,p*j-m),
            p=0..q)*u^q, q=0..n);
end;

Answer 2

The following is a solution by use of an extension of the Principle of Inclusion and Exclusion. We will find the probability that the sample contains exactly $n-m$ different types, where we call all balls with the same number a "type". Note that this is a revision of the original problem statement.

There are $\binom{nr}{N}$ possible samples of size $N$, all of which we assume are equally likely. Say a sample has "Property $j$" if it includes no balls of type $j$ for $j=1,2,3,\dots ,n$, and let $S_i$ be the number of samples with $i$ of the properties (with over-counting) for $i=1,2,3,\dots ,n$. If a sample has $m$ of the properties then there are $\binom{n}{m}$ ways to pick the missing ball types and $\binom{(n-m)r}{N}$ possible ways to pick $N$ balls from the remaining types. So $$S_m = \binom{n}{m} \binom{(n-m)r}{N}$$ for $m = 1,2,3,...,n$.

Now define $e_m$ to be the number of samples with exactly $m$ of the properties. By Theorem 2.8 in Schaum's Outline of Theory and Problems of Combinatorics by V.K. Balakrishnan, $$e_m = \sum_{k=0}^{n-m} (-1)^k \binom{m+k}{m} S_{m+k}$$ so $$e_m = \sum_{k=0}^{n-m} (-1)^k \binom{m+k}{m} \binom{n}{m+k} \binom{(n-m-k)r}{N}$$ and the probability that a sample pf size $N$ contains exactly $n-m$ different types of balls is $$\frac{e_m}{\binom{nr}{N}}$$