A370450 - OEIS

%I #19 Mar 10 2024 11:44:00

%S 1,1,1,3,2,3,377,9,9,377,1037891564126671,754,27,754,1037891564126671

%N Numerator triangle of PDF coefficients for probability A370448/A370449 read by rows.

%C 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.

%C 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 {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).

%C 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), ...

%C All coefficients {C(n)}(n) are rational.

%H Philip Geißler, <a href="/A370450/b370450.txt">Table of n, a(n) for n = 0..27</a>

%F P(0) = 1

%F P(n+1) = Integral_{x=0..1} max_{L=0..n} C_{L,n-L} x^L (1-x)^{n-L} dx

%F C_{L,R} = (L+R)!/(L!R!) a(L) a(R)

%F where P(n) = A370448(n)/A370449(n)

%F and C(L,R) = A370450(L,R)/A370451(L,R)

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

%e The problem can now be constrained to solving the case of a list with only 2 spaces to fill.

%e For such a list, the success probability is 3/4 = A370448(2)/A370449(2) (see A370448, example section).

%e 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.

%e 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.

%e The coefficient of the PDF is 3/4 = A370450(3)/A370451(3), and the numerator is thus a(3)=3.

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

%e The problem can now be constrained to solving the case of a list with only 1 space to fill twice.

%e For such a list, the success probability is P(1) = 1 = A370448(1)/A370449(1) (see A370448, example section).

%e 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.

%e 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

%e The coefficient of the PDF is 2*1*1 = 2 = 2/1 = A370450(4)/A370451(4), and the numerator is thus a(4)=2.

%e The triangle begins:

%e             1;

%e          1     1;

%e       3     2     3;

%e   377    9     9    377;

%o (Python)

%o import sympy, functools

%o from numpy.lib.stride_tricks import sliding_window_view as rolling

%o binomial_sym_sympy = lambda L, R : sympy.functions.combinatorial.factorials.binomial(L+R, L)

%o @functools.cache

%o def C_analytic(L, R):

%o     return binomial_sym_sympy(L, R) * P_analytic(L) * P_analytic(R)

%o @functools.cache

%o def P_analytic(n):

%o     _zero, _one, _x = sympy.core.numbers.Zero(), sympy.core.numbers.One(), sympy.symbols("x")

%o     if n == 0: return _one

%o     # provide analytic expressions for the functions to integrate and the bounds of them

%o     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]

%o     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)]

%o     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))]

%o     return sum(int_summands)

%o # quickly convert n to (l,r) tuple up to n=999

%o lrs, row, col = [], 0, 0

%o for n in range(1000):

%o     lrs.append((row-col, col))

%o     if col == row: row, col = row+1, 0

%o     else: col += 1

%o def A370450(n): return C_analytic(*lrs[n]).numerator

%o def A370451(n): return C_analytic(*lrs[n]).denominator

%Y Cf. A370451 (denominators).

%Y Cf. A370448, A370449.

%K tabl,frac,nonn

%O 0,4

%A _Philip Geißler_, Feb 18 2024