Circular Permutations of a Multiset

Question

How many circular permutations are there of the multiset $$S=\{2*a,3*b,4*c,5*d\}$$ where for each type of letter, all letters of that type do not appear consecutively.

Answer 1

The key observation here is the following. The problem becomes interesting when there are duplicate counts in the multiset or when the GCD of the counts is more than one.

Remark. The task that we are treating here represents the case where the forbidden configurations are those that contain a block where all letters of one type appear consecutively, e.g. in the example from the OP this would be a block of two $a$s, three $b$s, four $c$s or five $d$s.

Applying the Polya Enumeration Theorem (PET) we have the cycle index of the cyclic group

$$Z(C_n) = \frac{1}{n}\sum_{d|n} \varphi(d) a_d^{n/d}.$$

Let the multiset be represented by the polynomial

$$A_1^{q_1} A_2^{q_2} \times\cdots\times A_p^{q_p}.$$

where $p$ is the number of different types of elements and the $q$ represent multiplicities. Introduce $A=\{1,2,\ldots p\}$ and define for $B\subseteq A$

$$s(B) = |B|+\sum_{k\in A\setminus B} q_k.$$

Furthermore we introduce

$$t(B) = \prod_{k\in B} A_k \prod_{k\in A\setminus B} A_k^{q_k}.$$

The sets $B$ represent fused blocks where the types contained in $B$ appear consecutively. We then have by inclusion-exclusion the closed form

$$\sum_{B\subseteq A} (-1)^{|B|} \left[t(B)\right] Z(C_{s(B)}) \left(\sum_{k\in A} A_k\right).$$

where $\left[t(B)\right]$ denotes coefficient extraction.

Applying this to $A_1^2 A_2^3 A_3^4 A_4^5$ yields the answer

$$\bbox[5px,border:2px solid #00A000]{144029}.$$

The Maple code for this was as follows. (We have included a total enumeration routine which is practicable only for small element counts but does nonetheless confirm the results from PET in those cases that were checked.)

with(numtheory);
with(combinat);

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_cyclic :=
proc(n)
local d, s;

    s := 0;
    for d in divisors(n) do
        s := s + phi(d)*a[d]^(n/d);
    od;

    s/n;
end;

mset_incl_excl :=
proc(mset)
option remember;
local res, pset, types, dist,
    pos, gf, src, cind, slots;

    types := nops(mset);

    res := 0;

    for pset in powerset([seq(q, q=1..types)]) do
        dist :=
        [seq(`if`(member(q, pset), 1, mset[q]),
             q=1..types)];
        slots := add(q, q in dist);

        src := add(A[q], q=1..types);
        cind := pet_cycleind_cyclic(slots);

        gf := pet_varinto_cind(src, cind);
        gf := expand(gf);

        for pos to types do
            gf := coeff(gf, A[pos], dist[pos]);
        od;

        res := res + gf*(-1)^nops(pset);
    od;

    res;
end;

mset_enum :=
proc(mset)
local perm, cperm, orbits, orbit, rot, pos,
    src, kind, types, slots, runl;

    types := nops(mset);

    src := [seq(seq(q, p=1..mset[q]), q=1..types)];
    slots := add(q, q in mset);

    orbits := table();

    for perm in permute(src) do
        orbit := {};

        for pos to slots do
            rot :=
            [seq(perm[q], q=pos..slots),
             seq(perm[q], q=1..pos-1)];

            orbit := orbit union {rot};
        od;

        cperm := [op(perm), op(perm)];

        for kind to types do
            runl := 0;

            for pos to nops(cperm) do
                if cperm[pos] = kind then
                    runl := runl + 1;
                else
                    runl := 0;
                fi;

                if runl = mset[kind] then
                    break;
                fi;
            od;

            if pos <= nops(cperm) then
                break;
            fi;
        od;

        if kind = types + 1 then
            orbits[orbit] := 1;
        fi;
    od;

    nops([indices(orbits)]);
end;

Addendum Nov 2 2016. The above formula admits radical simplification. We effectively remove all symmetries as soon as we fuse a block of similar elements. Therefore we only need the cycle index in the first step when we compute the set of all circular configurations. We may simply divide by the number of elements thereafter. This gives the formula

$$[t(\emptyset)] Z(C_{s(\emptyset)})\left(\sum_{k\in A} A_k\right) + \sum_{B\neq\emptyset, B\subseteq A} (-1)^{|B|} \frac{(s(B)-1)!}{\prod_{k\in A\setminus B} q_k!}.$$

The Maple code now becomes

mset_incl_excl2 :=
proc(mset)
option remember;
local res, pset, types, dist,
    pos, gf, src, cind, slots;

    types := nops(mset);

    slots := add(q, q in mset);

    src := add(A[q], q=1..types);
    cind := pet_cycleind_cyclic(slots);

    gf := pet_varinto_cind(src, cind);
    gf := expand(gf);

    for pos to types do
        gf := coeff(gf, A[pos], mset[pos]);
    od;

    res := gf;

    for pset in powerset({seq(q, q=1..types)})
    minus {{}} do
        dist :=
        [seq(`if`(member(q, pset), 1, mset[q]),
             q=1..types)];
        slots := add(q, q in dist);

        res := res +
        (-1)^nops(pset)*(slots-1)!
        / mul(q!, q in dist);
    od;

    res;
end;