A185419 Table of coefficients of a polynomial sequence of binomial type related to the enumeration of minimax trees A080795.

1, 3, 1, 10, 9, 1, 42, 67, 18, 1, 248, 510, 235, 30, 1, 1992, 4378, 2835, 605, 45, 1, 19600, 44268, 34888, 10605, 1295, 63, 1, 222288, 524748, 461748, 178913, 31080, 2450, 84, 1, 2851712, 7103088, 6728428, 3069612, 690753, 77112, 4242, 108, 1

Offset: 1

Author

Peter Bala, Feb 07 2011

Keywords

• nonn
• easy
• tabl

Comments

DEFINITION

Define a sequence of polynomials M(n,x) by means of the recurrence relation

(1)... M(n+1,x) = x*{2*M(n,x+1)-M(n,x-1)},

with starting value M(0,x) = 1. We call these the minimax polynomials.

The first few polynomials are

M(1,x) = x

M(2,x) = x*(x + 3)

M(3,x) = x*(x^2 + 9*x + 10)

M(4,x) = x*(x^3 + 18*x^2 + 67*x + 42)

M(5,x) = x*(x^4 + 30*x^3 + 235*x^2 + 510*x + 248).

This triangle lists the coefficients of these polynomials (apart from M(0,x)) in ascending powers of x.

RELATION TO MINIMAX TREES

The value M(n,1) equals the number of minimax trees on n nodes - A080795(n). This result can be used to recursively calculate the entries of A080795 - see A185420.

In addition, the minimax polynomials M(n,x) occur in the formula for the number T(n,k) of forests of k minimax trees on n nodes. ... T(n,k) = 1/k!*sum {j = 0..k} (-1)^(k-j)*binomial(k,j)*M(n,j).

ANALOGIES WITH THE MONOMIALS

{M(n,x)}n>=0 is a polynomial sequence of binomial type and so is analogous to the sequence of monomials x^n. Denoting M(n,x) by x^[n] to emphasize this analogy, we have, for example, the following analog of Bernoulli's formula for the sum of integer powers:

(2)... 1^[p]+...+(n-1)^[p] = -2*n^[p]+ 1/(p+1)*Sum_{k = 0..floor(p/2)} 8^k*binomial(p+1,2k)*B_(2k)*n^[p+1-2k], where {B_k}k>=0 = [1, -1/2, 1/6, 0, -1/30, ...] is the sequence of Bernoulli numbers.

For other polynomial sequences defined by recurrences similar to (1), and related to the zigzag numbers A000111 and the Springer numbers A001586, see A147309 and A185417, respectively. See also A185415.

The Bell transform of A143523(n). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

Examples

			Triangle begins
n\k|.....1......2......3......4......5......6......7
====================================================
..1|.....1
..2|.....3......1
..3|....10......9......1
..4|....42.....67.....18......1
..5|...248....510....235.....30......1
..6|..1992...4378...2835....605.....45......1
..7|.19600..44268..34888..10605...1295.....63......1
..
Example of the generalized Bernoulli summation formula:
The second row of the triangle gives x^[2] = 3*x+x^2.
Then 1^[2]+2^[2]+...+(n-1)^[2] = (n^3+3*n^2-4*n)/3 = 1/3*(MB(3,n)-MB(3,0)).
From _R. J. Mathar_, Mar 15 2013: (Start)
The matrix inverse starts
       1;
      -3,       1;
      17,      -9,        1;
    -147,      95,      -18,      1;
    1697,   -1245,      305,    -30,      1;
  -24483,   19687,    -5670,    745,    -45,    1;
  423857, -365757,   118237, -18690,   1540,  -63,   1;
-8560947, 7819287, -2761122, 498197, -50190, 2842, -84, 1; (End)
		

Crossrefs

Cf. A080253 (coeffs. of delta operator), A080795 (row sums), A143523 (column 1), A147309, A185415, A185417, A185420.

Programs

Maple

#A185419
M := proc(n,x) option remember;
if n = 0 then
return 1
else return
x*(2*M(n-1,x+1)-M(n-1,x-1))
end if;
end proc:
with(PolynomialTools):
for n from 1 to 10 do
CoefficientList(M(n,x),x);
end do;

Mathematica

