|
| |
|
|
A002955
|
|
Number of (unordered, unlabeled) rooted trimmed trees with n nodes.
(Formerly M1140)
|
|
21
|
|
|
|
1, 1, 1, 2, 4, 8, 17, 36, 79, 175, 395, 899, 2074, 4818, 11291, 26626, 63184, 150691, 361141, 869057, 2099386, 5088769, 12373721, 30173307, 73771453, 180800699, 444101658, 1093104961, 2695730992, 6659914175, 16481146479, 40849449618
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
A rooted trimmed tree is a tree without limbs of length >= 2. Limbs are the paths from the leafs (towards the root) to the nearest branching point (with the root considered to be a branching point). [clarified by Joerg Arndt, Mar 03 2015]
A rooted tree with a forbidden limb of length k is a rooted tree where the path from any leaf inward hits a branching node or the root within k steps.
Also counts the unordered rooted trees without "x x" in the level sequence for the pre-order walk. The bijection transforms the two outmost nodes in all limbs of lengths >= 2 into V-shaped subtrees. - Joerg Arndt, Mar 03 2015
|
|
|
REFERENCES
|
K. L. McAvaney, personal communication.
A. J. Schwenk, Almost all trees are cospectral, pp. 275-307 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) satisfies a=SHIFT_RIGHT(EULER(a-b)) where b(2)=1, b(k)=0 if k != 2.
a(n) ~ c * d^n / n^(3/2), where d = 2.59952511060090659632378883695107..., c = 0.391083882871301267612387143401... . - Vaclav Kotesovec, Aug 24 2014
|
|
|
MAPLE
|
with(numtheory): a:= proc(n) option remember; local d, j, aa; aa:= n-> a(n)-`if`(n=2, 1, 0); if n<=1 then n else (add(d*aa(d), d=divisors(n-1)) +add(add(d*aa(d), d=divisors(j)) *a(n-j), j=1..n-2))/ (n-1) fi end: seq(a(n), n=1..32); # Alois P. Heinz, Sep 06 2008
|
|
|
MATHEMATICA
|
a[n_] := a[n] = (Total[ #*b[#]& /@ Divisors[n-1] ] + Sum[ Total[ #*b[#]& /@ Divisors[j] ]*a[n-j], {j, 1, n-2}]) / (n-1); a[1] = 1; b[n_] := a[n]; b[2] = 0; Table[ a[n], {n, 1, 32}](* Jean-François Alcover, Nov 18 2011, after Maple *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,eigen
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
