|
| |
|
|
A002955
|
|
Number of rooted trimmed trees with n nodes.
(Formerly M1140)
|
|
19
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| A rooted trimmed tree is a tree with a forbidden limb of length 2.
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.
|
|
|
REFERENCES
| F. Goebel and R. P. Nederpelt, The number of numerical outcomes of iterated powers, Amer. Math. Monthly, 78 (1971), 1097-1103.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.
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
| Vincenzo Librandi, Table of n, a(n) for n = 1..300
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy)
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
|
|
|
FORMULA
| a(n) satisfies a=SHIFT_RIGHT(EULER(a-b)) where b(2)=1, b(k)=0 if k != 2.
|
|
|
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}](* From Jean-François Alcover, Nov 18 2011, after Maple *)
|
|
|
CROSSREFS
| Cf. A002988-A002992, A052318-A052329.
Sequence in context: A182901 A002845 A072925 * A202844 A093951 A137255
Adjacent sequences: A002952 A002953 A002954 * A002956 A002957 A002958
|
|
|
KEYWORD
| nonn,nice,eigen
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms, formula and comments from Christian G. Bower (bowerc(AT)usa.net), Dec 15 1999.
|
| |
|
|
