A185420 -id:A185420 - cp's OEIS frontend

A080795 Number of minimax trees on n nodes.

1, 1, 4, 20, 128, 1024, 9856, 110720, 1421312, 20525056, 329334784, 5812797440, 111923560448, 2334639652864, 52444850814976, 1262260748288000, 32405895451246592, 883950436237705216, 25530268718794276864

Offset: 0

Emanuele Munarini, Mar 14 2003

A minimax tree is (i) rooted, (ii) binary (i.e., each node has at most two sons), (iii) topological (i.e., the left son is different from the right son), (iv) labeled (i.e., there is a bijection between the nodes and a finite totally ordered set). Moreover it has the following property: (v) the label of each node x is the minimum or the maximum of all the labels of the nodes of the subtree whose root is x.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA]
Dominique Foata & Guo-Niu Han, Arbres minimax et polynomes d'André , Advances in Appl. Math., 27, 2001, p. 367-389.
Dominique Foata and Guo-Niu Han, Arbres minimax et polynomes d'André. Special issue in honor of Dominique Foata's 65th birthday (Philadelphia, PA, 2000). Adv. in Appl. Math. 27 (2001), no. 2-3, 367-389.
E. Norton, Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions, arXiv preprint arXiv:1302.5411, 2013

Cf. A185419, A185420. A008292, A185896.

w := (sqrt(2) - 1)/2:
seq(simplify((2*sqrt(2))^(n-1)*add(k!*Stirling2(n, k)*w^(k-1), k = 1..n)), n = 1..20); # Peter Bala, Oct 31 2024

Range[0, 18]! CoefficientList[ Series[ Tanh[ ArcTanh[ Sqrt[2]] - Sqrt[2] x]/Sqrt[2], {x, 0, 18}], x] (* Robert G. Wilson v *)

{Stirling2(n,k)=(1/k!)*sum(j=0,k,(-1)^j*binomial(k,j)*(k-j)^n)}
/* Finite sum given by Peter Bala: */
{a(n)=local(w=(sqrt(2)-1)/2);if(n==0,1,round((2*sqrt(2))^(n-1)*sum(k=1,n,k!*Stirling2(n,k)*w^(k-1))))}

