login
A316699
Number of (marked) cyclic n-bit binary strings containing no runs of length > 3.
1
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,1
COMMENTS
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.
LINKS
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.
FORMULA
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
EXAMPLE
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.
MATHEMATICA
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 *)
PROG
(PARI) 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
(Magma) R<x>:=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
(Sage) 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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Petros Hadjicostas, Jul 10 2018
STATUS
approved