A213674 Number of rooted trees with n nodes, where cycles are allowed instead of subtrees.

0, 1, 1, 3, 6, 13, 29, 71, 176, 454, 1188, 3168, 8542, 23319, 64201, 178249, 498241, 1401344, 3962353, 11257882, 32122442, 92011118, 264474749, 762620137, 2205415254, 6394813039, 18587795338, 54151405093, 158088694125, 462420145673, 1355063144072

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

a(n) ~ c * d^n / n^(3/2), where d = 3.0842695283018951389734653060490863..., c = 0.46707331868314508788370370390913... . - Vaclav Kotesovec, Sep 07 2014

Example

: o : o :   o     o   o :   o     o     o     o     o   o :
:   : | :  / \   / \  | :  / \    |     |    / \   /|\  | :
:   : o : o---o o   o o : o   o   o     o   o   o o o o o :
:   :   :             | :  \ /   / \   / \  |           | :
:   :   :             o :   o   o---o o   o o           o :
:   :   :               :                               | :
:n=1.n=2. n=3           . n=4                           o :
...........................................................

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(a(i)+j-1, j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> b(n-1, n-1) +`if`(n>2, 1, 0):
seq(a(n), n=0..40);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[a[i]+j-1, j]*b[n-i*j, i-1], {j, 0, n/i}]] // FullSimplify] ; a[n_] := b[n-1, n-1] + If[n>2, 1, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

Crossrefs

Cf. A000081, A213682, A213683.

Sequence in context: A018909 A093128 A005313 * A108639 A327795 A087218

Adjacent sequences: A213671 A213672 A213673 * A213675 A213676 A213677

Keyword

nonn

Author

Alois P. Heinz, Mar 03 2013

Status

approved