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 numerator is thus a(4)=2.
The triangle begins:
1;
1 1;
3 2 3;
377 9 9 377;
PROG
(Python)
import sympy, functools
from numpy.lib.stride_tricks import sliding_window_view as rolling
binomial_sym_sympy = lambda L, R : sympy.functions.combinatorial.factorials.binomial(L+R, L)
@functools.cache
def C_analytic(L, R):
return binomial_sym_sympy(L, R) * P_analytic(L) * P_analytic(R)
@functools.cache
def P_analytic(n):
_zero, _one, _x = sympy.core.numbers.Zero(), sympy.core.numbers.One(), sympy.symbols("x")
if n == 0: return _one
# provide analytic expressions for the functions to integrate and the bounds of them
int_bounds = [_zero, *[1/(1 + C_analytic(L+1, n-L-2)/C_analytic(L, n-L-1)) for L in range(n-1)], _one]
int_polys = [sympy.poly(C_analytic(L, n-1-L) * _x**L * (1-_x)**(n-1-L), _x, domain="Q").integrate() for L in range(n)]
int_summands = [int_poly(R_bound)-int_poly(L_bound) for int_poly, (L_bound, R_bound) in zip(int_polys, rolling(int_bounds, 2))]
return sum(int_summands)
# quickly convert n to (l, r) tuple up to n=999
lrs, row, col = [], 0, 0
for n in range(1000):
lrs.append((row-col, col))
if col == row: row, col = row+1, 0
else: col += 1
def A370450(n): return C_analytic(*lrs[n]).numerator
def A370451(n): return C_analytic(*lrs[n]).denominator
CROSSREFS
KEYWORD
AUTHOR
Philip Geißler, Feb 18 2024
STATUS
approved