cp's OEIS Frontend

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.

%I A316666 #32 Apr 25 2025 16:00:19
%S A316666 1,0,1,3,15,87,597,4701,41787,413691,4512993,53779833,695000919,
%T A316666 9680369943,144560191149,2303928046437,39031251610227,700394126116851,
%U A316666 13270625547477177,264748979672169681,5547121478845459983,121784530649198053263,2795749225338111831429,66981491857058929294653
%N 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.
%C A316666 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 A316666 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 A316666 G. C. Greubel, <a href="/A316666/b316666.txt">Table of n, a(n) for n = 0..448</a>
%H A316666 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 A316666 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 A316666 E.g.f.: (3*exp(-z)+z-2)/(1-z)^2.
%F A316666 a(n) ~ (3*exp(-1) - 1) * n * n!. - _Vaclav Kotesovec_, Jul 12 2018
%F A316666 a(n) = 3*round((n+2)*n!/e) - (n+2)*n!. - _Gary Detlefs_, Dec 11 2018
%F A316666 From _Seiichi Manyama_, Apr 25 2025: (Start)
%F A316666 a(n) = 3 * A000255(n) - n! - (n+1)!.
%F A316666 a(0) = 1, a(1) = 0; a(n) = n*a(n-1) + (n-1)*a(n-2). (End)
%p A316666 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 A316666 terms = 24;
%t A316666 CoefficientList[(3E^-z+z-2)/(1-z)^2 + O[z]^terms, z] Range[0, terms-1]! (* _Jean-François Alcover_, Sep 14 2018 *)
%o A316666 (PARI) Vec(serlaplace((3*exp(-x + O(x^25)) + x - 2)/(1 - x)^2)) \\ _Andrew Howroyd_, Jul 10 2018
%o A316666 (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 A316666 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 A316666 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 A316666 Cf. A000255, A096654.
%K A316666 nonn
%O A316666 0,4
%A A316666 _Michael Wallner_, Jul 10 2018