A065238 -id:A065238 - cp's OEIS frontend

A035615 Number of winning length n strings with a 2-symbol alphabet in "same game".

1, 0, 2, 2, 6, 12, 26, 58, 126, 278, 602, 1300, 2774, 5878, 12350, 25778, 53470, 110332, 226610, 463602, 945214, 1921550, 3896642, 7885092, 15927086, 32121582, 64697726, 130166378, 261637446, 525478668, 1054673162, 2115601450, 4241716734, 8501080838, 17031744170

Offset: 0

Erich Friedman

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

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).

Cf. A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243.
See A309874 for the losing strings.
For some similar questions in base 10, see A323830, A323831, A320487. - N. J. A. Sloane, Feb 04 2019
Row b=2 of A323844.

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 *)

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

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

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

A035617 Number of winning length n strings with a 3-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 3, 3, 15, 33, 105, 297, 879, 2631, 7833, 23697, 71385, 216765, 657849, 2003151, 6103743, 18624693, 56870385, 173760513, 531128349, 1623881889, 4965695331, 15185222199, 46435889601, 141985777503

Offset: 0

Erich Friedman

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Dec 27 2018

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

C. Burns and B. Purcell, A note on Stephan's conjecture 77, preprint, 2005.
C. Burns and B. Purcell, Counting the number of winning strings in the 1-dimensional same game Fibonacci Quarterly, 45(3) (2007), 233-238.
Sascha Kurz, Polynomials in "same game", 2001. [ps file]
Sascha Kurz, Polynomials in "same game", 2001. [pdf file]

Cf. A035615, A065237, A065238, A065239, A065240, A065241, A065242, A065243.

Row b=3 of A323844.

a(16)-a(25) from Bert Dobbelaere, Dec 26 2018

A065237 Number of winning length n strings with a 4-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 4, 4, 28, 64, 268, 844, 3100, 10876, 39244, 142432, 518380, 1906012, 7012660, 25980940, 96407356, 359260936, 1341482740, 5023006444, 18844637356

Offset: 0

Sascha Kurz, Oct 23 2001

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Jul 05 2018

			11011001 is a winning string since 110{11}001->11{000}1->{111}->null.

C. Burns and B. Purcell, A note on Stephan's conjecture 77, preprint, 2005.
C. Burns and B. Purcell, Counting the number of winning strings in the 1-dimensional same game Fibonacci Quarterly, 45(3) (2007), 233-238.
Sascha Kurz, Polynomials in "same game", 2001. [ps file]
Sascha Kurz, Polynomials in "same game", 2001. [pdf file]

Cf. A035615, A035617, A065238, A065239, A065240, A065241, A065242, A065243.

Row b=4 of A323844.

a(13)-a(20) from Bert Dobbelaere, Dec 26 2018

A065243 Number of winning length n strings with a 10-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 10, 10, 190, 460, 4690, 17650, 136630, 651790, 4439890, 24056020, 154885870, 898393870, 5659321510, 34068918250, 213351643990

Offset: 0

Sascha Kurz, Oct 23 2001

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

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 in "same game", 2001. [ps file]
Sascha Kurz, Polynomials for same game, 2001. [pdf file]
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065242, A309874, A323812.

Row b=10 of A323844.

a(12)-a(16) from Bert Dobbelaere, Dec 24 2018

A309874 a(n) = 2nFibonacci(n-2) + (-1)^n + 1.

Original entry on oeis.org

2, 6, 10, 20, 38, 70, 130, 234, 422, 748, 1322, 2314, 4034, 6990, 12066, 20740, 35534, 60686, 103362, 175602, 297662, 503516, 850130, 1432850, 2411138, 4051350, 6798010, 11392244, 19068662, 31882198, 53250562, 88853754, 148125014

Offset: 2

Petros Hadjicostas, Sep 01 2019

For n >= 2, a(n) is the number of length n losing strings with a binary alphabet in the "same game".
In the "same game", winning strings are those that can be reduced to the null string by repeatedly removing an entire run of two or more consecutive symbols.
Sequence A035615 counts the winning strings of length n in a binary alphabet in the "same game".

			For n=2, we have 2^2 = 4 strings of length 2 in the binary alphabet {0,1}: 00, 11, 01, and 10. Out of those strings, only 00 and 11 are winning strings in the "same game" because removing an entire run of two or more consecutive symbols gives the null string. Thus, a(2) = 2 (corresponding to the losing strings 01 and 10).
