Distributing colored balls into bins such that each bin is distinct.

Question

Suppose I have $n = n_1 + n_2 + \dots + n_k$ balls of $k$ colors, with exactly $n_i \geq 1$ balls of color $i$. Balls that are the same color are indistinguishable. Additionally, we have $m$ indistinguishable bins. I would like to count the number of ways in which we can distribute the balls over all bins such that each bin is non-empty, and no two bins have the exact same multiset of balls (i.e. we can not have two bins $\{R, B\}$, but we can have both of the bins $\{R, B\}$ and $\{R, R, B\}$).

Example: say we have $m=2$ and $n_1 = 3$ ('red') and $n_2 = 2$ ('blue'). Then the valid distributions are:

• $\{\{R, R, R, B\}, \{B\}\}$
• $\{\{R, R, R\}, \{B, B\}\}$
• $\{\{R, R, B, B\}, \{R\}\}$
• $\{\{R, R, B\}, \{R, B\}\}$
• $\{\{R, R\}, \{R, B, B\}\}$

So the answer is $5$ (modulo an overseen distribution on my part :-) ).

How can I compute this quantity for given $n_1,n_2, \dots, n_k$ and $m$?

Answer 1

Note: what follows is a close adaptation of this MSE link, which treats unique factorizations of integers into multisets of factors. In the present problem the factors have to be unique. Suppose we start with the source multiset and using the notation from the cited link

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \prod_{k=1}^l A_k^{\tau_k}$$

where we have $l$ different values and their multiplicities are the $\tau_k.$

If we have a CAS like Maple, $N$ is reasonable and we seek fairly instant computation of these values then we may just use the cycle index $Z(P_N)$ of the unlabeled operator $\textsc{SET}_{=N}.$ This yields the formula

$$\left[\prod_{k=1}^l A_k^{\tau_k}\right] Z\left(P_N; -1 + \prod_{k=1}^l \frac{1}{1-A_k}\right).$$

Here we have used the recurrence by Lovasz for the quoted cycle index, 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.$$

Maple can extract these coefficients by asking for the coefficient of the corresponding Taylor series. We get the following transcript:

> MSETS([3,2], 2);                                          
                             5

> map(el->el[1], select(el->el[\                            
> 2]>0, [seq([n, FACTORS(n,3)], n=1..256)]));           
[24, 30, 36, 40, 42, 48, 54, 56, 60, 64, 66, 70, 72, 78, 80,

    84, 88, 90, 96, 100, 102, 104, 105, 108, 110, 112, 114,

    120, 126, 128, 130, 132, 135, 136, 138, 140, 144, 150,

    152, 154, 156, 160, 162, 165, 168, 170, 174, 176, 180,

    182, 184, 186, 189, 190, 192, 195, 196, 198, 200, 204,

    208, 210, 216, 220, 222, 224, 225, 228, 230, 231, 232,

    234, 238, 240, 246, 248, 250, 252, 255, 256]

The sequence is OEIS A122181 and looks to have the right values. The Maple code here is quite simple and also includes a recurrence that does not use PET, which is based on MSE Link II.

with(combinat);
with(numtheory);

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, subsl, polyvars, indvars, v, pot;

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

    subsl := [];

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

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

        subsl := [op(subsl), v=subs(subs1, poly)];
    od;

    subs(subsl, ind);
end;


MSETS :=
proc(src, N)
local msetgf, cind, gf, cf;

    msetgf := mul(1/(1-A[q]), q=1..nops(src))-1;
    cind := pet_cycleind_set(N);

    gf := pet_varinto_cind(msetgf, cind);

    for cf to nops(src) do
        gf := coeftayl(gf, A[cf] = 0, src[cf]);
    od;

    gf;
end;

FACTORS :=
proc(n, N)
local mults;

    mults := map(el -> el[2], op(2, ifactors(n)));
    MSETS(mults, N);
end;

FACTREC :=
proc(val, numel, maxfact)
option remember;
local divs;

    if numel = 1 then
        return `if`(1 < val and val <= maxfact, 1, 0);
    fi;

    divs := select(d -> d <= maxfact, divisors(val));
    add(FACTREC(val/d, numel-1, d-1), d in divs);
end;

FACTORSX := (n, N) -> FACTREC(n, N, n);