2
$\begingroup$

Let there be $n$ distinguishable balls and $m$ distinguishable bins, each bin of size $s$, that is, we cannot place more than $s$ balls into it. How many possibilites are there to place the balls into the bins?

$\endgroup$
1
$\begingroup$

This can be done using species and generating functions. If some bins are allowed to remain empty the species is

$$\mathfrak{S}_{=m}(\mathfrak{P}_{\le s}(\mathcal{Z})).$$

This gives the generating function $$P(z) = \left(\sum_{k=0}^s \frac{z^k}{k!}\right)^m$$

and the closed formula $$p_{n,m,s} = n! [z^n] \left(\sum_{k=0}^s \frac{z^k}{k!}\right)^m.$$

If no bins are allowed to remain empty the species is

$$\mathfrak{S}_{=m}(\mathfrak{P}_{1\le\cdot\le s}(\mathcal{Z})).$$

This gives the generating function $$Q(z) = \left(\sum_{k=1}^s \frac{z^k}{k!}\right)^m$$

and the closed formula $$q_{n,m,s} = n! [z^n] \left(\sum_{k=1}^s \frac{z^k}{k!}\right)^m.$$

The following Maple code implements a brute force calculation to verify these values and the generating functions as well.

P := proc(n, m, s) n!*coeftayl(add(z^k/k!, k=0..s)^m, z=0, n); end;
Q := proc(n, m, s) n!*coeftayl(add(z^k/k!, k=1..s)^m, z=0, n); end;

P_ex :=
proc(n, m, s)
    option remember;
    local ind, d, ms, k, res, pos;

    res := 0;

    if m = 1 then
        if n <= s then res := res + 1 fi;
        return res;
    fi;

    for ind from m^(n+1) to m^(n+1)+m^n-1 do
        d := convert(ind, base, m);
        ms := convert([seq(d[k], k=1..n)], multiset);

        for pos to nops(ms) do
            if ms[pos][2] > s then
                break;
            fi;
        od;

        if pos = nops(ms)+1 then
            res := res + 1;
        fi;
    od;

    res;
end;


Q_ex :=
proc(n, m, s)
    option remember;
    local ind, d, ms, k, res, pos;

    res := 0;

    if m = 1 then
        if n <= s then res := res + 1 fi;
        return res;
    fi;

    for ind from m^(n+1) to m^(n+1)+m^n-1 do
        d := convert(ind, base, m);
        ms := convert([seq(d[k], k=1..n)], multiset);

        for pos to nops(ms) do
            if ms[pos][2] > s then
                break;
            fi;
        od;

        if pos = nops(ms)+1 and nops(ms) = m then
            res := res + 1;
        fi;
    od;

    res;
end;

I was not able to find OEIS entries for these.

$\endgroup$
  • $\begingroup$ Thank you. Can you explain, how I might apply the closed formula, i.e. what the parameter z stands for, exactly? I'm sorry if this is a really stupid question. $\endgroup$ – ComibinatorialCrocodile Oct 15 '14 at 21:14
  • $\begingroup$ The above might not be suitable for a first combinatorics course. Maybe someone from the set of experts on MSE will post an elementary derivation. If you want to understand the meaning of the parameter $z$ and the concept of generating functions there is this Wikipedia article on Symbolic / Analytic Combinatorics. $\endgroup$ – Marko Riedel Oct 15 '14 at 21:21
  • $\begingroup$ It would be very helpful if you could post the coefficient that I need to compute this quantity. $\endgroup$ – ComibinatorialCrocodile Oct 15 '14 at 21:34
  • $\begingroup$ The two functions at the top of the Maple code namely P and Q will instantly produce the answer for any $n,m$ and $s$. Consult these to see how to input the formula into a CAS. Any one of the major CAS can do this and MSE is likely to have contributors that use them. $\endgroup$ – Marko Riedel Oct 15 '14 at 22:54

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.