|
%I #68 Sep 02 2019 08:09:57
%S 1,0,2,2,6,12,26,58,126,278,602,1300,2774,5878,12350,25778,53470,
%T 110332,226610,463602,945214,1921550,3896642,7885092,15927086,
%U 32121582,64697726,130166378,261637446,525478668,1054673162,2115601450,4241716734,8501080838,17031744170
%N Number of winning length n strings with a 2-symbol alphabet in "same game".
%C Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
%H Robert Price, <a href="/A035615/b035615.txt">Table of n, a(n) for n = 0..1000</a>
%H Chris Burns and Benjamin Purcell, <a href="/A035615/a035615.pdf">A note on Stephan's conjecture 77</a>, preprint, 2005. [Cached copy]
%H Chris Burns and Benjamin Purcell, <a href="https://www.fq.math.ca/Papers1/45-3/burns.pdf">Counting the number of winning strings in the 1-dimensional same game</a>, Fibonacci Quarterly, 45(3) (2007), 233-238.
%H Sascha Kurz, Polynomials for same game, <a href="http://www.mathe2.uni-bayreuth.de/sascha/oeis/paper/same_game.pdf">pdf</a>.
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0409509">Prove or disprove: 100 conjectures from the OEIS</a>, arXiv:math/0409509 [math.CO], 2004.
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (4, -2, -8, 6, 6, -3, -2).
%F 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.
%F 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
%F 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
%e 11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.
%t 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 *)
%o (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
%Y Cf. A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243.
%Y See A309874 for the losing strings.
%Y For some similar questions in base 10, see A323830, A323831, A320487. - _N. J. A. Sloane_, Feb 04 2019
%Y Row b=2 of A323844.
%K nonn,nice,easy
%O 0,3
%A _Erich Friedman_
%E More terms from _Naohiro Nomoto_, Jul 09 2001
%E Further terms from _Sascha Kurz_, Oct 19 2001
%E a(27)-a(36) from _Robert Price_, Apr 08 2019
|
