Number of cycle partition of a set with repeating elements

bell-numberscombinatoricspermutationspolynomialsset-partition

We have a set $S$ with $E$ elements of which only $N$ are unique. We of course know how many repetitions of each of the $N$ elements are present: element $s_i$ is repeating $t_i$ times.

I would like to count the number of ways we can divide the $E$ elements in $N$ blocks of size $k_1, k_2, \cdots , k_N$ when the elements within the block are indistinguishable.

If the $E$ elements are all unique, we can answer directly using the Bell Polynomials.

Do you think is it possible to extend the above result ?

Best Answer

It appears that we have a simplified version of the computation from the following MSE link. Using the notation that was presented there we obtain the closed form

$$\left[\prod_{k=1}^l A_k^{\tau_{k}}\right] \prod_{k=1}^m Z\left(S_k; \sum_{k'=1}^l A_{k'}\right)^{\sigma_k}.$$

In terms of combinatorial classes we have made use of the unlabeled class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=\sigma_k} \left(\textsc{MSET}_{=k} \left(\sum_{k'=1}^l \mathcal{A}_{k'}\right)\right).$$

Note that the cycle index will create the intermediate multisets during evaluation.

Related Solutions

Permutations with repeating symbols and binomial coefficient

Well, the number of ways you can arrange $a,a,a,b,b$ amounts to the number of ways to choose the locations for the three $a$s, since the $b$s will just go in the other two spots. But choosing locations for the $a$s is simply choosing a $3$-element subset of the set of all $5$ locations, of which there are $C[5,3],$ as you noticed.

Let's number our spots--$\{1,2,3,4,5\}.$ Then if we went with the arrangement $aabab,$ this would correspond to the subset $\{1,2,4\},$ for example. On the other hand, the subset $\{2,3,5\}$ would correspond to the arrangement $baaba.$

As you already observed, this only works with two types of objects to permute, since the locations of the first type of object tell the whole story. Otherwise, we can analogously use multinomial coefficients. (Note that the article uses "permutations with repetition" differently than you do.)

Combinatorics – Partitioning a Multiset into Multisets of Fixed Sizes

It would appear that these are multisets of multisets which may be enumerated using the Polya Enumeration Theorem (PET). Let the multiset that is being drawn have factorization

$$\prod_{k=1}^m B_k^{\sigma_{k}}$$

where $k$ is the value of a term and $\sigma_k$ the number of times it ocurs and recall that we have $l$ types of items forming the source multiset

$$\prod_{k=1}^l A_k^{\tau_{k}}.$$

The answer is then given by

$$\left[\prod_{k=1}^l A_k^{\tau_{k}}\right] \prod_{k=1}^m Z\left(S_{\sigma_k}; Z\left(S_k; \sum_{k'=1}^l A_{k'}\right)\right).$$

In terms of combinatorial classes we have made use of the unlabeled class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{MSET}_{=\sigma_k} \left(\textsc{MSET}_{=k} \left(\sum_{k'=1}^l \mathcal{A}_{k'}\right)\right).$$

As an example for ${2,2\choose 1,1,2} = 3$ we get

$$\textsc{MSET}_{=2} (\textsc{MSET}_{=1}(\mathcal{A_1}+\mathcal{A}_2)) \times \textsc{MSET}_{=1} (\textsc{MSET}_{=2}(\mathcal{A_1}+\mathcal{A}_2)).$$

As an additional example we find for ${2,2,4\choose 1,1,3,3} = 16$

$$\textsc{MSET}_{=2} (\textsc{MSET}_{=1}(\mathcal{A_1}+\mathcal{A}_2+\mathcal{A}_3)) \times \textsc{MSET}_{=2} (\textsc{MSET}_{=3}(\mathcal{A_1}+\mathcal{A}_2+\mathcal{A}_3)).$$

Here we have used the cycle index of the symmetric group $Z(S_n)$, which is computed from the recurrence by Lovasz which says that

$$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}) \quad\text{where}\quad Z(S_0) = 1.$$

For this to be effective we need to compute the iterated cycle index when $Z(S_k)$ is substituted into $Z(S_{\sigma_k}).$ This is accomplished with the substitution rule for substitution of the former into the latter:

$$a_q = Z(S_k;\; a_1=a_q, \; a_2=a_{2q}, \; a_3=a_{3q}, \; \ldots).$$

We have used the notation $Z(S_k; F)$ for substitution of a generating function and on the previous line, the notation for substitution into the variables of the cycle index. This is in fact all we need and we can start computing some of these multiset coefficients. For example we find for the example given by OP the cycle index

