|
| |
|
|
A080795
|
|
Number of minimax trees on n nodes.
|
|
7
|
|
|
|
1, 1, 4, 20, 128, 1024, 9856, 110720, 1421312, 20525056, 329334784, 5812797440, 111923560448, 2334639652864, 52444850814976, 1262260748288000, 32405895451246592, 883950436237705216, 25530268718794276864
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
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.
|
|
|
FORMULA
|
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.
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
a(n) = (2*sqrt(2))^(n-1)*Sum_{k = 1..n} k!*Stirling2(n,k)*w^(k-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)
The inverse function A(x)^-1 of the generating function A(x) satisfies A(x)^-1 = Integral_{t = 0..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
|
|
|
MATHEMATICA
|
Range[0, 18]! CoefficientList[ Series[ Tanh[ ArcTanh[ Sqrt[2]] - Sqrt[2] x]/Sqrt[2], {x, 0, 18}], x] (* Robert G. Wilson v *)
|
|
|
PROG
|
(PARI) {Stirling2(n, k)=(1/k!)*sum(j=0, k, (-1)^j*binomial(k, j)*(k-j)^n)}
{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))))}
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
