cp's OEIS Frontend

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

%I A288950 #22 Apr 26 2025 09:43:51
%S A288950 1,0,1,2,15,140,1575,20790,315315,5405400,103378275,2182430250,
%T A288950 50414138775,1264936572900,34258698849375,996137551158750,
%U A288950 30951416768146875,1023460181133390000,35885072600989486875,1329858572860198631250,51938365373373313209375
%N A288950 Number of relaxed compacted binary trees of right height at most one with empty initial and final sequence on level 0.
%C A288950 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 A288950 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 A288950 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 A288950 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 A288950 E.g.f.: z + (1-z)/3 * (2-z + (1-2*z)^(-1/2)).
%F A288950 From _Seiichi Manyama_, Apr 26 2025: (Start)
%F A288950 a(n) = (n-1)*(2*n-3)/(n-2) * a(n-1) for n > 3.
%F A288950 a(n) = A001879(n-2)/3 for n > 2. (End)
%e A288950 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 A288950 The general structure is
%e A288950   L-o-o-o-o-o-o-o-o-o
%e A288950     |       |     | |
%e A288950     o   o-o-o   o-o o.
%e A288950 For n=0 the a(0)=1 solution is L.
%e A288950 For n=1 we have a(1)=0 because we need nodes on level 0 and level 1.
%e A288950 For n=2 the a(2)=1 solution is
%e A288950      L-o
%e A288950        |
%e A288950        o
%e A288950 and the pointers of the node on level 1 both point to the leaf.
%e A288950 For n=3 the a(3)=2 solutions have the structure
%e A288950      L-o
%e A288950        |
%e A288950      o-o
%e A288950 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 A288950 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 A288950 Cf. A001147 (relaxed compacted binary trees of right height at most one).
%Y A288950 Cf. A082161 (relaxed compacted binary trees of unbounded right height).
%Y A288950 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 A288950 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).
%Y A288950 Cf. A001879.
%K A288950 nonn
%O A288950 0,4
%A A288950 _Michael Wallner_, Jun 20 2017