A263656 Number of length-2n central circular binary strings without zigzags (see reference for precise definition).

0, 0, 4, 6, 12, 30, 70, 168, 412, 1014, 2514, 6270, 15702, 39468, 99516, 251586, 637500, 1618638, 4117102, 10488684, 26758762, 68354250, 174810354, 447533586, 1146836662, 2941443180, 7550434480, 19395863358, 49859516292, 128252962434, 330101861850

Offset: 0

Author

Felix Fröhlich, Oct 23 2015

Keywords

• nonn

Comments

See page 6 in the reference.

A zigzag is a substring which is either 010 or 101. The central binary strings are those that contain an equal number of 0's and 1's.

Examples

			For n=3 the 6 strings are 000111, 001110, 011100, 111000, 110001, 100011.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..100
• E. Munarini and N. Z. Salvi, Circular Binary Strings without Zigzags, Integers: Electronic Journal of Combinatorial Number Theory 3 (2003), #A19.

Crossrefs

Main diagonal of A263655.

Cf. A007039, A263657, A263658, A263659.

Programs

Mathematica

a[n_ /; n < 6] := {0, 0, 4, 6, 12, 30}[[n + 1]]; a[n_] := a[n] = (-(3*(n - 6)*a[n - 6]) + (7*n - 37)*a[n - 5] - 6*a[n - 4] + (7*n - 27)*a[n - 3] - 4*(n - 4)*a[n - 2] + 3*(n - 1)*a[n - 1])/n;
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

Formula

a(n) = (1/n)*(3*(n-1)*a(n-1) - 4*(n-4)*a(n-2) + (7*n-27)*a(n-3) - 6*a(n-4) + (7*n-37)*a(n-5) - 3*(n-6)*a(n-6)) for n >= 6. - Andrew Howroyd, Feb 26 2017

Extensions

corrected a(1) and a(17)-a(30) from Andrew Howroyd, Feb 26 2017