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 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
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
LINKS
Muniru A Asiru, Table of n, a(n) for n = 0..100
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.: exp( -Sum_{n>=1} Fibonacci(n-1)*x^n/n ), where Fibonacci(n) = A000045(n).
E.g.f.: exp( -1/sqrt(5)*arctanh(sqrt(5)*z/(2-z)) )/sqrt(1-z-z^2).
a(0) = 1, a(1) = 0, a(n) = (n-1)*a(n-1) + (n-1)^2*a(n-2). - Daniel Suteu, Jan 25 2018
MAPLE
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:
seq(a(n), n=0..100); # Muniru A Asiru, Jan 26 2018
MATHEMATICA
Fold[Append[#1, (#2 - 1) Last[#1] + #1[[#2 - 1]] (#2 - 1)^2] &, {1, 0}, Range[2, 21]] (* Michael De Vlieger, Jan 28 2018 *)
PROG
(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
CROSSREFS
Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
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).
KEYWORD
nonn
AUTHOR
Michael Wallner, Jun 20 2017
STATUS
approved