1
$\begingroup$

I have seen explanations for distribution among '$r$' groups as opposed to '$r$' identical groups(example: if $12$ eggs are to be distributed among $4$ baskets such that the baskets are not numbered). I know that it cannot be done by finding the number of possible whole number solutions for these $4$ baskets$[(12+4-1)C(4-1)]$, which gives the answer when the baskets are numbered, and then dividing by 4! to "adjust" for the "identical" baskets(as there would also be distributions such as $2,2,3,5; 2,3,2,5; 2,2,2,6$). All this leads me to wonder if there is a single working formula(without the need of step-by-step calculation) for the same.

$\endgroup$
0
$\begingroup$

Using the Polya Enumeration Theorem the closed form is given by

$$[z^n] Z(S_r)\left(\frac{1}{1-z}\right)$$

where $Z(S_r)$ is the cycle index of the symmetric group. This cycle index is known in species theory as the multiset operator $\mathfrak{M}_{=r}.$

Recall the recurrence by Lovasz for the cycle index $Z(S_r)$ of the set operator $\mathfrak{M}_{=r}$ on $r$ slots, which is

$$Z(S_r) = \frac{1}{r} \sum_{l=1}^r a_l Z(S_{r-l}) \quad\text{where}\quad Z(S_0) = 1.$$ This recurrence lets us calculate the cycle index $Z(S_r)$ very easily.

For example when $r=5$ the cycle index is $$Z(S_5) = {\frac {{a_{{1}}}^{5}}{120}}+1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{3}} {a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2} \\+1/4\,a_{{4}}a_{{1}}+1/6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}$$

and the generating function becomes

$${\frac {1}{120\, \left( 1-z \right) ^{5}}} +1/12\,{\frac {1}{ \left(-{z}^{2}+1 \right) \left( 1-z \right) ^{3}}} +1/6\,{\frac {1}{ \left( -{z}^{3}+1 \right) \left( 1-z \right) ^{2}}} \\+1/8\,{\frac {1}{ \left( 1-z \right) \left( -{z}^{2}+1 \right) ^{2}}} +1/4\,{\frac {1}{ \left( -{z}^{4}+1 \right) \left( 1-z \right) }} +1/6\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( -{z}^{3}+1 \right) }} \\+1/5\, \left( -{z}^{5}+1 \right) ^{-1}.$$

which gives the sequence

$$1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 84, 101, \\ 119, 141, 164, 192, \ldots$$

that points to OEIS A001401 which looks to be a match. Here we have assumed that empty bins are admissible.

This MSE link shows how one might go about producing a closed form expression for the coefficients of this type of generating function. Furthermore this MSE link II presents an algorithm for computing these closed forms.

There is some Maple code to help explore these data.

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;

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
$\endgroup$

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.