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

 

Logo


Hints
(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)
OFFSET

0,4

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.

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

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

PROG

(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

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.

Sequence in context: A246538 A132371 A192989 * A192253 A127785 A287511

Adjacent sequences:  A316663 A316664 A316665 * A316667 A316668 A316669

KEYWORD

nonn

AUTHOR

Michael Wallner, Jul 10 2018

STATUS

approved

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