Counting Circular Sequence (Burnside Lemma?)

Question

1. How many distinct circular binary sequences of length $n$ are there?
2. How many distinct circular binary sequences of length $n$ containing a given pattern, e.g., $110$ are there?
3. The same questions as in Question 1. and 2. for circular sequence of elements from $\{1,2,...,k\}$.

Do we need the Burnside orbit counting lemma?

Answer 1

We now treat the case of an alphabet of $k$ letters rather than a binary alphabet. We use two classes of letters, the pattern being represented by $WWY_0$ and an additional sequence of letters from $Y_1$ to $Y_{k-2}.$ In this way we obtain $k$ letters total.

Now there are several cases, the easiest is if $W$ does not ocur at all. These are given by

$$Q_{n, k-1} = Z(C_n)(Y_0+Y_1+\cdots+Y_{k-2})_{Y_0=Y_1=\cdot=Y_{k-2}=1}.$$

This quantity can also be computed by Burnside, I chose Polya because the code for it was already written.

The second case is a necklace consisting of instances of $W$ only, of which there is exactly one.

The third case is a necklace of blocks starting with an initial run of ones of some length followed by other letters. The key observation here is that any rotational symmetry must map the runs of ones to themselves, so the symmetry of blocks corresponds exactly to the symmetry of single letters. That means we may consider necklaces of blocks instead of necklaces of letters.

We must now construct the inventory of blocks for use with Redfield-Polya Enumeration Theorem. A block starts with a run of ones but a run of a single one is special, in that it may be followed by any letter whereas a run of at least two ones may not be followed by $Y_0.$ We make a design choice here, marking all letters with a $Z$ so that the desired count is coefficient on $[Z^n].$ We will show later how the variables other than $Z$ can be optimized out. We thus get for the inventory of blocks

$$WZ\sum_{q=1}^n (ZY_0+\cdots+ZY_{k-2})^q \\ + \sum_{p=2}^n W^pZ^p (ZY_1+\cdots+ZY_{k-2}) \sum_{q=0}^n (ZY_0+\cdots+ZY_{k-2})^q.$$

We may form necklaces of one block, two and so on to $\lfloor n/2\rfloor$ of these blocks. We therefore get the formula

$$1 + Q_{n,k-1} + \sum_{s=1}^{\lfloor n/2\rfloor} [Z^n] Z(C_s) \left(WZ\sum_{q=1}^n \left(\sum_{r=0}^{k-2} ZY_r\right)^q \\ + \sum_{p=2}^n W^p Z^p \sum_{r=1}^{k-2} ZY_r \sum_{q=0}^n \left(\sum_{r=0}^{k-2} ZY_r\right)^q \right)_{W=Y_0=\cdots=Y_{k-2}=1}.$$

Observe that the $Z(C_s)$ refers to the cycle index and not to the variable $Z$, which counts the total letters in the necklace. We now optimize this formula as promised and improve readablity and efficiency. Making the substitutions we get

$$1 + Q_{n,k-1} \\ +\sum_{s=1}^{\lfloor n/2\rfloor} [z^n] Z(C_s) \left(z\sum_{q=1}^n (k-1)^q z^q + \sum_{p=2}^n z^p (k-2) z \sum_{q=0}^n (k-1)^q z^q\right).$$

Clearly additional simplification is possible here as the sums have a closed form but the resulting expression does not necessarily provide a gain in insight or compactness.

With this formula in place we can start to compute counts. The binary case is the same as in the companion post.

For three letters we get

$$3, 6, 10, 21, 42, 103, 237, 603, 1519, 3942, 10257, 27131, 71940, \\ 192462, 516933, 1395636, 3781356, 10283911, 28050600, 76732047, \\ 210414811, 578330649,\ldots$$

for four letters

$$4, 10, 23, 66, 192, 636, 2092, 7228, 25175, 89212, 318808, 1150444, \\ 4177908, 15268494, 56078527, 206903020, 766342160, 2848351388, \\ 10619472284, 39702648534,\ldots$$

and for five letters

$$5, 15, 44, 160, 604, 2510, 10545, 45825, 201669, 900307, 4057625, \\ 18447565, 84444000, 388878560, 1799985435, 8368841895, 39062428790, \\ 182961584260,\ldots$$

The Maple code for this was as follows.

with(numtheory);

Y :=
proc(n, k)
option remember;
local d, dd, ind, orbit, orbits, pos, shft;

    if k = 1 then return 1 fi;

    orbits := {};

    for ind from k^n to 2*k^n-1 do
        d := convert(ind, base, k);

        dd := [seq(d[q], q=1..n), d[1], d[2]];

        for pos to n do
            if dd[pos] = 1 and
            dd[pos+1] = 1 and dd[pos+2] = 0 then
                break;
            fi;
        od;

        if pos = n+1 then
            orbit := {};

            for shft to n do
                orbit :=
                {op(orbit),
                 [seq(d[p], p=shft .. n),
                  seq(d[p], p=1..shft-1)]};
            od;

            orbits := {op(orbits), orbit};
        fi;
    od;

    nops(orbits);
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_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;

pet_cycleind_cyclic_num :=
proc(n, k)
local d, s;

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

    s/n;
end;


