cp's OEIS Frontend

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

%I A323844 #93 Jan 05 2025 19:51:41
%S A323844 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,
%T A323844 64,45,6,7,0,1,126,297,268,105,66,7,8,0,1,278,879,844,545,156,91,8,9,
%U A323844 0,1,602,2631,3100,1825,966,217,120,9,10,0,1
%N 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).
%C A323844 Terms for this square array were calculated by _Bert Dobbelaere_, _Erich Friedman_, _Sascha Kurz_, and _Robert Price_ (see the Crossrefs below).
%C A323844 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).
%C A323844 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.
%H A323844 Chris Burns and Benjamin Purcell, <a href="/A035615/a035615.pdf">A note on Stephan's conjecture 77</a>, preprint, 2005. [Cached copy]
%H A323844 Chris Burns and Benjamin Purcell, <a href="https://web.archive.org/web/2024*/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 A323844 Sascha Kurz, <a href="http://www.mathe2.uni-bayreuth.de/sascha/oeis/paper/same_game.ps">Polynomials in "same game"</a>, 2001. [ps file]
%H A323844 Sascha Kurz, <a href="http://www.mathe2.uni-bayreuth.de/sascha/oeis/paper/same_game.pdf">Polynomials for same game</a>, 2001. [pdf file]
%H A323844 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.
%F A323844 T(b=2, m) = 2^m - 2 * m * Fibonacci(m-2) - (-1)^m - 1 for m >= 2 (Burns and Purcell (2005, 2007)).
%F A323844 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).)
%F A323844 Kurz (2001) goes on to list the following formulas (without proof) for the columns of the array (valid for b >= 1):
%F A323844 T(b,1) = 0;
%F A323844 T(b,2) = b;
%F A323844 T(b,3) = b;
%F A323844 T(b,4) = 2*b^2 - b;
%F A323844 T(b,5) = 5*b^2 - 4*b;
%F A323844 T(b,6) = 5*b^3 - 3*b^2 - b;
%F A323844 T(b,7) = 21*b^3 - 35*b^2 + 15*b;
%F A323844 T(b,8) = 14*b^4 - 36*b^2 + 23*b;
%F A323844 T(b,9) = 84*b^4 - 204*b^3 + 162*b^2 - 41*b;
%F A323844 T(b,10) = 42*b^5 + 60*b^4 - 405*b^3 + 465*b^2 - 161*b;
%F A323844 T(b,11) = 330*b^5 - 990*b^4 + 990*b^3 - 341*b^2 + 12*b.
%F A323844 It is not clear whether Kurz's formulas are statements of fact (with an easy proof) or just conjectures.
%F A323844 From the results in the Crossrefs, we may also conjecture the following:
%F A323844 T(b,12) = 132*b^6 + 495*b^5 - 3135*b^4 + 5066*b^3 - 3384*b^2 + 827*b;
%F A323844 T(b,13) = 1287*b^6 - 4290*b^5 + 4004*b^4 + 585*b^3 - 2392*b^2 + 807*b;
%F A323844 T(b,14) = 429*b^7 + 3003*b^6 - 20020*b^5 + 40495*b^4 - 38402*b^3 + 18095*b^2 - 3599*b;
%F A323844 T(b,15) = 5005*b^7 - 17017*b^6 + 7098*b^5 + 38500*b^4 - 62455*b^3 + 36495*b^2 - 7625*b;
%F A323844 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.
%F A323844 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.
%e A323844 Table T(b,m) (with rows b >= 2 and columns m >= 0) begins as follows:
%e A323844   1, 0, 2, 2,   6,  12,   26,   58,   126,    278,     602,    1300,     2774, ...
%e A323844   1, 0, 3, 3,  15,  33,  105,  297,   879,   2631,    7833,   23697,    71385, ...
%e A323844   1, 0, 4, 4,  28,  64,  268,  844,  3100,  10876,   39244,  142432,   518380, ...
%e A323844   1, 0, 5, 5,  45, 105,  545, 1825,  7965,  30845,  128945,  527785,  2202785, ...
%e A323844   1, 0, 6, 6,  66, 156,  966, 3366, 16986,  70386,  332646, 1484676,  6922146, ...
%e A323844   1, 0, 7, 7,  91, 217, 1561, 5593, 32011, 139363,  732697, 3492265, 17899609, ...
%e A323844   1, 0, 8, 8, 120, 288, 2360, 8632, 55224, 249656, 1443128, 7243552, 40366040, ...
%e A323844   ...
%e A323844 11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.
%Y A323844 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).
%K A323844 nonn,tabl,more
%O A323844 0,4
%A A323844 _Petros Hadjicostas_, Aug 31 2019