A236696 Number of forests on n vertices consisting of labeled rooted trees of the same size.

1, 3, 10, 77, 626, 8707, 117650, 2242193, 43250842, 1049248991, 25937424602, 772559330281, 23298085122482, 817466439388341, 29223801257127976, 1181267018656911617, 48661191875666868482, 2232302772999145783735, 104127350297911241532842

Offset

1,2

Links

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

Formula

a(n) = sum(d divides n, n!/(n/d)!*(d^(d-1)/d!)^(n/d) ).

E.g.f.: sum(k>=1, exp(k^(k-1)*x^k/k!)).

Example

For n = 3 we have the following 10 forests (where the roots are denoted by ^):
                              3  2  3  1  2  1
                              |  |  |  |  |  |
         2   3  1   3  1   2  2  3  1  3  1  2
          \ /    \ /    \ /   |  |  |  |  |  |
  1 2 3    1      2      3    1  1  2  2  3  3
  ^ ^ ^,   ^,     ^,     ^,   ^, ^, ^, ^, ^, ^

Mathematica

Table[Sum[n!/(n/d)!*(d^(d-1)/d!)^(n/d), {d, Divisors[n]}], {n, 1, 100}]

Prog

(Maxima) a(n):= lsum(n!/(n/d)!*(d^(d-1)/d!)^(n/d), d, listify(divisors(n))); makelist(a(n), n, 1, 40); /* Emanuele Munarini, Feb 03 2014 */

Crossrefs

Cf. A000169, A038041, A005225, A055225.

Sequence in context: A082245 A158033 A027159 * A262259 A203492 A320258

Adjacent sequences: A236693 A236694 A236695 * A236697 A236698 A236699

Keyword

nonn

Author

Emanuele Munarini, Jan 30 2014

Status

approved