OFFSET
0,3
COMMENTS
Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
LINKS
Robert Price, Table of n, a(n) for n = 0..1000
Chris Burns and Benjamin Purcell, A note on Stephan's conjecture 77, preprint, 2005. [Cached copy]
Chris Burns and Benjamin Purcell, Counting the number of winning strings in the 1-dimensional same game, Fibonacci Quarterly, 45(3) (2007), 233-238.
Sascha Kurz, Polynomials for same game, pdf.
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.
Index entries for linear recurrences with constant coefficients, signature (4, -2, -8, 6, 6, -3, -2).
FORMULA
G.f.: x(2x^6 - 6x^5 + 8x^4 + 2x^3 - 6x^2 + 2x)/[(1 - x^2)(1 - 2x)(1 - x - x^2)^2] (conjectured). - Ralf Stephan, May 11 2004. Established by Burns and Purcell - see link.
a(0) = 1, a(1) = 0, a(2) = 2, a(3) = 2, a(4) = 6, a(5) = 12, a(6) = 26, a(7) = 58, a(n) = 4*a(n-1) - 2*a(n-2) - 8*a(n-3) + 6*a(n-4) + 6*a(n-5) - 3*a(n-6) - 2*a(n-7). - Harvey P. Dale, Sep 26 2012
a(n) = 2^n - 2 * n * Fibonacci(n-2) - (-1)^n - 1 for n >= 2 (proved by Burns and Purcell (2005, 2007)). - Petros Hadjicostas, Jul 04 2018
EXAMPLE
11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.
MATHEMATICA
Join[{1}, Rest[CoefficientList[Series[x (2x^6 - 6x^5 + 8x^4 + 2x^3 - 6x^2 + 2x)/((1 - x^2)(1 - 2x)(1 - x - x^2)^2), {x, 0, 40}], x]]] (* or *) Join[{1}, LinearRecurrence[{4, -2, -8, 6, 6, -3, -2}, {0, 2, 2, 6, 12, 26, 58}, 40]] (* Harvey P. Dale, Sep 26 2012 *)
PROG
(PARI) a(n)=if(n, ([0, 1, 0, 0, 0, 0, 0; 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 1; -2, -3, 6, 6, -8, -2, 4]^(n-1)*[0; 2; 2; 6; 12; 26; 58])[1, 1], 1) \\ Charles R Greathouse IV, Jun 15 2015
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Naohiro Nomoto, Jul 09 2001
Further terms from Sascha Kurz, Oct 19 2001
a(27)-a(36) from Robert Price, Apr 08 2019
STATUS
approved