A002955 - OEIS

%I M1140 #52 Oct 27 2023 21:06:51

%S 1,1,1,2,4,8,17,36,79,175,395,899,2074,4818,11291,26626,63184,150691,

%T 361141,869057,2099386,5088769,12373721,30173307,73771453,180800699,

%U 444101658,1093104961,2695730992,6659914175,16481146479,40849449618

%N Number of (unordered, unlabeled) rooted trimmed trees with n nodes.

%C 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]

%C 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.

%C 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

%D K. L. McAvaney, personal communication.

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A002955/b002955.txt">Table of n, a(n) for n = 1..1000</a> (terms n = 1..300 from Vincenzo Librandi)

%H F. Goebel and R. P. Nederpelt, <a href="http://www.jstor.org/stable/2316312">The number of numerical outcomes of iterated powers</a>, Amer. Math. Monthly, 80 (1971), 1097-1103.

%H R. K. Guy and J. L. Selfridge, <a href="http://www.jstor.org/stable/2319392">The nesting and roosting habits of the laddered parenthesis</a>, Amer. Math. Monthly 80 (8) (1973), 868-876.

%H R. K. Guy and J. L. Selfridge, <a href="/A003018/a003018.pdf">The nesting and roosting habits of the laddered parenthesis</a> (annotated cached copy)

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F a(n) satisfies a=SHIFT_RIGHT(EULER(a-b)) where b(2)=1, b(k)=0 if k != 2.

%F a(n) ~ c * d^n / n^(3/2), where d = 2.59952511060090659632378883695107..., c = 0.391083882871301267612387143401... . - _Vaclav Kotesovec_, Aug 24 2014

%p 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

%t 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 *)

%Y Cf. A002988-A002992, A052318-A052329.

%Y Column k=2 of A255636.

%K nonn,nice,eigen

%O 1,4

%A _N. J. A. Sloane_

%E More terms, formula and comments from _Christian G. Bower_, Dec 15 1999