login
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

%I #28 Sep 08 2022 08:46:22

%S 1,0,1,3,15,87,597,4701,41787,413691,4512993,53779833,695000919,

%T 9680369943,144560191149,2303928046437,39031251610227,700394126116851,

%U 13270625547477177,264748979672169681,5547121478845459983,121784530649198053263,2795749225338111831429,66981491857058929294653

%N 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.

%C 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.

%C 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

%H G. C. Greubel, <a href="/A316666/b316666.txt">Table of n, a(n) for n = 0..448</a>

%H Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">Asymptotic Enumeration of Compacted Binary Trees</a>, arXiv:1703.10031 [math.CO], 2017.

%H Michael Wallner, <a href="https://arxiv.org/abs/1706.07163">A bijection of plane increasing trees with relaxed binary trees of right height at most one</a>, arXiv:1706.07163 [math.CO], 2017.

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

%F a(n) ~ (3*exp(-1) - 1) * n * n!. - _Vaclav Kotesovec_, Jul 12 2018

%F a(n) = 3*round((n+2)*n!/e) - (n+2)*n!. - _Gary Detlefs_, Dec 11 2018

%p 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

%t terms = 24;

%t CoefficientList[(3E^-z+z-2)/(1-z)^2 + O[z]^terms, z] Range[0, terms-1]! (* _Jean-François Alcover_, Sep 14 2018 *)

%o (PARI) Vec(serlaplace((3*exp(-x + O(x^25)) + x - 2)/(1 - x)^2)) \\ _Andrew Howroyd_, Jul 10 2018

%o (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

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

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

%Y Cf. A000255, A096654.

%K nonn

%O 0,4

%A _Michael Wallner_, Jul 10 2018