OFFSET
0,13
COMMENTS
See page 5, figure 1 in the reference.
A zigzag is a substring which is either 010 or 101.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..819
E. Munarini and N. Z. Salvi, Circular Binary Strings without Zigzags, Integers: Electronic Journal of Combinatorial Number Theory 3 (2003), #A19.
FORMULA
From Andrew Howroyd, Feb 26 2017: (Start)
T(n,m) = Sum_{k>=0} U(m,k)*U(n,k) - 2*V(m,k)*V(n,k)*(-1)^k
where U(r,k)=binomial(r-k+2*floor(k/3), floor(k/3)), V(r,k)=binomial(r-ceiling(k/2)-1, floor(k/2)).
T(n,0)=1 for n>=1, T(n,1)=0 for n>=1, T(n,2)=n+2 for n>=2, T(n,3)=n+3 for n>=2.
T(n,4)=(n-1)*(n+4)/2 for n>=3, T(n,5)=(n-2)*(n+5) for n>=3. (End)
EXAMPLE
Table starts:
0 1 1 1 1 1 1 1 1 1 1 1 1 ...
1 0 0 0 0 0 0 0 0 0 0 0 0 ...
1 0 4 5 6 7 8 9 10 11 12 13 14 ...
1 0 5 6 7 8 9 10 11 12 13 14 15 ...
1 0 6 7 12 18 25 33 42 52 63 75 88 ...
1 0 7 8 18 30 44 60 78 98 120 144 170 ...
1 0 8 9 25 44 70 104 147 200 264 340 429 ...
1 0 9 10 33 60 104 168 255 368 510 684 893 ...
1 0 10 11 42 78 147 255 412 629 918 1292 1765 ...
1 0 11 12 52 98 200 368 629 1014 1558 2300 3283 ...
1 0 12 13 63 120 264 510 918 1558 2514 3885 5786 ...
MATHEMATICA
max = 11;
U[r_, k_] := Binomial[r - k + 2*Floor[k/3], Floor[k/3]];
V[r_, k_] := Binomial[r - Ceiling[k/2] - 1, Floor[k/2]];
T[0, 0] = T[1, 1] = 0;
T[0, _] = T[_, 0] = 1;
T[n_ /; n >= 2, m_] /; m <= n := T[n, m] = Switch[m, 1, 0, 2, n + 2, 3, n + 3, _, Sum[ U[m, k]*U[n, k] - 2*V[m, k]*V[n, k]*(-1)^k, {k, 0, max-3}]];
T[n_, m_] /; m > n := T[m, n];
Table[T[n - k, k], {n, 0, max}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 01 2018, after Andrew Howroyd *)
CROSSREFS
KEYWORD
tabl,nonn
AUTHOR
Felix Fröhlich, Oct 23 2015
EXTENSIONS
a(66)-a(77) from Andrew Howroyd, Feb 26 2017
STATUS
approved