login
A213682
Number of rooted trees with n nodes having some subtrees replaced by cycles such that no leaf nodes are left over.
3
0, 0, 0, 1, 2, 3, 4, 6, 9, 16, 28, 51, 91, 169, 312, 588, 1113, 2125, 4068, 7844, 15174, 29505, 57553, 112680, 221224, 435637, 859958, 1701775, 3374860, 6706722, 13352832, 26632446, 53205674, 106458153, 213317105, 428021186, 859924107, 1729741358, 3483357290
OFFSET
0,5
LINKS
FORMULA
a(n) ~ c * d^n / n^(3/2), where d = 2.097576205396085315047533452..., c = 0.47373451480298310710830384... . - 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 :
: : : \ / / \ :
: n=3 : n=4 : n=5 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=6 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 o :
: \ / | | / \ | :
: o o---o o o o :
: \ / / \ :
: n=7 o o---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-> `if`(n<3, 0, 1+b(n-1, n-1)):
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_] := If[n<3, 0, 1+b[n-1, n-1]]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 04 2013
STATUS
approved