Jtdylktuy

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$?

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

$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{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]
Zleft(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})
quadtext{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);