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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005197 a(n) = Sum_t t*F(n,t), where F(n,t) (see A033185) is the number of rooted forests with n (unlabeled) nodes and exactly t rooted trees.
(Formerly M2663)
5
1, 3, 7, 17, 39, 96, 232, 583, 1474, 3797, 9864, 25947, 68738, 183612, 493471, 1334143, 3624800, 9893860, 27113492, 74577187, 205806860, 569678759, 1581243203, 4400193551, 12273287277, 34307646762, 96093291818, 269654004899, 758014312091, 2134300171031 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

REFERENCES

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..600

E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.

FORMULA

To get a(n), take row n of the triangle in A033185, multiply successive terms by 1, 2, 3, ... and sum. E.g. a(4) = 1*4+2*3+3*1+4*1 = 17.

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.955765285..., c = 2.85007275... . - Vaclav Kotesovec, Sep 10 2014

MAPLE

with(numtheory):

t:= proc(n) option remember; local d, j; `if`(n<=1, n,

      (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))

    end:

b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,

      `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j) *

       binomial(t(i)+j-1, j), j=0..min(n/i, p)))))

    end:

a:= a-> add(k*b(n, n, k), k=1..n):

seq(a(n), n=1..40);  # Alois P. Heinz, Aug 20 2012

MATHEMATICA

t[1] = 1; t[n_] := t[n] = Module[{d, j}, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]; b[1, 1, 1] = 1; b[n_, i_, p_] := b[n, i, p] = If[p>n, 0, If[n == 0, 1, If[Min[i, p]<1, 0, Sum[b[n-i*j, i-1, p-j]*Binomial[t[i]+j-1, j], {j, 0, Min[n/i, p]}]]]]; a[n_] := Sum[k*b[n, n, k], {k, 1, n}]; Table[a[n] // FullSimplify, {n, 1, 30}] (* Jean-Fran├žois Alcover, Mar 13 2014, after Alois P. Heinz *)

CROSSREFS

Cf. A000081, A005196, A033185.

Sequence in context: A191825 A229514 A077927 * A147142 A298371 A106472

Adjacent sequences:  A005194 A005195 A005196 * A005198 A005199 A005200

KEYWORD

nonn

AUTHOR

N. J. A. Sloane. Definition clarified by N. J. A. Sloane, May 29 2012

EXTENSIONS

More terms from Alois P. Heinz, Aug 20 2012

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 07:50 EST 2018. Contains 299599 sequences. (Running on oeis4.)