A218034 -id:A218034 - cp's OEIS frontend

A054878 Number of closed walks of length n along the edges of a tetrahedron based at a vertex.

1, 0, 3, 6, 21, 60, 183, 546, 1641, 4920, 14763, 44286, 132861, 398580, 1195743, 3587226, 10761681, 32285040, 96855123, 290565366, 871696101, 2615088300, 7845264903, 23535794706, 70607384121, 211822152360, 635466457083

Offset: 0

Paolo Dominici (pl.dm(AT)libero.it), May 23 2000

Number of closed walks of length n at a vertex of C_4, the cyclic graph on 4 nodes. 3*A015518(n) + a(n) = 3^n. - Paul Barry, Feb 03 2004
Form the digraph with matrix A = [0,1,1,1; 1,0,1,1; 1,1,0,1; 1,0,1,1]; a(n) corresponds to the (1,1) term of A^n. - Paul Barry, Oct 02 2004
Absolute values of A084567 (compare generating functions).
For n > 1, 4*a(n)=A218034(n)= the trace of the n-th power of the adjacency matrix for a complete 4-graph, a 4 X 4 matrix with a null diagonal and all ones for off-diagonal elements. The diagonal elements for the n-th power are a(n) and the off-diagonal are a(n)+1 for an odd power and a(n)-1 for an even (cf. A001045). - Tom Copeland, Nov 06 2012

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
R. J. Mathar, Counting Walks on Finite Graphs, (Nov 2020), Section 2.
Index entries for linear recurrences with constant coefficients, signature (2,3).

Row n=4 of A109502. A084567 (signed version).
{a(n)/3} for n>0 is A015518, non-closed walks.
Cf. A001045, A078008, A097073, A115341, A015518 (sequences where a(n)=3^n-a(n-1)). - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

[(3^n+(-1)^n*3)/4: n in [0..35]]; // Vincenzo Librandi, Jun 30 2011

A054878:=n->(3^n + (-1)^n*3)/4: seq(A054878(n), n=0..50); # Wesley Ivan Hurt, Sep 16 2017

Table[(3^n + (-1)^n*3)/4, {n, 0, 26}] (* or *)
CoefficientList[Series[1/4*(3/(1 + x) + 1/(1 - 3 x)), {x, 0, 26}], x] (* Michael De Vlieger, Sep 15 2017 *)

a(n) = (3^n + 3*(-1)^n)/4; \\ Altug Alkan, Sep 17 2017

