Counting Circular Sequence (Burnside Lemma?) 
*

*How many distinct circular binary sequences of length $n$ are there?

*How many distinct circular binary sequences of length $n$ containing a given pattern, e.g., $110$ are there?

*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?
 A: 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;

