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

%I #22 Nov 30 2024 21:02:59

%S 1,0,1,2,15,92,835,8322,99169,1325960,19966329,332259290,6070777999,

%T 120694673748,2594992240555,59986047422378,1483663965460545,

%U 39095051587497488,1093394763005554801,32347902448449172530,1009325655965539561231,33125674098690460236620

%N Number of relaxed compacted binary trees of right height at most one with empty sequences between branch nodes 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 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 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 Muniru A Asiru, <a href="/A288952/b288952.txt">Table of n, a(n) for n = 0..100</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/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 E.g.f.: exp( -Sum_{n>=1} Fibonacci(n-1)*x^n/n ), where Fibonacci(n) = A000045(n).

%F E.g.f.: exp( -1/sqrt(5)*arctanh(sqrt(5)*z/(2-z)) )/sqrt(1-z-z^2).

%F 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 See A288950 and A288953.

%p 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 seq(a(n),n=0..100); # _Muniru A Asiru_, Jan 26 2018

%t 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 (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 Cf. A001147 (relaxed compacted binary trees of right height at most one).

%Y Cf. A082161 (relaxed compacted binary trees of unbounded right height).

%Y 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 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 nonn

%O 0,4

%A _Michael Wallner_, Jun 20 2017