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

Author

Emanuele Munarini, Jan 30 2014

Keywords

• nonn

Examples

			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
  ^ ^ ^,   ^,     ^,     ^,   ^, ^, ^, ^, ^, ^
		

Links

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

Crossrefs

Cf. A000169, A038041, A005225, A055225.

Programs

Mathematica

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

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 */

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!)).