|
| |
|
|
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).
|
|
12
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
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.
|
|
|
EXAMPLE
|
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.
|
|
|
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).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
