cp's OEIS Frontend

A080795 Number of minimax trees on n nodes.

%I A080795 #69 Nov 01 2024 02:54:15
%S A080795 1,1,4,20,128,1024,9856,110720,1421312,20525056,329334784,5812797440,
%T A080795 111923560448,2334639652864,52444850814976,1262260748288000,
%U A080795 32405895451246592,883950436237705216,25530268718794276864
%N A080795 Number of minimax trees on n nodes.
%C A080795 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.
%H A080795 Vincenzo Librandi, <a href="/A080795/b080795.txt">Table of n, a(n) for n = 0..200</a>
%H A080795 D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions.</a> arXiv:math/0501052v2 [math.CA]
%H A080795 Dominique Foata & Guo-Niu Han, <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub86minimax.html">Arbres minimax et polynomes d'André </a>, Advances in Appl. Math., 27, 2001, p. 367-389.
%H A080795 Dominique Foata and Guo-Niu Han, <a href="http://dx.doi.org/10.1006/aama.2001.0740">Arbres minimax et polynomes d'André</a>. Special issue in honor of Dominique Foata's 65th birthday (Philadelphia, PA, 2000). Adv. in Appl. Math. 27 (2001), no. 2-3, 367-389.
%H A080795 E. Norton, <a href="http://arxiv.org/abs/1302.5411">Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions</a>, arXiv preprint arXiv:1302.5411, 2013
%F A080795 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) ).
%F A080795 Recurrence: a(n+1) = 2*(Sum_{k=0..n} binomial(n,k)*a(k)*a(n-k)) - 0^n.
%F A080795 a(2*n) = 2^n * A006154(2*n), n>0 (conjectured). - _Ralf Stephan_, Apr 29 2004
%F A080795 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
%F A080795 From _Peter Bala_, Jan 30 2011: (Start)
%F A080795 A finite sum equivalent to the previous formula of _Benoit Cloitre_ is
%F A080795 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.
%F A080795 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.
%F A080795 For similar formulas for labeled plane and non-plane unary-binary trees see A080635 and A000111 respectively.
%F A080795 For a sequence of related polynomials see A185419. For a recursive table to calculate a(n) see A185420.
%F A080795 The e.g.f. A(x) satisfies the autonomous differential equation d/dx (A(x)) = 2*A(x)^2 - 1. (End)
%F A080795 From _Peter Bala_, Aug 26 2011: (Start)
%F A080795 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.
%F A080795 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).
%F A080795 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).
%F A080795 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)
%F A080795 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
%F A080795 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
%F A080795 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
%F A080795 a(n) ~ n! * 2^((3*n+1)/2) / (log(3+2*sqrt(2)))^(n+1). - _Vaclav Kotesovec_, Feb 25 2014
%p A080795 w := (sqrt(2) - 1)/2:
%p A080795 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
%t A080795 Range[0, 18]! CoefficientList[ Series[ Tanh[ ArcTanh[ Sqrt[2]] - Sqrt[2] x]/Sqrt[2], {x, 0, 18}], x] (* _Robert G. Wilson v_ *)
%o A080795 (PARI) {Stirling2(n,k)=(1/k!)*sum(j=0,k,(-1)^j*binomial(k,j)*(k-j)^n)}
%o A080795 /* Finite sum given by _Peter Bala_: */
%o A080795 {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))))}
%Y A080795 Cf. A185419, A185420. A008292, A185896.
%K A080795 nonn,easy
%O A080795 0,3
%A A080795 _Emanuele Munarini_, Mar 14 2003