M[0, ] = 1; M[n, x_] := M[n, x] = x (2 M[n-1, x+1] - M[n-1, x-1]);
Table[CoefficientList[M[n, x], x] // Rest, {n, 1, 10}] (* Jean-François Alcover, Jun 26 2019 *)

Sage

# uses[bell_matrix from A264428]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A143523(n), 10) # Peter Luschny, Jan 18 2016

Formula

GENERATING FUNCTION

Let a = 3-2*sqrt(2). Let f(t) = (1/2)*sqrt(2)*((1+a*exp(2*sqrt(2)*t))/ (1-a*exp(2*sqrt(2)*t))) = 1 + t + 4*t^2/2! + 20*t^3/3! + ... be the e.g.f. for A080795. Then the e.g.f. for the current table, including a constant 1, is

(1)... F(x,t) = f(t)^x = Sum_{n>=0} M(n,x)*t^n/n! = 1 + x*t + (3*x+x^2)*t^2/2! + (10*x+9*x^2+x^3)*t^3/3! + ....

ROW POLYNOMIALS

One easily checks that d/dt(F(x,t)) = x*(2*F(x+1,t)-F(x-1,t)) and hence the row generating polynomials M(n,x) satisfy the recurrence relation

(2)... M(n+1,x) = x*{2*M(n,x+1)-M(n,x-1)}.

The form of the e.g.f shows that the row polynomials are a polynomial sequence of binomial type. The associated delta operator D* is given by

(3)... D* = sqrt(2)/4*log((3+2*sqrt(2))*(sqrt(2)*exp(D)-1)/(sqrt(2)*exp(D)+1)),

where D is the derivative operator d/dx. This expands to

(4)... D* = D - 3*D^2/2! + 17*D^3/3! - 147*D^4/4! + ....

The sequence of coefficients [1,3,17,147,...] is A080253.

The delta operator D* acts as a lowering operator for the minimax polynomials

(5)...(D*) M(n,x) = n*M(n-1,x).

In what follows it will be convenient to denote M(n,x) by x^[n].

ANALOG OF THE LITTLE FERMAT THEOREM

For integer x and odd prime p

(6)... x^[p] = (-1)^((p^2-1)/8)*x (mod p).

More generally, for k = 1,2,...

(7)... x^[p+k-1] = (-1)^((p^2-1)/8)*x^[k] (mod p).

GENERALIZED BERNOULLI POLYNOMIALS ASSOCIATED WITH THE MINIMAX POLYNOMIALS

The generalized Bernoulli polynomial MB(k,x) associated with the minimax polynomial x^[k] (= M(k,x)) may be defined as the result of applying the differential operator D*/(exp(D)-1) to the polynomial x^[k]:

(8)... MB(k,x) := {D*/(exp(D)-1)} x^[k].

The first few generalized Bernoulli polynomials are

MB(0,x) = 1,

MB(1,x) = x - 2,

MB(2,x) = x^2 - x + 4/3,

MB(3,x) = x^3 + 3*x^2 - 4*x,

MB(4,x) = x^4 + 10*x^3 + 3*x^2 - 14*x - 32/15.

Since exp(D)-1 is the forward difference operator it follows from (5) and (8) that

(9)... MB(k,x+1) - MB(k,x) = k*x^[k-1].

Summing (9) from x = 1 to x = n-1 and telescoping we find a closed form expression for the finite sums

(10)... 1^[p]+2^[p]+...+(n-1)^[p] = 1/(p+1)*{MB(p+1,n)-MB(p+1,1)}.

The generalized Bernoulli polynomials can be expanded in terms of the minimax polynomials x^[k]. Use (3) to express exp(D)-1 in terms of D*.

Substitute the resulting expression in (8) and expand as a power series in D* to arrive at the expansion:

(11)... MB(k,x) = -2*k*x^[k-1] + Sum_{j=0..floor(k/2)} 2^(3*j) * binomial(k,2j)*B_(2j)*x^[k-2j], where {B_j}j>=0 = [1,-1/2,1/6,0,-1/30,...] denotes the Bernoulli number sequence.

RELATION WITH OTHER SEQUENCES

Column 1 [1, 3, 10, 42, 248, ...] = A143523 with an offset of 1.

Row sums [1, 1, 4, 20, 128, 1024, ...] = A080795.