For n=3, we have 2^3 = 8 strings of length 3 in the binary alphabet {0,1}: 000, 001, 010, 100, 110, 101, 011, 111. Out of these, only the strings 000 and 111 are winning, while the rest a(2) = 6 strings are losing strings.
For n=4, we have 2^4 = 16 strings of length 4 in the binary alphabet {0,1}. From these, only 0000, 0011, 1100, 0110, 1001, and 1111 are winning strings while the rest a(4) = 16 - 6 = 10 are losing strings. (For example 0{11}0 -> 00 -> null.)
For n=8, the string 11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Robert Israel, Table of n, a(n) for n = 2..4764
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, 2001.
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 (2,2,-4,-2,2,1).

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243, A323812, A323844.

seq(2*n*combinat:-fibonacci(n-2) + (-1)^n + 1, n=2..100); # Robert Israel, Sep 03 2019

A309874[n_]:=Fibonacci[n-2]2n+(-1)^n+1;Array[A309874,50,2] (* Paolo Xausa, Nov 16 2023 *)

a(n) = 2^n - A323844(2,n) = 2^n - A035615(n) = 2*A323812(n) for n >= 2.

G.f.: x^2*(2 + 2*x - 6*x^2 - 4*x^3 + 6*x^4 + 2*x^5)/((1-x^2)*(1-x-x^2)^2). - Robert Israel, Sep 03 2019

A323844 Square array T(b,m), read by descending antidiagonals: Number of winning length m strings with a b-symbol alphabet in "same game" (b >= 2, m >= 0).

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 6, 3, 4, 0, 1, 12, 15, 4, 5, 0, 1, 26, 33, 28, 5, 6, 0, 1, 58, 105, 64, 45, 6, 7, 0, 1, 126, 297, 268, 105, 66, 7, 8, 0, 1, 278, 879, 844, 545, 156, 91, 8, 9, 0, 1, 602, 2631, 3100, 1825, 966, 217, 120, 9, 10, 0, 1

Offset: 0

Petros Hadjicostas, Aug 31 2019

Terms for this square array were calculated by Bert Dobbelaere, Erich Friedman, Sascha Kurz, and Robert Price (see the Crossrefs below).
This array counts strings that can be reduced to the null string by repeatedly removing an entire run of two or more consecutive symbols (see the example below and the references).
For binary strings (b = 2), the formula for the number of winning strings of length m (i.e., T(b=2, m) = 2^m - 2 * m * Fibonacci(m-2) - (-1)^m - 1 for m >= 2) was conjectured by Ralf Stephan (2004, p. 8) and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved.

			Table T(b,m) (with rows b >= 2 and columns m >= 0) begins as follows:
  1, 0, 2, 2,   6,  12,   26,   58,   126,    278,     602,    1300,     2774, ...
  1, 0, 3, 3,  15,  33,  105,  297,   879,   2631,    7833,   23697,    71385, ...
  1, 0, 4, 4,  28,  64,  268,  844,  3100,  10876,   39244,  142432,   518380, ...
  1, 0, 5, 5,  45, 105,  545, 1825,  7965,  30845,  128945,  527785,  2202785, ...
  1, 0, 6, 6,  66, 156,  966, 3366, 16986,  70386,  332646, 1484676,  6922146, ...
  1, 0, 7, 7,  91, 217, 1561, 5593, 32011, 139363,  732697, 3492265, 17899609, ...
  1, 0, 8, 8, 120, 288, 2360, 8632, 55224, 249656, 1443128, 7243552, 40366040, ...
  ...
11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

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 in "same game", 2001. [ps file]
Sascha Kurz, Polynomials for same game, 2001. [pdf file]
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

Cf. A035615 (row b=2), A035617 (row b=3), A065237 (row b=4), A065238 (row b=5), A065239 (row b=6), A065240 (row b=7), A065241 (row b=8), A065242 (row b=9), A065243 (row b=10), A238879, A309874 (losing strings for b=2), A323812 (one-half of the losing strings for b=2).