a(n) = (3^n + (-1)^n*3)/4.
G.f.: 1/4*(3/(1+x) + 1/(1-3*x)).
E.g.f.: (exp(3*x) + 3*exp(-x))/4. - Paul Barry, Apr 20 2003
a(n) = 3^n - a(n-1) with a(0)=0. - Labos Elemer, Apr 26 2003
G.f.: (1 - 3*x^2 - 2*x^3)/(1 - 6*x^2 - 8*x^3 - 3*x^4) = (1 - 3*x^2 - 2*x^3)/charpoly(adj(C_4)). - Paul Barry, Feb 03 2004
From Paul Barry, Oct 02 2004: (Start)
G.f.: (1-2*x)/(1 - 2*x - 3*x^2).
a(n) = 2*a(n-1) + 3*a(n-2). (End)
G.f.: 1 - x + x/Q(0), where Q(k) = 1 + 3*x^2 - (3*k+4)*x + x*(3*k+1 - 3*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013
a(n+m) = a(n)*a(m) + a(n+1)*a(m+1)/3. - Yuchun Ji, Sep 12 2017
a(n) = 3*a(n-1) + 3*(-1)^n. - Yuchun Ji, Sep 13 2017
From Peter Bala, May 28 2024: (Start)
a(n) = (-1)^n + Sum_{k = 1..n} (-1)^(n-k)*binomial(n, k)*4^(k-1).
G.f.: A(x) = 1/(1 - x^2) o 1/(1 - x^2), where o denotes the black diamond product of power series as defined by Dukes and White. Cf. A015575.
The black diamond product A(x) o A(x) is the g.f. for the number of closed walks of length n at a vertex along the edges of the 15-simplex. (End)

A092297 Number of ways of 3-coloring an annulus consisting of n zones joined like a pearl necklace.

Original entry on oeis.org

0, 6, 6, 18, 30, 66, 126, 258, 510, 1026, 2046, 4098, 8190, 16386, 32766, 65538, 131070, 262146, 524286, 1048578, 2097150, 4194306, 8388606, 16777218, 33554430, 67108866, 134217726, 268435458, 536870910, 1073741826, 2147483646

Offset: 1

S. B. Step (stepy(AT)vesta.ocn.ne.jp), Feb 06 2004

A circular domain means a domain between two concentric circles and it is divided into n parts by n boundary lines perpendicular to the circles. Both sides of a line must have different colors. How many ways of coloring are there?
a(n) is also the multiple of six that's nearest to 2^n. - David Eppstein, Aug 31 2010
a(n) apparently is the trace of the n-th power of the adjacency matrix of the complete 3-graph, a 3 X 3 matrix with diagonal elements all zero and off-diagonal all ones (cf. A001045). If so, a(n) is the number of closed walks on the graph of length n. - Tom Copeland, Nov 06 2012
For n >= 2, a(n) is the number of length n words on 3 letters with no two consecutive like letters including the first and the last. Cf. A218034. - Geoffrey Critzer, Apr 05 2014

			a(2)=6 because we can color one zone in 3 colors and the other in 2, so 2*3=6 in all.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
K. Böhmová, C. Dalfó, and C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
Cristina Dalfó, From subKautz digraphs to cyclic Kautz digraphs, arXiv:1709.01882 [math.CO], 2017.
Cristina Dalfó, The spectra of subKautz and cyclic Kautz digraphs, Linear Algebra and its Applications, 531 (2017), p. 210-219.
Fern Gossow, Lyndon-like cyclic sieving and Gauss congruence, arXiv:2410.05678 [math.CO], 2024. See p. 25.
Paul P. Martin and Siti Fatimah Zakaria, Zeros of the 4-state Potts model partition function for the square lattice revisited, J. Stat. Mech. 084003 (2019). eq. (7).
Carlos I. Perez-Sanchez, The Spectral Action on quivers, arXiv:2401.03705 [math.RT], 2024.
Index entries for linear recurrences with constant coefficients, signature (1,2).

Column k=3 of A106512.

Cf. A001045.

[2^n+2*(-1)^n : n in [1..40]]; // Vincenzo Librandi, Sep 27 2011

nn=28;Drop[CoefficientList[Series[6x^2/(1+x)^2/(1-3x/(1+x)),{x,0,nn}],x],1] (* Geoffrey Critzer, Apr 05 2014 *)
a[ n_] := 2 (2^(n - 1) + (-1)^n); (* Michael Somos, Oct 25 2014 *)
a[ n_] := If[ n < 1, -(-2)^(n - 1) a[2 - n] , (-1)^n HypergeometricPFQ[ Table[ -2, {k, n}], Table[ 1, {k, n - 1}], 1]] (* Michael Somos, Oct 25 2014 *)
LinearRecurrence[{1,2},{0,6},40] (* Harvey P. Dale, May 21 2024 *)

{a(n) = 2 * (2^(n-1) - (-1)^n)}; /* Michael Somos, Oct 25 2014 */

a(n) = 2^n + 2*(-1)^n; recurrence a(1)=0, a(2)=6, a(n) = 2*a(n-2) + a(n-1).
O.g.f: -6*x^2/((1+x)*(2*x-1)) = -3 - 1/(2*x-1) + 2/(1+x). - R. J. Mathar, Dec 02 2007
a(n) = 6*A001045(n-1). - R. J. Mathar, Aug 30 2008
a(n) = (-1)^n * a(2-n) * 2^(n-1) for all n in Z. - Michael Somos, Oct 25 2014

A007040 Number of (marked) cyclic n-bit binary strings containing no runs of length > 2.

Original entry on oeis.org

2, 2, 6, 6, 10, 20, 28, 46, 78, 122, 198, 324, 520, 842, 1366, 2206, 3570, 5780, 9348, 15126, 24478, 39602, 64078, 103684, 167760, 271442, 439206, 710646, 1149850, 1860500, 3010348, 4870846, 7881198, 12752042, 20633238, 33385284, 54018520

Offset: 1

N. J. A. Sloane

For n >= 3, also the number of maximal independent vertex sets (and minimal vertex covers) in the n-prism graph. - Eric W. Weisstein, Mar 30 and Aug 07 2017
From Petros Hadjicostas, Jul 08 2018: (Start)
Let q and m be positive integers. We denote by f1(m,q,n) the number of (marked) cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.
It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.
Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
By generalizing Moser (1991, 1993), Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).
Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).
A necklace is an unmarked cyclic string. If f3(m,q,n) is the number of q-ary necklaces of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).
For the current sequence, we have q = 2 and m = 2. We have a(n) = f1(m=2, q=2, n) = f2(m=2, q=2, n) for n >= 3, but for a(1) and a(2) it is unclear what approach the author of the sequence is following. He has a(1) = q^1 = 2, but a(2) = q^2 - q = 2^2 - 2 = 2. (Note that, for q = m = 2, we have f1(m=2, q=2, 1) = 2, f1(m=2, q=2, 2) = 4, f2(m=2, q=2, 1) = 0, and f2(m=2, q=2, 2) = 2.)
If A(x) is the g.f. of the current sequence, we have A(x) = F1(m=2,q=2, x) - 2*x^2 = F2(m=2, q=2, x) + 2*x.
When m = 1 and q = 3, we have f1(m=1, q=3, n) = number of marked cyclic words on three letters with no two consecutive like letters. We have f1(m=1, q=3, n) = A092297(n) for n >= 2. This was first stated in the comments of that sequence by G. Critzer.
When m = 1 and q = 4, we have f1(m=1, q=4, n) = number of marked cyclic words on four letters with no two consecutive like letters. We have f1(m=1, q=4, n) = A218034(n) for n >= 1. This was first stated in the comments of that sequence by J. Arndt.
A generalization of the above formula by Burstein and Wilf (1997) was given by Taylor (2014) in Section 5 of his paper. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Z. Agur, A. S. Fraenkel, and S. T. Klein, The number of fixed points of the majority rule, Discr. Math., 70 (1988), 295-302.
A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
W. Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
Matthew Macauley, Jon McCammond, and Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, 33(1) (2011), 11-35.
A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80(1) (2007), 29-37.
W. O. J. Moser, On cyclic binary n-bit strings, Report from the Department of Mathematics and Statistics, McGill University, 1991. (Annotated scanned copy)
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31(1) (1993), 2-6.
Noriaki Sannomiya, Hosho Katsura, and Yu Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv:1612.02285 [cond-mat.str-el], 2016. See Table I, line 2.
Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set.
Eric Weisstein's World of Mathematics, Minimal Vertex Cover.
Eric Weisstein's World of Mathematics, Prism Graph.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).

