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

1, 0, 1, 2, 15, 140, 1575, 20790, 315315, 5405400, 103378275, 2182430250, 50414138775, 1264936572900, 34258698849375, 996137551158750, 30951416768146875, 1023460181133390000, 35885072600989486875, 1329858572860198631250, 51938365373373313209375

Offset: 0

Author

Michael Wallner, Jun 20 2017

Keywords

• nonn

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

Examples

			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   o-o 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
     L-o
       |
       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
     L-o
       |
     o-o
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.
		

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.

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

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

Cf. A001879.

Programs

Mathematica

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 *)

Formula

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

From Seiichi Manyama, Apr 26 2025: (Start)

a(n) = (n-1)*(2*n-3)/(n-2) * a(n-1) for n > 3.

a(n) = A001879(n-2)/3 for n > 2. (End)