OFFSET
0,3
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 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
a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels maximal young leaves and non-maximal young leaves alternate except for a sequence of maximal young leaves at the beginning. 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
LINKS
Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017
FORMULA
E.g.f.: (2-z)/(3*(1-z)^2) + 1/(3*sqrt(1-z^2)).
EXAMPLE
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.
The general structure is
L-o-o-o-o-o-o-o-o
| | | | |
o o o o o.
For n=0 the a(0)=1 solution is L.
For n=1 the a(1)=1 solution is L-o.
For n=2 the a(2)=3 solutions are
L-o-o L-o
|
o
2 + 1 solutions of this shape with pointers.
CROSSREFS
Cf. A288954 (variation with additional initial sequence).
Cf. A177145 (variation without final sequence).
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, A213527, A288950, A288952, A288954 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
KEYWORD
nonn
AUTHOR
Michael Wallner, Jun 20 2017
STATUS
approved