T(b=2, m) = 2^m - 2 * m * Fibonacci(m-2) - (-1)^m - 1 for m >= 2 (Burns and Purcell (2005, 2007)).
For the columns, Kurz (2001) says: "Because of the fact, that a winning m-digit b-ary string can only have floor(m/2) different digits, there exists for T(b,m) a polynomial with maximal degree floor(m/2)." (I changed his n to m and his a(n,b) to T(b,m).)
Kurz (2001) goes on to list the following formulas (without proof) for the columns of the array (valid for b >= 1):
T(b,1) = 0;
T(b,2) = b;
T(b,3) = b;
T(b,4) = 2*b^2 - b;
T(b,5) = 5*b^2 - 4*b;
T(b,6) = 5*b^3 - 3*b^2 - b;
T(b,7) = 21*b^3 - 35*b^2 + 15*b;
T(b,8) = 14*b^4 - 36*b^2 + 23*b;
T(b,9) = 84*b^4 - 204*b^3 + 162*b^2 - 41*b;
T(b,10) = 42*b^5 + 60*b^4 - 405*b^3 + 465*b^2 - 161*b;
T(b,11) = 330*b^5 - 990*b^4 + 990*b^3 - 341*b^2 + 12*b.
It is not clear whether Kurz's formulas are statements of fact (with an easy proof) or just conjectures.
From the results in the Crossrefs, we may also conjecture the following:
T(b,12) = 132*b^6 + 495*b^5 - 3135*b^4 + 5066*b^3 - 3384*b^2 + 827*b;
T(b,13) = 1287*b^6 - 4290*b^5 + 4004*b^4 + 585*b^3 - 2392*b^2 + 807*b;
T(b,14) = 429*b^7 + 3003*b^6 - 20020*b^5 + 40495*b^4 - 38402*b^3 + 18095*b^2 - 3599*b;
T(b,15) = 5005*b^7 - 17017*b^6 + 7098*b^5 + 38500*b^4 - 62455*b^3 + 36495*b^2 - 7625*b;
T(b,16) = 1430*b^8 + 16016*b^7 - 113568*b^6 + 266560*b^5 - 308660*b^4 + 197440*b^3 - 73376*b^2 + 14159*b.
It seems that, for m >= 2, T(b,m) is a polynomial of b of degree floor(m/2) with a leading coefficient equal to A238879(m-2). In other words, the leading coefficient equals (2/(m+2)) * binomial(m, m/2), if m is even >= 2, and binomial(m, (m - 3)/2) if m is odd >= 3.

A065239 Number of winning length n strings with a 6-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 6, 6, 66, 156, 966, 3366, 16986, 70386, 332646, 1484676, 6922146, 31921506, 149341506, 700002366, 3299514906, 15618721956, 74169285366

Offset: 0

Sascha Kurz, Oct 23 2001

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

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 in "same game", 2001. [ps file]
Sascha Kurz, Polynomials for same game, 2001. [pdf file]
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

Cf. A035615, A035617, A065237, A065238, A065240, A065241, A065242, A065243, A309874, A323812.

Row b=6 for A323844.

a(12)-a(18) from Bert Dobbelaere, Dec 26 2018

A065240 Number of winning length n strings with a 7-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 7, 7, 91, 217, 1561, 5593, 32011, 139363, 732697, 3492265, 17899609, 89014933, 455041825, 2311847083, 11875575355, 61080825757

Offset: 0

Sascha Kurz, Oct 23 2001

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

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 in "same game", 2001. [ps file]
Sascha Kurz, Polynomials for same game, 2001. [pdf file]
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

Cf. A035615, A035617, A065237, A065238, A065239, A065241, A065242, A065243, A309874, A323812.

Row b=7 of A323844.

a(12)-a(17) from Bert Dobbelaere, Dec 26 2018

A065241 Number of winning length n strings with an 8-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 8, 8, 120, 288, 2360, 8632, 55224, 249656, 1443128, 7243552, 40366040, 213357880, 1178216264, 6395922296, 35375108728, 194951335888

Offset: 0

Sascha Kurz, Oct 23 2001

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

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 in "same game", 2001. [ps file]
Sascha Kurz, Polynomials for same game, 2001. [pdf file]
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065242, A065243, A309874, A323812.

Row b=8 of A323844.

a(12)-a(17) from Bert Dobbelaere, Dec 26 2018

A065242 Number of winning length n strings with a 9-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 9, 9, 153, 369, 3393, 12609, 89145, 415161, 2614689, 13684977, 82237185, 457154577, 2704775985, 15524314425, 91659251961

Offset: 0

Sascha Kurz, Oct 23 2001

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

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 in "same game", 2001. [ps file]
Sascha Kurz, Polynomials for same game, 2001. [pdf file]
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065243, A309874, A323812.

Row b=9 of A323844.

a(12)-a(16) from Bert Dobbelaere, Dec 26 2018

cp's OEIS Frontend

A035615 Number of winning length n strings with a 2-symbol alphabet in "same game".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A035617 Number of winning length n strings with a 3-symbol alphabet in "same game".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A065237 Number of winning length n strings with a 4-symbol alphabet in "same game".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A065243 Number of winning length n strings with a 10-symbol alphabet in "same game".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A309874 a(n) = 2*n*Fibonacci(n-2) + (-1)^n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A323844 Square array T(b,m), read by descending antidiagonals: Number of winning length m strings with a b-symbol alphabet in "same game" (b >= 2, m >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A065239 Number of winning length n strings with a 6-symbol alphabet in "same game".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A065240 Number of winning length n strings with a 7-symbol alphabet in "same game".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A309874 a(n) = 2nFibonacci(n-2) + (-1)^n + 1.