Cf. A000032, A007039, A316660.

Join[{2}, LinearRecurrence[{0, 1, 2, 1}, {2, 6, 6, 10}, 40]] (* Harvey P. Dale, Nov 09 2011 *)
Join[{2}, Table[n Sum[Binomial[2 k, n - 2 k]/k, {k, n}], {n, 2, 40}]] (* Harvey P. Dale, Nov 09 2011 *)
Table[LucasL[n] + 2 Cos[2 n Pi/3], {n, 20}] (* Eric W. Weisstein, Mar 30 2017 *)

a(n)=if(n<3,2,([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,2,1,0]^(n-2)*[2;6;6;10])[1,1]) \\ Charles R Greathouse IV, Jun 15 2015

a(n) = a(n-2) + 2*a(n-3) + a(n-4), n >= 7. - David W. Wilson
a(n) = n*Sum_{k=1..n} binomial(2*k, n-2*k)/k for n > 1 with a(0) = 0 and a(1) = 2. - Vladimir Kruchinin, Oct 12 2011
G.f.: 2*x*(1 + x + 2*x^2 - x^4)/((1 - x - x^2)*(1 + x + x^2)). - Colin Barker, Mar 15 2012
a(n) = A000032(n) + 2*cos(2*Pi*n/3) for n > 1. - Eric W. Weisstein, Mar 30 2017
a(n) = 2*A100886(n-1), n > 1. - R. J. Mathar, Jan 20 2018
a(n) = A000032(n) - A061347(n) for n > 1. - Wojciech Florek, Feb 18 2018

Name clarified by Petros Hadjicostas, Jul 08 2018

A226493 Closed walks of length n in K_4 graph.

Original entry on oeis.org

0, 12, 24, 84, 240, 732, 2184, 6564, 19680, 59052, 177144, 531444, 1594320, 4782972, 14348904, 43046724, 129140160, 387420492, 1162261464, 3486784404, 10460353200, 31381059612, 94143178824, 282429536484, 847288609440, 2541865828332, 7625597484984, 22876792454964

Offset: 1

Gustavo Gordillo, Jun 09 2013

Essentially the same as A218034.

Mike Krebs and Tony Shaheen, Expander Families and Cayley Graphs, Oxford University Press, Inc. 2011

K. Böhmová, C. Dalfó, and C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
Cristina Dalfó, From subKautz digraphs to cyclic Kautz digraphs, arXiv:1709.01882 [math.CO], 2017.
C. Dalfó, The spectra of subKautz and cyclic Kautz digraphs, Linear Algebra and its Applications, 531 (2017), p. 210-219.
Carlos I. Perez-Sanchez, The Spectral Action on quivers, arXiv:2401.03705 [math.RT], 2024.
Index entries for linear recurrences with constant coefficients, signature (2,3).

