The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
1, 0, 1, 3, 15, 87, 597, 4701, 41787, 413691, 4512993, 53779833, 695000919, 9680369943, 144560191149, 2303928046437, 39031251610227, 700394126116851, 13270625547477177, 264748979672169681, 5547121478845459983, 121784530649198053263, 2795749225338111831429, 66981491857058929294653 (list; graph; refs; listen; history; text; internal format)



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


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.


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


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


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

(MAGMA) m:=25; R<x>:=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


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.

Sequence in context: A246538 A132371 A192989 * A192253 A127785 A287511

Adjacent sequences:  A316663 A316664 A316665 * A316667 A316668 A316669




Michael Wallner, Jul 10 2018



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 30 09:24 EDT 2020. Contains 334723 sequences. (Running on oeis4.)