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

%I #32 Mar 23 2020 17:31:49

%S 1,3,1,10,9,1,42,67,18,1,248,510,235,30,1,1992,4378,2835,605,45,1,

%T 19600,44268,34888,10605,1295,63,1,222288,524748,461748,178913,31080,

%U 2450,84,1,2851712,7103088,6728428,3069612,690753,77112,4242,108,1

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

%C DEFINITION

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

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

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

%C The first few polynomials are

%C M(1,x) = x

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

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

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

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

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

%C RELATION TO MINIMAX TREES

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

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

%C ANALOGIES WITH THE MONOMIALS

%C {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:

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

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

%C The Bell transform of A143523(n). For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 18 2016

%F GENERATING FUNCTION

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

%F (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! + ....

%F ROW POLYNOMIALS

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

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

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

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

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

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

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

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

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

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

%F ANALOG OF THE LITTLE FERMAT THEOREM

%F For integer x and odd prime p

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

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

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

%F GENERALIZED BERNOULLI POLYNOMIALS ASSOCIATED WITH THE MINIMAX POLYNOMIALS

%F 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]:

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

%F The first few generalized Bernoulli polynomials are

%F MB(0,x) = 1,

%F MB(1,x) = x - 2,

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

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

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

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

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

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

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

%F 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*.

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

%F (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.

%F RELATION WITH OTHER SEQUENCES

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

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

%e Triangle begins

%e n\k|.....1......2......3......4......5......6......7

%e ====================================================

%e ..1|.....1

%e ..2|.....3......1

%e ..3|....10......9......1

%e ..4|....42.....67.....18......1

%e ..5|...248....510....235.....30......1

%e ..6|..1992...4378...2835....605.....45......1

%e ..7|.19600..44268..34888..10605...1295.....63......1

%e ..

%e Example of the generalized Bernoulli summation formula:

%e The second row of the triangle gives x^[2] = 3*x+x^2.

%e Then 1^[2]+2^[2]+...+(n-1)^[2] = (n^3+3*n^2-4*n)/3 = 1/3*(MB(3,n)-MB(3,0)).

%e From _R. J. Mathar_, Mar 15 2013: (Start)

%e The matrix inverse starts

%e 1;

%e -3, 1;

%e 17, -9, 1;

%e -147, 95, -18, 1;

%e 1697, -1245, 305, -30, 1;

%e -24483, 19687, -5670, 745, -45, 1;

%e 423857, -365757, 118237, -18690, 1540, -63, 1;

%e -8560947, 7819287, -2761122, 498197, -50190, 2842, -84, 1; (End)

%p #A185419

%p M := proc(n,x) option remember;

%p if n = 0 then

%p return 1

%p else return

%p x*(2*M(n-1,x+1)-M(n-1,x-1))

%p end if;

%p end proc:

%p with(PolynomialTools):

%p for n from 1 to 10 do

%p CoefficientList(M(n,x),x);

%p end do;

%t M[0, _] = 1; M[n_, x_] := M[n, x] = x (2 M[n-1, x+1] - M[n-1, x-1]);

%t Table[CoefficientList[M[n, x], x] // Rest, {n, 1, 10}] (* _Jean-François Alcover_, Jun 26 2019 *)

%o (Sage) # uses[bell_matrix from A264428]

%o # Adds a column 1,0,0,0, ... at the left side of the triangle.

%o bell_matrix(lambda n: A143523(n), 10) # _Peter Luschny_, Jan 18 2016

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

%K nonn,easy,tabl

%O 1,2

%A _Peter Bala_, Feb 07 2011