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

1, 1, 1, 1, 5, 2, 1, 12, 29, 6, 1, 22, 131, 206, 24, 1, 35, 385, 1525, 1774, 120, 1, 51, 895, 6585, 19624, 18204, 720, 1, 70, 1792, 21070, 117019, 281260, 218868, 5040, 1, 92, 3234, 55496, 492849, 2210348, 4483436, 3036144, 40320

Offset: 1

Author

Michel Marcus and Petros Hadjicostas, Jul 14 2020

Keywords

• nonn
• 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 subdivisions of P_(m,n) is given by A(m,n) = 2^(m-2)/(n-1)!*Q_n(m), where Q_n(m) is some monic polynomial of degree n-1. See Theorem 2, p. 6, in Robeva and Sun (2020).

By symmetry, A(m,n) = A(n,m). For more information and formulas, see A059576.

Examples

			Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins
  1;
  1,  1;
  1,  5,   2;
  1, 12,  29,   6;
  1, 22, 131, 206, 24;
  ...
Q_3(m) = m^2 + 5*m + 2.
		

Links

• Elina Robeva and Melinda Sun, Bimonotone Subdivisions of Point Configurations in the Plane, arXiv:2007.00877 [math.CO], 2020. See Table 2, p. 5.
• Wikipedia, Faulhaber's formula.

Crossrefs

Cf. A059576, A103213, A336245.

Programs

Maple

# We assume the rows indexed by the degree of the polynomials, n = 0,1,2,...
A336244row := proc(n) local p, k, s, b; p := 1;
b := n -> bernoulli(n, x+1) - bernoulli(n, 1);
for k from 1 to n-1 do
  s := p + add(coeff(p, x, i-1)*b(i)/i, i=1..k-1);
  p := b(k) + k*s od;
seq(coeff(p, x, n-i), i=1..n) end:
seq(A336244row(n), n=0..9); # Peter Luschny, Jul 15 2020

Mathematica

b[n_] := BernoulliB[n, x + 1] - BernoulliB[n, 1]; b[1] = x;
row[n_] := Module[{p = 1, s}, Do[s = p + Sum[Coefficient[p, x, i-1] b[i]/i, {i, 1, k-1}]; p = b[k] + k s, {k, 1, n-1}]; CoefficientList[p, x] // Reverse];
row /@ Range[9] // Flatten (* Jean-François Alcover, Aug 21 2020, after Peter Luschny *)

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) + sum(i=0, n-3, polcoef(p, i, m)*polf(i)))); print(Vec(q)); p = q;);}

Formula

A(m,n) = (2^(m-2)/(n-1)!) * Sum_{k=1..n} T(n,k)*m^(n-k).

A(m,n) = (2^(m-2)/(n-1)!) * Q_n(m) = A059576(m-1, n-1) (provided the latter is viewed as a square array rather than a triangle).

A(m,n) = (2^(m-2)/(n-2)!) * (Q_(n-1)(m) + Sum_{i=1..m} Q_(n-1)(i)).

A(m,n) = 2*(A(m,n-1) + A(m-1,n) - A(m-1,n-1)) for m > n.

T(n, 1) = 1 and T(n, n) = (n - 1)!.

Conjectures:

(a) T(n,2) = (n - 1)*(3*n - 4)/2.

(b) T(n,3) = (n - 2)*(n - 1)*(27*n^2 - 97*n + 72)/24.

(c) T(n,4) = (n - 3)*(n - 2)*(n - 1)^2*(27*n^2 - 156*n + 208)/48.

(d) T(n, n - 1) = (n - 1)!*Sum_{k=1..n-1} binomial(n-1, k)/k = A103213(n-1).