login
Number of semi-increasing binary plane trees with n vertices.
8

%I #45 Apr 26 2021 12:18:43

%S 1,4,26,232,2624,35888,575280,10569984,218911872,5044346112,

%T 127980834816,3544627393536,106408500206592,3441351475359744,

%U 119279906031888384,4410902376303722496,173335758665503997952,7213199863532804702208,316878056718379090771968

%N Number of semi-increasing binary plane trees with n vertices.

%C a(n) is the number of semi-increasing plane binary trees with n vertices, which are labeled binary plane trees where each vertex with two children has a label less than the label of each of its descendants.

%H Brad R. Jones, <a href="/A227917/b227917.txt">Table of n, a(n) for n = 1..100</a>

%H B. R. Jones, <a href="http://summit.sfu.ca/item/14554">On tree hook length formulas, Feynman rules and B-series</a>, Master's thesis, Simon Fraser University, 2014.

%F E.g.f.: 2/(2+log(1-2*x))-1.

%F E.g.f. A(x) satisfies the differential equation A'(x) = (1+2*A(x)+A(x)^2)/(1-2*x).

%F a(n) ~ n! * 2^(n+1)*exp(2*n)/(exp(2)-1)^(n+1). - _Vaclav Kotesovec_, Oct 30 2013

%F a(n) = Sum_{k=1..n} |Stirling1(n,k)| * k! * 2^(n-k). - _Ilya Gutkovskiy_, Apr 26 2021

%e Examples of some semi-increasing binary plane trees of 4 vertices:

%e ----------

%e 1

%e / \

%e 4 2

%e /

%e 3

%e ----------

%e 1

%e / \

%e 3 2

%e /

%e 4

%e ----------

%e 3

%e /

%e 1

%e / \

%e 4 2

%e ----------

%e 3

%e /

%e 1

%e \

%e 2

%e \

%e 4

%e ----------

%e 1

%e /

%e 2

%e \

%e 3

%e /

%e 4

%e ----------

%e The following is NOT a semi-increasing binary tree because vertex 2 has two children and has vertex 1 as a descendant.

%e ----------

%e 2

%e / \

%e 3 4

%e /

%e 1

%e ----------

%p seq(coeff(taylor(2/(2+log(1-2*z))-1, z, 51), z^i)*i!, i=1..50);

%t Rest[CoefficientList[Series[2/(2+Log[1-2*x])-1, {x,0,20}], x]*Range[0,20]!] (* _Vaclav Kotesovec_, Oct 30 2013 *)

%K nonn

%O 1,2

%A _Brad R. Jones_, Oct 22 2013