0,4

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

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.

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)

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.

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

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.

Sequence in context: A215922 A285449 A371584 * A005415 A371523 A219868

Adjacent sequences: A288947 A288948 A288949 * A288951 A288952 A288953

Michael Wallner, Jun 20 2017

approved