Circular Permutations of a Multiset 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.
 A: 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;

