OFFSET
1,1
COMMENTS
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)
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
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).
FORMULA
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
MATHEMATICA
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 *)
PROG
(PARI) 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
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Name clarified by Petros Hadjicostas, Jul 08 2018
STATUS
approved