|
|
A254789
|
|
The number of unlabeled binary trees that contain n distinct subtrees, where a subtree means take any node and everything below that node.
|
|
3
|
|
|
1, 1, 3, 15, 111, 1119, 14487, 230943, 4395855, 97608831, 2482988079, 71321533887, 2286179073663, 80984105660415, 3144251526824991, 132867034410319359, 6073991827274809407, 298815244349875677183, 15746949613850439270975, 885279424331353488224511, 52902213099156326247243519
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is also the number of compacted binary trees of size n. A compacted binary tree is a directed acyclic graph computed by the UID procedure (see Flajolet et al.) from a given full binary tree. Every edge leading to a subtree that has already been seen during the traversal is replaced by a new kind of edge, a pointer, to the already existing subtree. The size of the compacted binary tree is defined by the number of its internal nodes. See Genitrini et al. - Michael Wallner, Apr 21 2017
|
|
LINKS
|
Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert, Analytic variations on the common subexpression problem, in Automata, Languages and Programming (Coventry, 1990), volume 443 of Lecture Notes in Comput. Sci., pages 220-234. Springer, New York, 1990.
|
|
FORMULA
|
a(n) := b(n,0) where b(0,p) := p+1, b(1,p) := p^2+p+1 and b(n+1,p) = sum(b(i,p)*b(n-i,p+i), i=0..n) for n>=2, see Genitrini et al. - Michael Wallner, Apr 21 2017
a(n) = c(n,n) where c(n,m)=(m+1)*c(n-1,m)+c(n,m-1)-(m-1)*c(n-2,m-1) for n>=m>=1, c(n,m)=0 for n<m, and c(n,0)=1 for n>=0. - Michael Wallner, Jan 31 2022
a(n) = Theta(n! 4^n exp(3*a1*n^(1/3)) n^(3/4)) for large n, where a1 = -2.338... = A096714 is the largest root of the Airy function Ai(x) of the first kind; see [Elvey Price, Fang, Wallner 2021]. - Michael Wallner, Jan 31 2022
|
|
EXAMPLE
|
Consider n = 2. For two different subtrees there are (i) the left path on two nodes, (ii) the right path on two nodes, and (iii) the complete tree on three nodes, giving three trees total.
a(3) = 15, as follows:
** First type:
4 paths on 3 nodes:
o
/
o
/
o
** Second type:
complete tree on three nodes with a singleton attached, 4 trees on 4 nodes:
o
/ \
o o
/
o
** Third type:
complete tree on three nodes attached to a singleton at the root, 2 trees on 4 nodes
o
/
o
/ \
o o
** Fourth type:
complete tree on three nodes with two singletons attached in parallel, 2 trees on 5 nodes
o
/ \
o o
/ /
o o
** Fifth type:
complete tree on three nodes with two singletons attached to the same terminal, 2 trees on 5 nodes
o
/ \
o o
/ \
o o
** Sixth type:
complete tree on seven nodes
o
/ \
o o
/ \ |\
o o o o
Total is 4+4+2+2+2+1 = 15.
|
|
MATHEMATICA
|
b[n_ /; n >= 2, p_] := b[n, p] = Sum[b[i, p] b[n-i-1, p+i], {i, 0, n-1}];
b[0, p_] := p + 1;
b[1, p_] := p^2 + p + 1;
a[n_] := b[n, 0];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(9)-a(15) computed by Johannes Waldmann
|
|
STATUS
|
approved
|
|
|
|