OFFSET
0,4
COMMENTS
Given the problem case given in A370448 and A370449, the choice in positioning the first random number r_1 leads to a success probability density function PDF_L(r_1), where the success probability is the probability that with this choice, all future numbers will still be able to be placed following the optimal strategy.
With a list of n spaces, placing r_1 such that there are L free places to the left and R=n-1-L free places to the right, the PDF is of the form C_{L,R} * r_1^L * (1-r_1)^R (see also: A370448, example section).
{C(n)} = A370450(n)/A370451(n) provides the C coefficient triangle row by row, where the row number N is defined by N=L+R, and the column is either L or R (the triangle is symmetric).
As such, n is converted to an (N,L,R) tuple as follows: 0 -> (0,0,0), 1 -> (1,0,1), 2 -> (1,1,0), 3 -> (2,0,2), 4 -> (2,1,1), 5 -> (2,2,0), 6 -> (3,0,3), 7 -> (3,1,2), ...
All coefficients {C(n)}(n) are rational.
LINKS
Philip Geißler, Table of n, a(n) for n = 0..27
FORMULA
EXAMPLE
For n=3 (L=0, R=2), the first number r_1 was placed on the leftmost free space of the 3 space list (0 free spaces on the left, 2 on the right).
The problem can now be constrained to solving the case of a list with only 2 spaces to fill.
For such a list, the success probability is 3/4 = A370448(2)/A370449(2) (see A370448, example section).
However, there is the extra constraint that both other random numbers r_2 and r_3 need to be smaller than r_1 as well.
This results in the success probability density function PDF(r_1) = 3/4 * (1-r_1)*(1-r_1), which is dependent on the value of r_1, but assumes no knowledge of r_2 and r_3.
For n=4 (L=1, R=1), the first number r_1 was placed on the middle free space of the 3 space list (1 free spaces on the left, 1 on the right).
The problem can now be constrained to solving the case of a list with only 1 space to fill twice.
For such a list, the success probability is P(1) = 1 = A370448(1)/A370449(1) (see A370448, example section).
However, there is the extra constraint that one of the other random numbers r_2 and r_3 needs to be smaller than r_1, and the other needs to be greater than r_1.
There are 2 permutations that achieve this, and thus PDF(r_1) = 2 * 1 * 1 * (1-r_1)*(r_1) = Number of Permutations * P(1) * P(1) * (1-r_1)^1 * (r_1)^1
The coefficient of the PDF is 2*1*1 = 2 = 2/1 = A370450(4)/A370451(4), and the denominator is thus a(4)=1.
The triangle begins:
1;
1 1;
4 1 4;
726 4 4 726;
PROG
CROSSREFS
KEYWORD
AUTHOR
Philip Geißler, Feb 18 2024
STATUS
approved