OFFSET
1,5
COMMENTS
Let P_(m,n) denote a grid with 2 rows that has m points in the top row and n points in the bottom, aligned at the left, and let the bottom left point be at the origin.
For m > n, the number of bimonotone subdivisions of P_(m,n) is given by B(m,n) = 2^(m-2)/(n-1)!*P_n(m), where P_n(m) is some monic polynomial with degree n - 1. See Theorem 1, p. 5, in Robeva and Sun (2020). (The authors' notation P_(m,n) for the grid should not be confused with their notation P_n(m) for the monic polynomial of degree n - 1 whose coefficients we tabulate here.)
We are not concerned here with the case m <= n. For more details, see A192933.
LINKS
Elina Robeva and Melinda Sun, Bimonotone Subdivisions of Point Configurations in the Plane, arXiv:2007.00877 [math.CO], 2020. See Table 1, p. 5.
Wikipedia, Faulhaber's formula.
FORMULA
B(m,n) = (2^(m-2)/(n-1)!) * Sum_{k=1..n} T(n,k)*m^(n-k).
B(m,n) = (2^(m-2)/(n-1)!) * P_n(m) = A192933(m,n).
B(m,n) = (2^(m-2)/(n-2)!) * (P_(n-1)(m) + S(m, n-2) - S(n-1, n-2) + Sum_{i=0..n-3} a_{i,n}*(S(m,i) - S(n-1,i))), where P_{n-1}(m) = m^(n-2) + Sum_{i=0..n-3} a_{i,n}*m^i and S(m,k) = Sum_{s=1..m} s^k. (Thus, a_{i,n} = T(n-1, n-1-i), and this formula is used in the PARI program below.)
B(m,n) = 2*(B(m,n-1) + B(m-1,n) - B(m-1,n-1)) for m > n.
EXAMPLE
Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins:
1;
1, 0;
1, 3, -6;
1, 9, -4, -60;
1, 18, 47, -258, -600;
1, 30, 215, -270, -4896, -6720;
...
P_3(m) = m^2 + 3*m - 6.
PROG
(PARI) polf(n) = if (n==0, return(m)); my(p=bernpol(n+1, m)); (subst(p, m, m+1) - subst(p, m, 0))/(n+1); \\ Faulhaber
tabl(nn) = {my(p = 1, q); for (n=1, nn, if (n==1, q = p, q = (n-1)*(p + polf(n-2) - subst(polf(n-2), m, n-1) + sum(i=0, n-3, polcoef(p, i, m)*(polf(i)-subst(polf(i), m, n-1))))); print(Vec(q)); p = q; ); }
CROSSREFS
KEYWORD
sign,tabl
AUTHOR
Michel Marcus and Petros Hadjicostas, Jul 14 2020
STATUS
approved