login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Alois P. Heinz, Table of n, a(n) for n = 0..371 (terms n = 1..100 from Andrew Szymczak)

P. Flajolet, P. Sipala, and J.-M. 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.

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.

Project Euler.chat, Counting Subtrees, (2015).

Marko Riedel, Eric Noeth et al., Distinct subtrees in binary trees, Math StackExchange, February 2015.

Michael Wallner, Combinatorics of lattice paths and tree-like structures (Dissertation, Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien), 2016.

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

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];

Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 29 2018  *)

CROSSREFS

Cf. A082161.

Sequence in context: A109498 A142967 A201339 * A112936 A001063 A130168

Adjacent sequences:  A254786 A254787 A254788 * A254790 A254791 A254792

KEYWORD

nonn

AUTHOR

Marko Riedel, Feb 07 2015

EXTENSIONS

a(9)-a(15) computed by Johannes Waldmann

a(16)-a(20) computed by Andrew Szymczak, added by Eric Noeth, Mar 04 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 24 13:24 EST 2020. Contains 331193 sequences. (Running on oeis4.)