A309874 -id:A309874 - 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

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

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.

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

Original entry on oeis.org

1, 0, 5, 5, 45, 105, 545, 1825, 7965, 30845, 128945, 527785, 2202785, 9222985, 38818505, 164436125, 698347645, 2981306665, 12756855065

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, A065239, A065240, A065241, A065242, A065243, A309874, A323812.

Row b=5 of A323844.

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

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

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

Original entry on oeis.org

1, 3, 5, 10, 19, 35, 65, 117, 211, 374, 661, 1157, 2017, 3495, 6033, 10370, 17767, 30343, 51681, 87801, 148831, 251758, 425065, 716425, 1205569, 2025675, 3399005, 5696122, 9534331, 15941099, 26625281, 44426877, 74062507, 123360230, 205303933, 341416205, 567353377, 942154863, 1563526761

Offset: 2

Petros Hadjicostas, Sep 01 2019

nonn

For n >= 2, a(n) is one-half 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", while A309874 counts the losing strings.
Thus, a(n) = A309874(n)/2 for n >= 2. The reason sequence A309874 is divisible by 2 is because the complement of every winning string is also a winning string (where by "complement" we mean 0 is replaced with 1 and vice versa).

			11011001 is a winning string because 110{11}001 -> 11{000}1 -> {111} -> null. Its complement, 00100110 is also a winning string because 001{00}110 -> 00{111}0 -> {000} -> 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 for same game, pdf.
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, A065243, A309874, A323844.

Table[n Fibonacci[n-2]+((-1)^n+1)/2,{n,2,40}] (* Harvey P. Dale, Sep 17 2019 *)

a(n) = A309874(n)/2 for n >= 2.

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

Original entry on oeis.org

2, 2, 6, 12, 26, 50, 98, 182, 338, 612, 1102, 1958, 3458, 6058, 10558, 18300, 31586, 54298, 93026, 158878, 270602, 459732, 779286, 1318222, 2225666, 3751250, 6312438, 10606572, 17797418, 29825282, 49922402, 83468678, 139411778, 232622148, 387796318, 645922550, 1074985346, 1787678458, 2970700846

Offset: 0

N. J. A. Sloane, Feb 20 2019

This sequence is distantly related to the number of losing strings using a binary alphabet in the "same game" described by Burns and Purcell (2007) and Kurz (2001). - Petros Hadjicostas, Sep 01 2019

Colin Barker, Table of n, a(n) for n = 0..1000
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.
Index entries for linear recurrences with constant coefficients, signature (2,2,-4,-2,2,1).

Cf. A000045, A035615, A099920, A309874, A324129.

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

Vec(2*(1 - x - x^2 + 2*x^3 + x^4 - x^5) / ((1 - x)*(1 + x)*(1 - x - x^2)^2) + O(x^40)) \\ Colin Barker, Mar 03 2019

From Chai Wah Wu, Feb 20 2019: (Start)
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3) - 2*a(n-4) + 2*a(n-5) + a(n-6) for n > 5.
G.f.: (2*x^5 - 2*x^4 - 4*x^3 + 2*x^2 + 2*x - 2)/((x - 1)*(x + 1)*(x^2 + x - 1)^2). (End)
From Petros Hadjicostas, Sep 01 2019: (Start)
a(n) = 2*A324129(n) for n >= 0.
a(n) = A309874(n) + 2*A099920(n-1) = 2^n - A035615(n) + 2*A099920(n-1) for n >= 2.[Here A309874 counts the losing strings while A035615 counts the winning strings using a binary alphabet in the "same game". See Burns and Purcell (2007) and Kurz (2001).]
(End)

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

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