cp's OEIS Frontend

A288952 Number of relaxed compacted binary trees of right height at most one with empty sequences between branch nodes on level 0.

%I A288952 #22 Nov 30 2024 21:02:59
%S A288952 1,0,1,2,15,92,835,8322,99169,1325960,19966329,332259290,6070777999,
%T A288952 120694673748,2594992240555,59986047422378,1483663965460545,
%U A288952 39095051587497488,1093394763005554801,32347902448449172530,1009325655965539561231,33125674098690460236620
%N A288952 Number of relaxed compacted binary trees of right height at most one with empty sequences between branch nodes on level 0.
%C A288952 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 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. 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. A branch node is a node with a left and right edge (no pointer). See the Genitrini et al. link. - _Michael Wallner_, Apr 20 2017
%C A288952 a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels a maximal young leaf has to be followed by a non-maximal young leaf. A young leaf is a leaf with no left sibling. A maximal young leaf is a young leaf with maximal label. See the Wallner link. - _Michael Wallner_, Apr 20 2017
%H A288952 Muniru A Asiru, <a href="/A288952/b288952.txt">Table of n, a(n) for n = 0..100</a>
%H A288952 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 A288952 Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">A bijection of plane increasing trees with relaxed binary trees of right height at most one</a>, arXiv:1706.07163 [math.CO], 2017.
%F A288952 E.g.f.: exp( -Sum_{n>=1} Fibonacci(n-1)*x^n/n ), where Fibonacci(n) = A000045(n).
%F A288952 E.g.f.: exp( -1/sqrt(5)*arctanh(sqrt(5)*z/(2-z)) )/sqrt(1-z-z^2).
%F A288952 a(0) = 1, a(1) = 0, a(n) = (n-1)*a(n-1) + (n-1)^2*a(n-2). - _Daniel Suteu_, Jan 25 2018
%e A288952 See A288950 and A288953.
%p A288952 a:=proc(n) option remember: if n=0 then 1 elif n=1 then 0 elif n>=2 then (n-1)*procname(n-1)-(n-1)^2*procname(n-2) fi; end:
%p A288952 seq(a(n),n=0..100); # _Muniru A Asiru_, Jan 26 2018
%t A288952 Fold[Append[#1, (#2 - 1) Last[#1] + #1[[#2 - 1]] (#2 - 1)^2] &, {1, 0}, Range[2, 21]] (* _Michael De Vlieger_, Jan 28 2018 *)
%o A288952 (GAP) a := [1,0];; for n in [3..10^2] do a[n] := (n-2)*a[n-1] + (n-2)^2*a[n-2]; od; a; # _Muniru A Asiru_, Jan 26 2018
%Y A288952 Cf. A001147 (relaxed compacted binary trees of right height at most one).
%Y A288952 Cf. A082161 (relaxed compacted binary trees of unbounded right height).
%Y A288952 Cf. A000032, A000246, A001879, A051577, A177145, A213527, A288950, A288953, A288954 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
%Y A288952 Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).
%K A288952 nonn
%O A288952 0,4
%A A288952 _Michael Wallner_, Jun 20 2017