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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005196 a(n) = Sum_t t*F(n,t), where F(n,t) (see A095133) is the number of forests with n (unlabeled) nodes and exactly t trees.
(Formerly M2567)
6
1, 3, 6, 13, 24, 49, 93, 190, 381, 803, 1703, 3755, 8401, 19338, 45275, 108229, 262604, 647083, 1613941, 4072198, 10374138, 26663390, 69056163, 180098668, 472604314, 1247159936, 3307845730, 8814122981, 23585720703, 63359160443, 170815541708, 462049250165 (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..300

E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121. [The 17th entry is wrong]

Eric Weisstein's World of Mathematics, Forest

FORMULA

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

MAPLE

with(numtheory):

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

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

    end:

t:= proc(n) option remember; local k; `if` (n=0, 1,

      b(n)-(add(b(k)*b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2)

    end:

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

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

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

    end:

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

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

MATHEMATICA

nn=30; s[n_, k_]:=s[n, k]=a[n+1-k]+If[n<2k, 0, s[n-k, k]]; a[1]=1; a[n_]:=a[n]=Sum[a[i]s[n-1, i]i, {i, 1, n-1}]/(n-1); ft=Table[a[i]-Sum[a[j]a[i-j], {j, 1, i/2}]+If[OddQ[i], 0, a[i/2](a[i/2]+1)/2], {i, 1, nn}]; CoefficientList[Series[D[Product[1/(1-y x^i)^ft[[i]], {i, 1, nn}], y]/.y->1, {x, 0, 20}], x]  (* Geoffrey Critzer, Oct 13 2012, after code given by Robert A. Russell in A000055 *)

CROSSREFS

Cf. A000055, A005195, A095133.

Sequence in context: A000219 A191782 A027999 * A320286 A032287 A199403

Adjacent sequences:  A005193 A005194 A005195 * A005197 A005198 A005199

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Jun 03 2004

Definition clarified by N. J. A. Sloane, May 29 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 November 14 15:07 EST 2018. Contains 317208 sequences. (Running on oeis4.)