A316666 Number of simple relaxed compacted binary trees of right height at most one with no sequences on level 1 and no final sequences on level 0.

1, 0, 1, 3, 15, 87, 597, 4701, 41787, 413691, 4512993, 53779833, 695000919, 9680369943, 144560191149, 2303928046437, 39031251610227, 700394126116851, 13270625547477177, 264748979672169681, 5547121478845459983, 121784530649198053263, 2795749225338111831429, 66981491857058929294653

Offset: 0

Author

Michael Wallner, Jul 10 2018

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 at most 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. It is called simple if for nodes with two pointers both point to the same node. 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. See the Wallner link.

a(n) is one of two "basis" sequences for sequences of the form a(0)=a, a(1)=b, a(n) = n*a(n-1) + (n-1)*a(n-2), the second basis sequence being A096654 (with 0 appended as a(0)). The sum of these sequences is listed as A000255. - Gary Detlefs, Dec 11 2018

Links

• G. C. Greubel, Table of n, a(n) for n = 0..448
• 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. A000032, A000246, A001879, A051577, A213527, A288950, A288952, A288953 (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 simple relaxed compacted binary trees of right height at most one, see the Wallner link).

Cf. A000255, A096654.

Programs

Magma

m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (3*Exp(-x) + x-2)/(1-x)^2 )); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Dec 12 2018

Maple

aseq := n-> 3*round((n+2)*n!/exp(1))-(n+2)*n!: bseq := n-> (n+2)*n!- 2* round((n+2)*n!/exp(1)): s := (a,b,n)-> a*aseq(n) + b*bseq( n): seq(s(1,0,n),n = 0..20);  # Gary Detlefs, Dec 11 2018

Mathematica

terms = 24;
CoefficientList[(3E^-z+z-2)/(1-z)^2 + O[z]^terms, z] Range[0, terms-1]! (* Jean-François Alcover, Sep 14 2018 *)

PARI

Vec(serlaplace((3*exp(-x + O(x^25)) + x - 2)/(1 - x)^2)) \\ Andrew Howroyd, Jul 10 2018

Formula

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

a(n) ~ (3*exp(-1) - 1) * n * n!. - Vaclav Kotesovec, Jul 12 2018

a(n) = 3*round((n+2)*n!/e) - (n+2)*n!. - Gary Detlefs, Dec 11 2018

From Seiichi Manyama, Apr 25 2025: (Start)

a(n) = 3 * A000255(n) - n! - (n+1)!.

a(0) = 1, a(1) = 0; a(n) = n*a(n-1) + (n-1)*a(n-2). (End)