A336245 Triangle read by rows: row n gives coefficients T(n,k), in descending powers of m, of a polynomial P_n(m) (of degree n - 1) in an expression for the number of bimonotone subdivisions B(m,n) of a grid with two rows.

1, 1, 0, 1, 3, -6, 1, 9, -4, -60, 1, 18, 47, -258, -600, 1, 30, 215, -270, -4896, -6720, 1, 45, 595, 1455, -16796, -84660, -85680, 1, 63, 1309, 8925, -22526, -470148, -1508424, -1239840, 1, 84, 2506, 30240, 66409, -1500324, -11721396, -28649040, -20200320

Offset: 1

Author

Michel Marcus and Petros Hadjicostas, Jul 14 2020

Keywords

• sign
• tabl

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.

Examples

			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.
		

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.

Crossrefs

Cf. A192933, A336244.

Programs

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;);}

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.