Column k=4 of A106512.

Cf. A218034.

Mathematica
```
Table[3 (-1)^k + 3^k, {k, 30}]
```

a(n) = { 3*(-1)^n + 3^n } \\ Andrew Howroyd, Sep 11 2019

a(n) = 3*(-1)^n + 3^n = 12*A015518(n-1).

G.f.: 12*x^2 / ( (1+x)*(1-3*x) ). - R. J. Mathar, Jun 29 2013

A326347 Number of unordered pairs of 4-colorings of an n-cycle that differ in the coloring of exactly one vertex.

Original entry on oeis.org

36, 240, 780, 2952, 10164, 35040, 118044, 393720, 1299012, 4251600, 13817388, 44641128, 143488980, 459165120, 1463588412, 4649045976, 14721978468, 46490458800, 146444944716, 460255541064, 1443528741876, 4518872583840, 14121476823900, 44059007691192

Offset: 3

Andrew Howroyd, Sep 11 2019

Andrew Howroyd, Table of n, a(n) for n = 3..200
Eric Weisstein's World of Mathematics, Cycle Graph
Index entries for linear recurrences with constant coefficients, signature (4,2,-12,-9).

Cf. A046717, A218034, A309380.

PARI
```
a(n) = 6*n*(3^(n-2) + (-1)^n);
```

a(n) = n*(3*A218034(n-2) + A218034(n-1)).
a(n) = 6*n*(3^(n-2) + (-1)^n).
a(n) = 12*n*A046717(n-2).
a(n) = 4*a(n-1) + 2*a(n-2) - 12*a(n-3) - 9*a(n-4) for n > 6.
G.f.: 12*x^3*(3 + 8*x - 21*x^2 - 18*x^3)/((1 + x)^2*(1 - 3*x)^2).

A316660 Number of n-bit binary necklaces (unmarked cyclic n-bit binary strings) containing no runs of length > 2.

Original entry on oeis.org

0, 1, 2, 2, 2, 5, 4, 7, 10, 14, 18, 31, 40, 63, 94, 142, 210, 329, 492, 765, 1170, 1810, 2786, 4341, 6712, 10461, 16274, 25414, 39650, 62075, 97108, 152287, 238838, 375166, 589526, 927555, 1459960, 2300347, 3626242, 5721044, 9030450, 14264309, 22542396, 35646311, 56393862

Offset: 1

Petros Hadjicostas, Jul 09 2018

nonn