E.g.f.: ( tanh(arctanh(sqrt(2)) - sqrt(2)*x) )/sqrt(2) = sqrt(2)/2* (1 + (3-2*sqrt(2))* exp(2*sqrt(2)*x) )/( 1 - (3-2*sqrt(2))* exp(2*sqrt(2)*x) ).
Recurrence: a(n+1) = 2*(Sum_{k=0..n} binomial(n,k)*a(k)*a(n-k)) - 0^n.
a(2*n) = 2^n * A006154(2*n), n>0 (conjectured). - Ralf Stephan, Apr 29 2004
For n>0, a(n) = sqrt(2)^(3*n+1)*Sum_{k>=0} k^n/(1+sqrt(2))^(2*k). - Benoit Cloitre, Jan 12 2005
From Peter Bala, Jan 30 2011: (Start)
A finite sum equivalent to the previous formula of Benoit Cloitre is
a(n) = (2*sqrt(2))^(n-1)*Sum_{k = 1..n} k!*Stirling2(n,k)*w^(k-1), for n >= 1, with w = (sqrt(2) - 1)/2.
This formula can be used to prove congruences for a(n). For example, a(p) == (-1)^((p^2-1)/8) (mod p) for odd prime p.
For similar formulas for labeled plane and non-plane unary-binary trees see A080635 and A000111 respectively.
For a sequence of related polynomials see A185419. For a recursive table to calculate a(n) see A185420.
The e.g.f. A(x) satisfies the autonomous differential equation d/dx (A(x)) = 2*A(x)^2 - 1. (End)
From Peter Bala, Aug 26 2011: (Start)
The inverse function A(x)^(-1) of the generating function A(x) satisfies A(x)^(-1) = Integral_{t = 1..x} 1/(2*t^2 - 1) dt.
Let f(x) = 2*x^2 - 1. Define the nested derivative D^n[f](x) by means of the recursion D^0[f](x) = 1 and D^(n+1)[f](x) = d/dx(f(x)*D^n[f](x)) for n >= 0 (see A145271 for the coefficients in the expansion of D^n[f](x) in powers of f(x)). Then by [Dominici, Theorem 4.1] we have a(n+1) = D^n[f](1).
For n >= 1 we have a(n) = (2 + sqrt(2))^(n-1)*A(n, 3 - 2*sqrt(2)), where {A(n, x)}n>=1 = [1, 1 + x, 1 + 4*x + x^2, 1 + 11*x + 11*x^2 + x^3, ...] denotes the sequence of Eulerian polynomials (see A008292).
a(n+1) = (-1)^n*(sqrt(-2))^n * R(n, sqrt(-2)) where R(n, x) are the polynomials defined in A185896 (derivative polynomials associated with the function sec^2(x)). (End)
G.f.: 1 + x/G(0) where G(k) =  1 - 4*x*(k+1) - 2*x^2*(k+1)*(k+2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Jan 11 2013
G.f.: 1 + x/(G(0) -x), where G(k) = 1 - x*(k+1) - 2*x*(k+1)/(1 - x*(k+2)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
E.g.f.: sqrt(2)*( -1/2 + (3+2*sqrt(2))/(4 + 2*sqrt(2)- E(0) )), where E(k) = 2 + 2*sqrt(2)*x/( 2*k+1 - 2*sqrt(2)*x/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 27 2013
a(n) ~ n! * 2^((3*n+1)/2) / (log(3+2*sqrt(2)))^(n+1). - Vaclav Kotesovec, Feb 25 2014

A185414 Square array, read by antidiagonals, used to recursively calculate the zigzag numbers A000111.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 5, 3, 1, 16, 16, 10, 4, 1, 61, 61, 39, 17, 5, 1, 272, 272, 176, 80, 26, 6, 1, 1385, 1385, 903, 421, 145, 37, 7, 1, 7936, 7936, 5200, 2464, 880, 240, 50, 8, 1, 50521, 50521, 33219, 15917, 5825, 1661, 371, 65, 9, 1

Offset: 1

Peter Bala, Jan 26 2011

The table entries T(n,k), for n,k>=1, are defined by means of the recurrence relation (1)... T(n+1,k) = 1/2*{(k-1)*T(n,k-1)+(k+1)*T(n,k+1)}, with boundary condition T(1,k) = 1.
The first column of the table produces the sequence of zigzag numbers A000111. Cf. A185416, A185418 and A185420.
Diagonal T(n,n+1) = A290579(n) for n>=1. - Paul D. Hanna, Aug 07 2017

			The array begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...;
2, 5, 10, 17, 26, 37, 50, 65, 82, ...;
5, 16, 39, 80, 145, 240, 371, 544, 765, ...;
16, 61, 176, 421, 880, 1661, 2896, 4741, 7376, ...;
61, 272, 903, 2464, 5825, 12336, 23947, 43328, 73989, ...;
272, 1385, 5200, 15917, 41936, 98377, 210320, 416765, ...;
1385, 7936, 33219, 112640, 326965, 840960, 1962191, ...; ...
Examples of the recurrence:
T(4,4) = 80 = (3*T(3,3) + 5*T(3,5))/2 = (3*10 + 5*26)/2;
T(5,3) = 176 = (2*T(4,2) + 4*T(4,4))/2 = (2*16 + 4*80)/2;
T(6,2) = 272 = (1*T(5,1) + 3*T(5,3))/2 = (1*16 + 3*176)/2.

Cf. A000111, A147309, A185416, A185418, A185420, A290579.

#A185414 Z := proc(n,x)
description 'zigzag polynomials A147309'
if n = 0 return 1 else return 1/2*x*(Z(n-1,x-1)+Z(n-1,x+1))
end proc:
# values of Z(n,x)/x
for n from 1 to 10 do seq(Z(n,k)/k, k = 1..10);
end do;

{T(n,k)=if(n==1,1,((k-1)*T(n-1,k-1)+(k+1)*T(n-1,k+1))/2)}
for(n=1,10, for(k=1,10, print1(T(n,k),", ")); print(""))

(1)... T(n,k) = Z(n,k)/k with Z(n,x) the zigzag polynomials described in A147309.

A185416 Square array, read by antidiagonals, used to recursively calculate A080635.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 9, 6, 3, 1, 39, 24, 11, 4, 1, 189, 114, 51, 18, 5, 1, 1107, 648, 279, 96, 27, 6, 1, 7281, 4194, 1767, 594, 165, 38, 7, 1, 54351, 30816, 12699, 4176, 1143, 264, 51, 8, 1, 448821, 251586, 101979, 32922, 8865, 2034, 399, 66, 9, 1

Offset: 1

Peter Bala, Jan 28 2011

The table entries T(n,k), n,k>=1, are defined by the recurrence relation
1)... T(n+1,k) = (k-1)*T(n,k-1)-k*T(n,k)+(k+1)*T(n,k+1) with boundary condition T(1,k)=1.
The first column of the table is A080635.
For similar tables to calculate the zigzag numbers, the Springer numbers and the number of minimax trees see A185414, A185418 and A185420, respectively.

			Triangle begins
n\k|....1......2......3......4......5.......6.......7
=====================================================
..1|....1......1......1......1......1.......1.......1
..2|....1......2......3......4......5.......6.......7
..3|....3......6.....11.....18.....27......38......51
..4|....9.....24.....51.....96....165.....264.....399
..5|...39....114....279....594...1143....2034....3399
..6|..189....648...1767...4176...8865...17304...31563
..7|.1107...4194..12699..32922..76203..161442..318339
..
Examples of the recurrence:
T(4,4) = 96 = 3*T(3,3)-4*T(3,4)+5*T(3,5) = 3*11-4*18+ 5*27;
T(5,1) = 39 = 0*T(4,0)-1*T(4,1)+2*T(4,2) = -1*9+2*24;

Cf. A080635, A185414, A185415, A185418, A185420.

#A185416
P := proc(n,x) description 'polynomial sequence P(n,x) A185415'
if n = 0 return 1
else return
x*(P(n-1,x-1)-P(n-1,x)+P(n-1,x+1))
end proc:
for n from 1 to 10 do
seq(P(n,k)/k,k = 1..10);
end do;

{T(n, k)=if(n==1, 1, (k-1)*T(n-1, k-1)-k*T(n-1,k)+(k+1)*T(n-1, k+1))}

(1)... T(n,k) = P(n,k)/k, where P(n,x) are the polynomials defined in A185415.

A185418 Square array, read by antidiagonals, used to recursively calculate the Springer numbers A001586.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 11, 11, 5, 1, 57, 57, 27, 7, 1, 361, 361, 175, 51, 9, 1, 2763, 2763, 1353, 413, 83, 11, 1, 24611, 24611, 12125, 3801, 819, 123, 13, 1, 250737, 250737, 123987, 39487, 8857, 1441, 171, 15, 1, 2873041, 2873041, 1424215, 458331, 105489, 18057, 2327, 227, 17, 1

Offset: 0

Peter Bala, Jan 30 2011

The table entries T(n,k), n,k>=0, are defined by the recurrence relation:
1)... T(n+1,k) = k*T(n,k-1)+(k+1)*T(n,k+1) with boundary condition T(0,k) = 1.
The first column of the table produces the sequence of Springer numbers A001586.
For similarly defined tables see A185414, A185416 and A185420.

			Square array begins
n\k|.....0......1.......2.......3........4........5........6
============================================================
..0|.....1......1.......1.......1........1........1........1
..1|.....1......3.......5.......7........9.......11.......13
..2|.....3.....11......27......51.......83......123......171
..3|....11.....57.....175.....413......819.....1441.....2327
..4|....57....361....1353....3801.....8857....18057....33321
..5|...361...2763...12125...39487...105489...244211...507013
..6|..2763..24611..123987..458331..1379003..3569523..8229891
..
Examples of recurrence relation:
T(4,3) = 3801 = 3*T(3,2) + 4*T(3,4) = 3*175 + 4*819;
T(5,1) = 2763 = 1*T(4,0)+ 2*T(4,2) = 1*57 + 2*1353.

Cf. A001586, A185417, A185414, A185416, A185420.

# A185418
S := proc(n, x) option remember; description `polynomials S(n, x)`;
if n = 0 then 1 else x*S(n-1,x-1)+(x+1)*S(n-1,x+1) end if end proc:
for n from 0 to 10 do seq(S(n, k), k = 0..10) end do;

T[n_, k_] := T[n, k] = If[n<0 || k<0, 0, If[n == 0, 1, k T[n-1, k-1] + (k+1)*T[n-1, k+1]]];
Table[T[n-k, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 22 2021 *)

{T(n,k)=if(n<0||k<0,0,if(n==0,1,k*T(n-1,k-1)+(k+1)*T(n-1,k+1)))}

(1)... T(n,k) = S(n,k) with S(n,x) the polynomials described in A185417.
(2)... First column: T(n,0) = A001586(n).
(3)... Second column: T(n,1) = A001586(n+1).
(4)... Second row: T(1,k) = A005408(k).
(5)... Third row: T(2,k) = A164897(k).

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

Original entry on oeis.org

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

Peter Bala, Feb 07 2011

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

			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)

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

#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;

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 *)

# 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

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.

cp's OEIS Frontend

A080795 Number of minimax trees on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A185414 Square array, read by antidiagonals, used to recursively calculate the zigzag numbers A000111.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Formula

A185416 Square array, read by antidiagonals, used to recursively calculate A080635.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Formula

A185418 Square array, read by antidiagonals, used to recursively calculate the Springer numbers A001586.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Sage

Formula