A370399 Triangle read by rows: T(n, k) is the denominator of the probability of winning a certain game while playing optimally.
1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 3, 18, 6, 1, 1, 15, 60, 15, 10, 1, 1, 15, 2, 100, 25, 20, 1, 1, 15, 210, 75, 1050, 105, 35, 1, 1, 15, 5880, 5880, 73500, 29400, 588, 70, 1, 1, 135, 30240, 35280, 529200, 1852200, 15435, 588, 126, 1, 1, 135, 340200, 453600, 7938000, 466754400, 3111696, 1481760, 19845, 252, 1
Offset: 1
Examples
The values of Pr(n,k) begin as follows:
.
n\k| 0 1 2 3 4 5 6 7
---+---------------------------------------------------------
1 | 0/1 1/1
2 | 0/1 1/2 1/1
3 | 0/1 1/3 2/3 1/1
4 | 0/1 1/3 11/18 5/6 1/1
5 | 0/1 4/15 31/60 11/15 9/10 1/1
6 | 0/1 4/15 1/2 69/100 21/25 19/20 1/1
7 | 0/1 4/15 101/210 49/75 829/1050 94/105 34/35 1/1
...
We can calculate Pr(4,2) using the table below, given the values of Pr(n,k) for n=3 and for n=2. The leftmost column lists each of the six possible results of randomizing the n=4 tokens during the first move; in each randomized sequence, the red and blue tokens are represented by "r" and "b", respectively.
.
randomized probability result if result if
sequence of last 1 token last 2 tokens
of tokens occurrence is removed are removed
========== =========== ============== =============
rrbb 1/6 Pr(3,1) = 1/3 Pr(2,0) = 0/1
rbrb 1/6 Pr(3,1) = 1/3 Pr(2,1) = 1/2
brrb 1/6 Pr(3,1) = 1/3 Pr(2,1) = 1/2
rbbr 1/6 Pr(3,2) = 2/3 Pr(2,1) = 1/2
brbr 1/6 Pr(3,2) = 2/3 Pr(2,1) = 1/2
bbrr 1/6 Pr(3,2) = 2/3 Pr(2,2) = 1/1
.
For example, when we get rbrb it's better to remove the last two tokens (one r and one b) instead of removing only the last token (b). So the probability of winning M(4,2) is
Pr(4,2) = (1/6)(1/3) + (1/6)(1/2) + (1/6)(1/2) + (1/6)(2/3) + (1/6)(2/3) + (1/6)(1/1) = 11/18.
Of course Pr(n,k) >= k/n, because k/n could be achieved by removing 1 token on each move.
Crossrefs
Numerators are in A370398.
Extensions
More terms from Jon E. Schoenfield, Feb 24 2024
Comments