

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 postorder 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 postorder 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 rightedges (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(n1) + (n1)*a(n2), 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)+z2)/(1z)^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+z2)/(1z)^2 + O[z]^terms, z] Range[0, terms1]! (* JeanFranç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) + x2)/(1x)^2 )); [Factorial(n1)*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



