login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Vincenzo Librandi and Alois P. Heinz, Table of n, a(n) for n = 1..1000 (terms n = 1..300 from Vincenzo Librandi)

F. Goebel and R. P. Nederpelt, The number of numerical outcomes of iterated powers, Amer. Math. Monthly, 80 (1971), 1097-1103.

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.

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.

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

Cf. A002988-A002992, A052318-A052329.

Column k=2 of A255636.

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

EXTENSIONS

More terms, formula and comments from Christian G. Bower, Dec 15 1999

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 15 18:22 EDT 2019. Contains 327082 sequences. (Running on oeis4.)