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

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

Author

Petros Hadjicostas, Aug 31 2019

Keywords

• nonn
• tabl
• more

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

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

Formula

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.