|
| |
|
|
A185419
|
|
Table of coefficients of a polynomial sequence of binomial type related to the enumeration of minimax trees A080795.
|
|
6
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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 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; - R. J. Mathar, Mar 15 2013
|
|
|
LINKS
|
Table of n, a(n) for n=1..45.
|
|
|
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..inf} 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*ln[(3+2sqrt(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.
|
|
|
EXAMPLE
|
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)).
|
|
|
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;
|
|
|
CROSSREFS
|
A080253 (coeffs. of delta operator), A080795 (row sums), A143523 (column 1), A147309, A185415, A185417, A185420
Sequence in context: A084178 A195812 A144697 * A146154 A068438 A064060
Adjacent sequences: A185416 A185417 A185418 * A185420 A185421 A185422
|
|
|
KEYWORD
|
nonn,easy,tabl
|
|
|
AUTHOR
|
Peter Bala, Feb 07 2011
|
|
|
STATUS
|
approved
|
| |
|
|
