cp's OEIS Frontend

A254789 The number of unlabeled binary trees that contain n distinct subtrees, where a subtree means take any node and everything below that node.

%I A254789 #93 Apr 18 2024 11:21:52
%S A254789 1,1,3,15,111,1119,14487,230943,4395855,97608831,2482988079,
%T A254789 71321533887,2286179073663,80984105660415,3144251526824991,
%U A254789 132867034410319359,6073991827274809407,298815244349875677183,15746949613850439270975,885279424331353488224511,52902213099156326247243519
%N A254789 The number of unlabeled binary trees that contain n distinct subtrees, where a subtree means take any node and everything below that node.
%C A254789 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
%H A254789 Alois P. Heinz, <a href="/A254789/b254789.txt">Table of n, a(n) for n = 0..371</a> (terms n = 1..100 from Andrew Szymczak)
%H A254789 Manosij Ghosh Dastidar and Michael Wallner, <a href="https://arxiv.org/abs/2404.08415">Asymptotics of relaxed k-ary trees</a>, arXiv:2404.08415 [math.CO], 2024. See p. 1.5.
%H A254789 Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert, <a href="http://dx.doi.org/10.1007/BFb0032034">Analytic variations on the common subexpression problem</a>, in Automata, Languages and Programming (Coventry, 1990), volume 443 of Lecture Notes in Comput. Sci., pages 220-234. Springer, New York, 1990.
%H A254789 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 A254789 Project Euler.chat, <a href="https://projecteuler.chat/viewtopic.php?t=3987">Counting Subtrees</a>, (2015).
%H A254789 Marko Riedel, Eric Noeth et al., <a href="http://math.stackexchange.com/questions/1132147/">Distinct subtrees in binary trees</a>, Math StackExchange, February 2015.
%H A254789 Michael Wallner, <a href="http://dmg.tuwien.ac.at/mwallner/files/Dissertation_Wallner.pdf"> Combinatorics of lattice paths and tree-like structures</a> (Dissertation, Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien), 2016.
%H A254789 Christoph Wernhard and Wolfgang Bibel, <a href="https://arxiv.org/abs/2104.13645">Learning from Łukasiewicz and Meredith: Investigations into Proof Structures (Extended Version)</a>, arXiv:2104.13645 [cs.AI], 2021.
%F A254789 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
%F A254789 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
%F A254789 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
%e A254789 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.
%e A254789 a(3) = 15, as follows:
%e A254789 ** First type:
%e A254789 4 paths on 3 nodes:
%e A254789       o
%e A254789      /
%e A254789     o
%e A254789    /
%e A254789   o
%e A254789 ** Second type:
%e A254789 complete tree on three nodes with a singleton attached, 4 trees on 4 nodes:
%e A254789       o
%e A254789      / \
%e A254789     o   o
%e A254789    /
%e A254789   o
%e A254789 ** Third type:
%e A254789 complete tree on three nodes attached to a singleton at the root, 2 trees on 4 nodes
%e A254789       o
%e A254789      /
%e A254789     o
%e A254789    / \
%e A254789   o   o
%e A254789 ** Fourth type:
%e A254789 complete tree on three nodes with two singletons attached in parallel, 2 trees on 5 nodes
%e A254789       o
%e A254789      / \
%e A254789     o   o
%e A254789    /   /
%e A254789   o    o
%e A254789 ** Fifth type:
%e A254789 complete tree on three nodes with two singletons attached to the same terminal, 2 trees on 5 nodes
%e A254789       o
%e A254789      / \
%e A254789     o   o
%e A254789    / \
%e A254789   o   o
%e A254789 ** Sixth type:
%e A254789 complete tree on seven nodes
%e A254789       o
%e A254789      / \
%e A254789     o   o
%e A254789    / \  |\
%e A254789   o   o o o
%e A254789 Total is 4+4+2+2+2+1 = 15.
%t A254789 b[n_ /; n >= 2, p_] := b[n, p] = Sum[b[i, p] b[n-i-1, p+i], {i, 0, n-1}];
%t A254789 b[0, p_] := p + 1;
%t A254789 b[1, p_] := p^2 + p + 1;
%t A254789 a[n_] := b[n, 0];
%t A254789 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jul 29 2018  *)
%Y A254789 Cf. A082161.
%K A254789 nonn
%O A254789 0,3
%A A254789 _Marko Riedel_, Feb 07 2015
%E A254789 a(9)-a(15) computed by Johannes Waldmann
%E A254789 a(16)-a(20) computed by _Andrew Szymczak_, added by _Eric Noeth_, Mar 04 2015