A225497 Total number of rooted labeled trees over all forests on {1,2,...,n} in which one tree has been specially designated.

1, 6, 42, 380, 4320, 59682, 974848, 18423288, 396000000, 9548713790, 255409127424, 7507985556084, 240659872940032, 8355664160156250, 312437224148828160, 12519386633593104368, 535233488907211702272, 24320165501859426874998, 1170472960000000000000000, 59483046140261749951587180

Offset

1,2

Comments

The expected number of trees in each forest approaches 5/2 as n gets large.

Links

Table of n, a(n) for n=1..20.

Formula

a(n) = Sum_{k=1..n} binomial(n,k)*n^(n-k)*k^2 = ((1 + 1/n)^n n^(1 + n) (-1 + 5 n))/(1 + n)^3.

a(n) = Sum_{k=1..n} A225465(n,k)*k.

Example

a(2) = 6 because there are 6 trees in these forests on 2 nodes.  The root node is on top and the designated tree is marked by '.
...1'...   ...2'...   ...1'..2...   ...1..2'...
...| ...   ...| ...   ...........   ...........
...2 ...   ...1 ...   ...........   ...........

Mathematica

Table[Sum[Binomial[n - 1, k - 1] n^(n - k) k^2, {k, 1, n}], {n, 1,
  20}]

Crossrefs

Sequence in context: A052589 A074107 A187121 * A336950 A304071 A052608

Adjacent sequences: A225494 A225495 A225496 * A225498 A225499 A225500

Keyword

nonn

Author

Geoffrey Critzer, May 08 2013

Status

approved