R :=
proc(n, k)
option remember;
local res, seg, inv, ovars, ofree, rest, gf;

    if k = 1 then return 1 fi;

    ovars := add(Z*Y[q], q=0..k-2);
    ofree := add(Y[q], q=0..k-2);

    inv := add(W*Z*ovars^q, q=1..n)
    + add(add(W^p*Z^p*(ovars-Z*Y[0])*ovars^q, q=0..n),
          p=2..n);

    res := 0;

    for seg to floor(n/2) do
        gf := expand(pet_varinto_cind
                     (inv, pet_cycleind_cyclic(seg)));
        res := res + coeff(gf, Z, n);
    od;

    rest := pet_varinto_cind(ofree, pet_cycleind_cyclic(n));

    1 + subs({W=1, seq(Y[q]=1, q=0..k-2)}, res + rest);
end;

R2 :=
proc(n, k)
option remember;
local seg, gf, res;

    if k = 1 then return 1 fi;

    res := 0;

    gf := z*add((k-1)^q*z^q, q=1..n)
    + add(z^p*(k-2)*z*add((k-1)^q*z^q, q=0..n), p=2..n);

    for seg to floor(n/2) do
        res := res +
        coeff(expand(pet_varinto_cind
                     (gf, pet_cycleind_cyclic(seg))),
              z, n);
    od;


    1 + pet_cycleind_cyclic_num(n, k-1) + res;
end;

Just to be on the safe side here is another total enumeration routine, this one written in Perl. It matches the values from the formula that are listed above. (Practical to about $n=10.$)

#! /usr/bin/perl -w
#

MAIN : {
    my $mx = shift || 10;
    my $k = shift || 2;

    my @res = ($k);

    for(my $n=2; $n <= $mx; $n++){
        my %orbits;

        for(my $ind = 0; $ind < $k ** $n; $ind++){
            my ($pos, $idx, @d);

            for(($pos, $idx) = (0, $ind); 
                $pos < $n; $pos++){
                my $digit = $idx % $k;

                push @d, $digit;
                $idx = ($idx-$digit) / $k;
            }

            push @d, $d[0], $d[1];

            for($pos=0; $pos < $n; $pos++){
                last if $d[$pos] == 1 && $d[$pos+1] == 1
                    && $d[$pos+2] == 0;
            }

            pop @d; pop @d;

            if($pos == $n){
                my %orbit;
                for(my $shft = 0; $shft < $n; $shft++){
                    my $str =
                        join('-', 
                             @d[$shft..$n-1], @d[0..$shft-1]);
                    $orbit{$str} = 1;
                }

                my $orbstr = join('|', sort(keys %orbit));
                $orbits{$orbstr} = 1;
            }
        }

        push @res, scalar(keys %orbits);
    }

    print join(', ', @res);
    print "\n";

    1;
}

Answer 2

In the present case (binary necklace, forbidden pattern $110$) we have a simple observation (which does not generalize). This is if we divide the necklace into adjacent segments consisting of repetitions of one and the same symbol we cannot have a run of two or more ones since these would form the pattern $110$ with the zero following the run of ones. Therefore we are distributing singleton ones on the necklace separated by runs of zeros. The minimum here is a single one and the maximum is $\lfloor n/2\rfloor.$ (As the separating run of zeros contains at least one zero this is the highest we can get.) With this observations we have reduced the problem to an ordinary necklace problem as we now have a necklace of runs of zeros in the slots of the necklace. We thus get the formula (using the cycle index $Z(C_q)$ of of the cyclic group)

$$2+\sum_{q=1}^{\lfloor n/2\rfloor} [x^{n-q}] Z(C_q)(x+x^2+\cdots+x^n).$$

Here $q$ counts the number of singleton ones, producing the sequence

$$2, 3, 3, 4, 4, 6, 6, 9, 11, 16, 20, 32, 42, 65, 95, 144, 212, \\ 330, 494, 767, 1171, 1812, 2788, 4342, 6714, 10463, 16275, \\ 25416, 39652, 62076, 97110, 152289,\ldots$$

The two in front represents necklaces consisting of zeros only and ones only which do not contain the pattern either.

The Maple code to compute and verify these was as follows.

with(numtheory);

Y :=
proc(n)
option remember;
local d, dd, ind, orbit, orbits, pos, shft;

    orbits := {};

    for ind from 2^n to 2*2^n-1 do
        d := convert(ind, base, 2);
        # print([seq(d[p], p=1..n)]);

        dd := [seq(d[q], q=1..n), d[1], d[2]];

        for pos to n do
            if dd[pos] = 1 and
            dd[pos+1] = 1 and dd[pos+2] = 0 then
                break;
            fi;
        od;

        if pos = n+1 then
            orbit := {};

            for shft to n do
                orbit :=
                {op(orbit),
                 [seq(d[p], p=shft .. n),
                  seq(d[p], p=1..shft-1)]};
            od;

            orbits := {op(orbits), orbit};
        fi;
    od;

    nops(orbits);
end;

XY :=
proc(n)
    local d;

    1/n*add(phi(d)*2^(n/d), d in divisors(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_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;

R :=
proc(n)
local res, seg, vars, gf;

    vars := add(X^q, q=1..n);

    res := 0;

    for seg to floor(n/2) do
        gf := expand(pet_varinto_cind
                     (vars, pet_cycleind_cyclic(seg)));
        res := res + coeff(gf, X, n-seg);
    od;

    res+2;
end;