$$Z(B_1^2 B_2) = 1/4\,{a_{{1}}}^{4}+1/2\,{a_{{1}}}^{2}a_{{2}}+1/4\,{a_{{2}}}^{2}.$$

Continuing with the example we get

$$Z(B_1^2 B_2; A_1+A_2) = 1/4\, \left( A_{{1}}+A_{{2}} \right) ^{4} +1/2\, \left( A_{{1}}+A_{{2}} \right) ^{2} \left( {A_{{1}}}^{2}+{A_{{2}}}^{2} \right) \\ +1/4\, \left( {A_{{1}}}^{2}+{A_{{2}}}^{2} \right) ^{2} \\ = {A_{{1}}}^{4}+2\,{A_{{1}}}^{3}A_{{2}} +3\,{A_{{1}}}^{2}{A_{{2}}}^{2}+2\,A_{{1}}{A_{{2}} }^{3}+{A_{{2}}}^{4}$$

and we confirm the value $3$ obtained by OP. This algorithm will make it possible to compute cycle indices not obtainable by enumeration. As an extra example we find the following excerpt from the cycle index for $[2,2,2,3,5,5]:$

$$Z(B_2^3 B_3 B_5^2) = \ldots +{\frac {11\,{a_{{1}}}^{8}a_{{2}}a_{{4}}a_{{5}}}{7200}} +{\frac {49\,{a_{{1}}}^{7}{a_{{2}}}^{2}a_{{3}}a_{{5}}}{14400}} \\ +{\frac {5\,{a_{{1}}}^{7} a_{{2}}{a_{{3}}}^{2}a_{{4}}}{1152}} +{\frac {1021\,{a_{{1}}}^{6}{a_{{2}}}^{3}a_{{3}}a_{{4}}}{69120}} +{\frac {43\,{a_{{1}}}^{7}a_{{2}}a_{{4}}a_{{6}}}{17280}}+\ldots$$

Here are some additional values that may assist the reader who is investigating this problem to verify the results of their approach:

$${1,3,3\choose 3,4} = 7, \; {2,3,3\choose 4,4} = 5, \; {2,3,3\choose 2,2,4} = 16 \quad\text{and}\quad {1,2,3,3\choose 2,3,4} = 87.$$

The Maple code for this problem was as follows.

with(combinat);


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;

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_comp :=
proc(idxtrg, idx)
local varstrg, vars, vt, sbstrg, sbs, len;

    varstrg := indets(idxtrg);
    vars := indets(idx);

    sbstrg := [];

    for vt in varstrg do
        len := op(1, vt);

        sbs :=
        [seq(v = a[op(1, v)*len], v in vars)];

        sbstrg :=
        [op(sbstrg),
         a[len] = subs(sbs, idx)];
    od;

    expand(subs(sbstrg, idxtrg));
end;

pet_cycleind_mset :=
proc(msetlst)
option remember;
local mset, res, ent, idxtrg, idx;

    mset := convert(msetlst, `multiset`);

    res := 1;

    for ent in mset do
        idx := pet_cycleind_symm(ent[1]);
        idxtrg := pet_cycleind_symm(ent[2]);

        res := res *
        pet_cycleind_comp(idxtrg, idx);
    od;

    expand(res);
end;


GENF :=
proc(src, msetlst)
local vars, srcp, res, gf, term;

    vars := add(A[q], q=1..nops(src));
    srcp := mul(A[q]^src[q], q=1..nops(src));

    gf := expand(pet_varinto_cind
                 (vars, pet_cycleind_mset(msetlst)));

    if not type(gf, `+`) then
        gf := [gf];
    fi;

    res := 0;

    for term in gf do
        if type(srcp/term, `polynom`) then
            res := res + term;
        fi;
    od;

    res;
end;

The syntax to compute ${\mathrm{A}\choose \mathrm{B}}$ is documented by the following examples:

> GENF([1,2,3,3], [2,3,4]);

                        2     3     3
            87 A[1] A[2]  A[3]  A[4]

> GENF([1,2,3,3], [2,2,5]);

                        2     3     3
            33 A[1] A[2]  A[3]  A[4]

> GENF([1,1,1,1], [2,2]);  

             3 A[1] A[2] A[3] A[4].

The last one is $\frac{1}{2} {4\choose 2}.$

Addendum. There is a slight improvement on this algorithm at the following MSE link.

Best Answer

Related Solutions

Permutations with repeating symbols and binomial coefficient

Combinatorics – Partitioning a Multiset into Multisets of Fixed Sizes

Related Question