

A288950


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


6



1, 0, 1, 2, 15, 140, 1575, 20790, 315315, 5405400, 103378275, 2182430250, 50414138775, 1264936572900, 34258698849375, 996137551158750, 30951416768146875, 1023460181133390000, 35885072600989486875, 1329858572860198631250, 51938365373373313209375
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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 postorder 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 postorder traversal. The right height is the maximal number of rightedges (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
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


LINKS



FORMULA

E.g.f.: z + (1z)/3*(2z+(12*z)^(1/2)).


EXAMPLE

Denote by L the leaf and by o nodes. Every node has exactly two outgoing 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.
The general structure is
Looooooooo
   
o ooo oo o.
For n=0 the a(0)=1 solution is L.
For n=1 we have a(1)=0 because we need nodes on level 0 and level 1.
For n=2 the a(2)=1 solution is
Lo

o
and the pointers of the node on level 1 both point to the leaf.
For n=3 the a(3)=2 solutions have the structure
Lo

oo
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.


MATHEMATICA

terms = 21; (z + (1  z)/3*(2  z + (1  2z)^(1/2)) + O[z]^terms // CoefficientList[#, z] &) Range[0, terms1]! (* JeanFrançois Alcover, Dec 04 2018 *)


CROSSREFS

Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
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).


KEYWORD

nonn


AUTHOR



STATUS

approved



