6
$\begingroup$
  1. Assume all balls with the same color are indistinguishable.
  2. The order in which balls are put in a bin does not matter.
  3. No bins are allowed to have the same distribution of balls!

For example, this configuration

{RRGGGB} {RRRRGBBBB} {RGB} {RGB}

is not ok, because the two last bins contains the same distribution of balls: one Red, one Green, one Blue.

Actualy I'm most intressted in the procedure for solving this problem where the number of balls, colors and bins are much larger numbers.

$\endgroup$
  • $\begingroup$ Is this from some programming contest? $\endgroup$ – Aryabhata Jan 10 '15 at 18:43
  • 1
    $\begingroup$ No, not what I know of. But I think the solution to this problem can be used to find all ways a number can be written as a product of k distinct integers, where k is the number of bins and balls corresponds to prime factors. $\endgroup$ – Penlect Jan 10 '15 at 19:04
  • $\begingroup$ What exactly do you mean by indistinguishable bins? $\endgroup$ – Nicholas Pipitone Jan 10 '15 at 19:24
  • $\begingroup$ I just mean that the bins are unlabeled. If two bins switched position, that should not be counted as a "new way". $\endgroup$ – Penlect Jan 10 '15 at 20:18
3
$\begingroup$

This problem is a straightforward application of the Polya Enumeration Theorem. Suppose we treat the case of $r$ red balls, $g$ green balls and $b$ blue balls and $n$ indistinguishable bins where no bins are left empty.

Recall the recurrence by Lovasz for the cycle index $Z(P_n)$ of the set operator $\mathfrak{P}_{=n}$ on $n$ slots, which is $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$

We need to employ the set operator because the elements of a distribution are supposed to be unique.

We have for example, $$Z(P_3) = 1/6\,{a_{{1}}}^{3}-1/2\,a_{{2}}a_{{1}}+1/3\,a_{{3}}$$ and $$Z(P_4) = 1/24\,{a_{{1}}}^{4}-1/4\,a_{{2}}{a_{{1}}}^{2} +1/3\,a_{{3}}a_{{1}}+1/8\,{a_{{2}}}^{2}-1/4\,a_{{4}}.$$

Applying PET and PIE it now follows almost by inspection that the desired count is given by the term $$\sum_{q=1}^n (-1)^{n-q} [R^r G^g B^b] Z(P_q)\left(\frac{1}{1-R}\frac{1}{1-G}\frac{1}{1-B}\right).$$

We need to employ PIE here because the substituted cycle index will include empty slots, which we are not counting in this problem.

As an example of what these substituted cycle indices look like consider $$Z(P_3)\left(\frac{1}{1-R}\frac{1}{1-G}\frac{1}{1-B}\right) \\ = 1/6\,{\frac {1}{ \left( 1-R \right) ^{3} \left( 1-G \right) ^{3} \left( 1-B \right) ^{3}}} \\-1/2\,{\frac {1}{ \left( -{R}^{2}+1 \right) \left( -{G}^{2}+1 \right) \left( -{B}^{2}+1 \right) \left( 1-R \right) \left( 1-G \right) \left( 1-B \right) }} \\+1/3\,{\frac {1}{ \left( -{R}^{3}+1 \right) \left( -{G }^{3}+1 \right) \left( -{B}^{3}+1 \right) }} .$$

It should be clear that coefficient extraction here is fast and efficient using the Newton binomial series which says that $$[Q^{\mu k}] \left(\frac{1}{1-Q^\mu}\right)^\nu = {k+\nu-1\choose \nu-1}.$$

The answer for eight red, six green and seven blue balls in four indistinguishable bins turns out to be $$60040.$$

The following Maple code implements two routines, q1 and q2. The first of these computes the value for $(r,g,b)$ and $n$ by brute force (enumerate all configurations) and can be used to verify the correctness of the PET formula for small values of the parameters. The second one uses the PET for instant computation of the desired coefficient.

Observe that we can compute values that are utterly out of reach of brute force enumeration, e.g. with ten balls of each color and five bins we obtain $$7098688.$$

With twenty balls of each color and six bins we get $$194589338219.$$

with(combinat);


pet_cycleind_set :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*
           add((-1)^(l-1)*a[l]*pet_cycleind_set(n-l), l=1..n));
end;


pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;

allparts :=
proc(val, size)
    option remember;
    local res, els, p, pp, q;

    res := [];

    for p in partition(val) do
        if nops(p) <= size then
            pp := [seq(q, q in p),
                   seq(0, q=1..(size-nops(p)))];
            res := [op(res), pp];
        fi;
    od;

    res;
end;

q1 :=
proc(RC, GC, BC, n)
    option remember;
    local p, q, pr, pg, pb, res,
    sr, sg, sb, dist;

    pr := [];
    for p in allparts(RC, n) do
        pr := [op(pr), seq(q, q in permute(p))];
    od;

    pg := [];
    for p in allparts(GC, n) do
        pg := [op(pg), seq(q, q in permute(p))];
    od;

    pb := [];
    for p in allparts(BC, n) do
        pb := [op(pb), seq(q, q in permute(p))];
    od;

    res := {};

    for sr in pr do
        for sg in pg do
            for sb in pb do
                dist :=
                {seq(R^sr[pos]*G^sg[pos]*B^sb[pos],
                     pos=1..n)};

                if nops(dist) = n and
                not member(1, dist) then
                    res := res union {dist};
                fi;
            od;
        od;
    od;

    nops(res);
end;

q2 :=
proc(RC, GC, BC, n)
    option remember;
    local els, vals, sind;

    vals := [];

    for els to n do
        sind :=
        pet_varinto_cind(1/(1-R)/(1-G)/(1-B),
                         pet_cycleind_set(els));

        vals :=
        [op(vals),
         coeftayl(
             coeftayl(
                 coeftayl(sind, R=0, RC),
                 G=0, GC),
             B=0, BC)];
    od;

    add(vals[els]*(-1)^(n-els), els=1..n);
end;
$\endgroup$
  • $\begingroup$ Thank you Marko for the great and detailed answer. I have not studied the Polya Enumeration Theorem, so I have some noobish follow-up questions :). I'm a bit uncertain about the square-bracket notation here: [R^rG^gB^b], and what are the difference between captial R and and lower case r? Also, what are the definition/values of the a_n coefficients? Finally, I don't fully understand the Newton binomial series expression, what does the square-bracket notation and Mu mean here? Thanks again. $\endgroup$ – Penlect Jan 11 '15 at 10:27
  • $\begingroup$ Thanks. I don't have the time for a detailed reply at the moment but I suggest you study the Maple code, which should make it clear what the variables mean. Not only does it compute values it is also a commentary on the text. There are many more PET examples including introductory ones at MSE Meta. $\endgroup$ – Marko Riedel Jan 11 '15 at 11:14
  • $\begingroup$ What's the complexity of this algorithm? $\endgroup$ – Elliot Gorokhovsky Oct 30 '15 at 17:42

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.