cp's OEIS Frontend

A288953 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except after the last branch node on level 0.

%I A288953 #7 Jun 26 2017 01:02:00
%S A288953 1,1,3,10,51,280,1995,15120,138075,1330560,14812875,172972800,
%T A288953 2271359475,31135104000,471038042475,7410154752000,126906349444875,
%U A288953 2252687044608000,43078308695296875,851515702861824000,17984171447178811875,391697223316439040000
%N A288953 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except after the last branch node on level 0.
%C A288953 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 A288953 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
%H A288953 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 A288953 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 A288953 E.g.f.: (2-z)/(3*(1-z)^2) + 1/(3*sqrt(1-z^2)).
%e A288953 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 A288953 The general structure is
%e A288953   L-o-o-o-o-o-o-o-o
%e A288953           | | | | |
%e A288953           o o o o o.
%e A288953 For n=0 the a(0)=1 solution is L.
%e A288953 For n=1 the a(1)=1 solution is L-o.
%e A288953 For n=2 the a(2)=3 solutions are
%e A288953 L-o-o     L-o
%e A288953             |
%e A288953             o
%e A288953   2    +   1    solutions of this shape with pointers.
%Y A288953 Cf. A288954 (variation with additional initial sequence).
%Y A288953 Cf. A177145 (variation without final sequence).
%Y A288953 Cf. A001147 (relaxed compacted binary trees of right height at most one).
%Y A288953 Cf. A082161 (relaxed compacted binary trees of unbounded right height).
%Y A288953 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).
%Y A288953 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 A288953 nonn
%O A288953 0,3
%A A288953 _Michael Wallner_, Jun 20 2017