login
Number of relaxed compacted binary trees of right height at most one with empty initial and final sequence on level 0.
6

%I #13 Dec 04 2018 08:42:30

%S 1,0,1,2,15,140,1575,20790,315315,5405400,103378275,2182430250,

%T 50414138775,1264936572900,34258698849375,996137551158750,

%U 30951416768146875,1023460181133390000,35885072600989486875,1329858572860198631250,51938365373373313209375

%N Number of relaxed compacted binary trees of right height at most one with empty initial and final sequence 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. The number of unbounded relaxed compacted binary trees of size n is A082161(n). The number of relaxed compacted binary trees of right height at most one of size n is A001147(n). See the Genitrini et al. and Wallner link. - _Michael Wallner_, Apr 20 2017

%C a(n) is the number of plane increasing trees with n+1 nodes where node 3 is at depth 1 on the right of node 2 and where the node n+1 has a left sibling. 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.: z + (1-z)/3*(2-z+(1-2*z)^(-1/2)).

%e Denote by L the leaf and by o nodes. Every node has exactly two out-going edges or pointers. Internal edges are denoted by - or |. Pointers are omitted and may point to any node further right. The root is at level 0 at the very left.

%e The general structure is

%e L-o-o-o-o-o-o-o-o-o

%e | | | |

%e o o-o-o o-o o.

%e For n=0 the a(0)=1 solution is L.

%e For n=1 we have a(1)=0 because we need nodes on level 0 and level 1.

%e For n=2 the a(2)=1 solution is

%e L-o

%e |

%e o

%e and the pointers of the node on level 1 both point to the leaf.

%e For n=3 the a(3)=2 solutions have the structure

%e L-o

%e |

%e o-o

%e where the pointers of the last node have to point to the leaf, but the pointer of the next node has 2 choices: the leaf of the previous node.

%t terms = 21; (z + (1 - z)/3*(2 - z + (1 - 2z)^(-1/2)) + O[z]^terms // CoefficientList[#, z] &) Range[0, terms-1]! (* _Jean-François Alcover_, Dec 04 2018 *)

%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, A177145, A213527, A288950, A288952, A288953, A288954 (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 0,4

%A _Michael Wallner_, Jun 20 2017