login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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