This is the "unmarked" version of sequence A007040. An unmarked cyclic string is a necklace. Notice that we define a(1) = 0 and a(2) = 1 because wrapping around the circle is allowed here (otherwise we would have to let a(1) = 2 and a(2) = 3).
Let q and m be positive integers. We denote by f1(m,q,n) the number of marked cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.
It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.
Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
By generalizing Moser (1993), Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).
Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).
If f3(m,q,n) is the number of q-ary necklaces (= unmarked cyclic strings) of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).
If A(x) is the g.f. of the current sequence (a(n): n >= 1), we have A(x) = F3(m=2, q=2, x). Also, a(n) = f3(m=2, q=2, n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m=2, q=2, d). Note that f2(m=2, q=2, n=1) = 0 and f2(m=2, q=2, n) = A007040(n) for n >= 2.

			For n=1 we have no allowable necklaces (because the strings 0 and 1 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
For n=2, the only allowable necklace is 01 (because 00 and 11 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
For n=3, the allowable necklaces are 011 and 100.
For n=4, the allowable necklaces are 0011 and 1010.
For n=5, the allowable necklaces are 01010 and 10101.
For n=6, the allowable necklaces are 010101, 001001, 110110, 101001, and 010110.

A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.

Cf. A000358, A007040, A011655, A092297, A218034.

a(n) = (1/n) * sumdiv(n, d, eulerphi(n/d)*(fibonacci(d-1)+fibonacci(d+1))) - sign(n%3); \\ Michel Marcus, Jul 10 2018; using 2nd formula

For proofs of the following formulae, see the comments above.
a(n) = (1/n)*Sum_{d|n} phi(n/d)*A007040(d)*I(d > 1), where I(condition) = 1 if the condition holds, and 0 otherwise.
a(n) = A000358(n) - A011655(n). (This formula is the "unmarked" version of E. W. Weisstein's formula that can be found in the comments for sequence A007040.)
a(p) = A007040(p)/p for p prime >= 2.
G.f.: A(x) = -x*(1+x)/(1-x^3) - Sum_{s>=1} (phi(s)/s)*log(1 - x^s - x^(2*s)) = (g.f. of A000358) - (g.f. of A011655).

More terms from Michel Marcus, Jul 10 2018

A316699 Number of (marked) cyclic n-bit binary strings containing no runs of length > 3.

Original entry on oeis.org

2, 4, 8, 14, 20, 38, 70, 134, 240, 442, 814, 1502, 2756, 5070, 9326, 17158, 31552, 58034, 106742, 196334, 361108, 664182, 1221622, 2246918, 4132720, 7601258, 13980894, 25714878, 47297028, 86992798

Offset: 1

Petros Hadjicostas, Jul 10 2018

Let q and m be positive integers. We denote by f1(m,q,n) the number of (marked) cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.
It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.
Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).
Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).
A necklace is an unmarked cyclic string. If f3(m,q,n) is the number of q-ary necklaces of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).
For the current sequence, we have q = 2 and m = 3. We have a(n) = f1(m=3, q=2, n) = f2(m=3, q=2, n) for n >= 4, but we have f1(m=3, q=2, n) = 2^n and f2(m=3, q=2, n) = 2^n - 2 for n = 1,2,3.
If A(x) is the g.f. of the current sequence, we have A(x) = F1(m=3,q=2, x) = F2(m=3, q=2, x) + 2*(x+x^2+x^3).
When m = 1 and q = 3, we have f1(m=1, q=3, n) = number of marked cyclic words on three letters with no two consecutive like letters. We have f1(m=1, q=3, n) = A092297(n) for n >= 2. This was first stated in the comments of that sequence by G. Critzer.
When m = 1 and q = 4, we have f1(m=1, q=4, n) = number of marked cyclic words on four letters with no two consecutive like letters. We have f1(m=1, q=4, n) = A218034(n) for n >= 1. This was first stated in the comments of that sequence by J. Arndt.
When m=2 and q=2, we have f1(m=2, q=2, n) = number of marked cyclic words on two letters containing no runs of length > 2. We have f1(m=2, q=2, n) = A007040(n) for n >= 3.
A generalization of the above formula by Burstein and Wilf (1997) was given by Taylor (2014) in Section 5 of his paper.

			For n=4, we have a(4) = 2^4 - 2 = 14 because we exclude 0000 and 1111.
For n=5, we have a(5) = 2^5 - 12 = 20 because we exclude 11111, 11110, 11101, 11011, 10111, 01111, and the same 6 strings with 0 switched with 1.
For n=6, we have a(6) = 2^6 - 26 = 38 because we exclude 111100, 111001, 110011, 100111, 001111, 011110, 111110, 111101, 111011, 110111, 101111, 011111, 111111, and the same 13 strings with 0 switched with 1.

G. C. Greubel, Table of n, a(n) for n = 1..1000
A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80(1) (2007), 29-37.
Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,3,2,1).

Cf. A001644, A007040, A092297, A176563, A218034.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( 2*x*(1+ x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3)) )); // G. C. Greubel, Apr 23 2019

Rest[CoefficientList[Series[2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3)), {x, 0, 40}], x]] (* G. C. Greubel, Apr 23 2019 *)

my(x='x+O('x^40)); Vec(2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3))) \\ G. C. Greubel, Apr 23 2019

a=(2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3))).series(x, 40).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Apr 23 2019

a(n) = A001644(n) + cos(n*Pi) + 2*cos(n*Pi/2) = A001644(n) - A176563(n+1) for n >= 4.
G.f.: 2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3) ).
a(n) = a(n-2) + 2*a(n-3) + 3*a(n-4) + 2*a(n-5) + a(n-6) for n>9. - Colin Barker, Jul 28 2019

cp's OEIS Frontend

A054878 Number of closed walks of length n along the edges of a tetrahedron based at a vertex.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A092297 Number of ways of 3-coloring an annulus consisting of n zones joined like a pearl necklace.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A007040 Number of (marked) cyclic n-bit binary strings containing no runs of length > 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A226493 Closed walks of length n in K_4 graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A326347 Number of unordered pairs of 4-colorings of an n-cycle that differ in the coloring of exactly one vertex.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A316660 Number of n-bit binary necklaces (unmarked cyclic n-bit binary strings) containing no runs of length > 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A316699 Number of (marked) cyclic n-bit binary strings containing no runs of length > 3.

Views

Author

Keywords

Comments

Examples

Links