|
%I #14 Dec 13 2018 08:07:19
%S 1,1,3,13,79,555,4605,42315,436275,4894155,60125625,794437875,
%T 11325612375,172141044075,2793834368325,48009995908875,
%U 874143494098875,16757439016192875,338309837281040625,7157757510792763875,158706419654857449375,3673441093896736036875
%N Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.
%C A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. A branch node is a node with a left and right edge (no pointer). See the Genitrini et al. link. - _Michael Wallner_, Apr 20 2017
%C a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels a maximal young leaves and non-maximal young leaves alternate except for a sequence of maximal young leaves at the begininning and at the end. A young leaf is a leaf with no left sibling. A maximal young leaf is a young leaf with maximal label. See the Wallner link. - _Michael Wallner_, Apr 20 2017
%H Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">Asymptotic Enumeration of Compacted Binary Trees</a>, arXiv:1703.10031 [math.CO], 2017.
%H Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">A bijection of plane increasing trees with relaxed binary trees of right height at most one</a>, arXiv:1706.07163 [math.CO], 2017.
%F E.g.f.: 1/(3*(1-z))*( 1/sqrt(1-z^2) + (3*z^3-z^2-2*z+2)/((1-z)*(1-z^2)) ).
%e See A288950 and A288953.
%t terms = 22; egf = 1/(3(1-z))(1/Sqrt[1-z^2] + (3z^3 - z^2 - 2z + 2)/((1-z)(1-z^2))) + O[z]^terms;
%t CoefficientList[egf, z] Range[0, terms-1]! (* _Jean-François Alcover_, Dec 13 2018 *)
%Y Cf. A288953 (variation without initial sequence).
%Y Cf. A177145 (variation without initial and final sequence).
%Y Cf. A001147 (relaxed compacted binary trees of right height at most one).
%Y Cf. A082161 (relaxed compacted binary trees of unbounded right height).
%Y Cf. A000032, A000246, A001879, A051577, A213527, A288950, A288952 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
%Y Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).
%K nonn
%O 2,3
%A _Michael Wallner_, Jun 20 2017
| 