2
$\begingroup$
  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?

$\endgroup$
  • 1
    $\begingroup$ These are called necklaces, and yes, they can be counted using the Burnside lemma. Question $2$ seems difficult. $\endgroup$ – joriki Jun 6 '16 at 7:44
  • $\begingroup$ @joriki: Thank you for providing the solution and confirming my hunch. Please let me know if you have any leads to Question 2. $\endgroup$ – Hans Jun 6 '16 at 18:09
  • 1
    $\begingroup$ For Question 2, you could look into inclusion-exclusion, but the interaction between the pattern constraints and the periodicity condition seems daunting. $\endgroup$ – joriki Jun 6 '16 at 19:46
  • $\begingroup$ @joriki I upvoted your observation, which I certainly agree with. Moreover when you compute the necklaces containing the pattern 110 you get a sequence that does not have an OEIS entry. Given the simplicity of the problem statement that fact suggests it being a challenging problem. Burnside has no notion of adjacency. $\endgroup$ – Marko Riedel Jun 6 '16 at 22:19
  • $\begingroup$ Apparently the sequence is $$0, 0, 1, 2, 4, 8, 14, 27, 49, 92, 168, 320, 590, 1117,\ldots$$ and the complementary sequence is $$2, 3, 3, 4, 4, 6, 6, 9, 11, 16, 20, 32, 42, 65,\ldots$$ and these add to $$2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182,\ldots$$ which is OEIS A000031. $\endgroup$ – Marko Riedel Jun 6 '16 at 22:36
2
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ Nice approach! (+1) for both $\endgroup$ – Markus Scheuer Jun 7 '16 at 6:51
  • $\begingroup$ Thank you very much! Do you use a programming language when you work on MSE? $\endgroup$ – Marko Riedel Jun 7 '16 at 17:31
  • $\begingroup$ You're welcome! Sometimes I write some R or perl snippets. Most of them for simple verifying tasks. $\endgroup$ – Markus Scheuer Jun 7 '16 at 17:49
  • $\begingroup$ Awesome! +1 Thank you, Marko Riedel. I need some time to study your wonderful answer. Also what does PET stand for? $\endgroup$ – Hans Jun 7 '16 at 18:58
  • $\begingroup$ PET = Polya Enumeration Theorem, this is the version for generating functions of Burnside's lemma. $\endgroup$ – Marko Riedel Jun 7 '16 at 19:47
2
$\begingroup$

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;
$\endgroup$
  • $\begingroup$ Nice. Thank you. It will be great if you would look into a solution for general patterns. $\endgroup$ – Hans Jun 7 '16 at 0:31
  • $\begingroup$ I believe I have solved this case as well. I need to run a few more checks and then I'll post. $\endgroup$ – Marko Riedel Jun 7 '16 at 0:34
  • $\begingroup$ Excellent! Does that include question 3? $\endgroup$ – Hans Jun 7 '16 at 0:37
  • $\begingroup$ Yes it does. Be patient. $\endgroup$ – Marko Riedel Jun 7 '16 at 0:39

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.