A225465 Triangular array read by rows. T(n,k) is the number of rooted forests on {1,2,...,n} in which one tree has been specially designated that contain exactly k trees; n>=1, 1<=k<=n.

1, 2, 2, 9, 12, 3, 64, 96, 36, 4, 625, 1000, 450, 80, 5, 7776, 12960, 6480, 1440, 150, 6, 117649, 201684, 108045, 27440, 3675, 252, 7, 2097152, 3670016, 2064384, 573440, 89600, 8064, 392, 8

Offset

1,2

Comments

Row sums = 2n*(n+1)^(n-2) = A089946(offset).

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

Links

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

Formula

T(n,k) = binomial(n-1,k-1)*n^(n-k)*k = A061356(n,k)*k(offset).

E.g.f.: y*A(x)*exp(y*A(x)) where A(x) is e.g.f. for A000169.

Example

    T(2,1)=2                  T(2,2)=2
...1'...   ...2'...   ...1'..2...   ...1..2'...
...| ...   ...| ...   ...........   ...........
...2 ...   ...1 ...   ...........   ...........
The root node is on top.  The ' indicates the tree which has been specially designated.
1,
2, 2,
9, 12, 3,
64, 96, 36, 4,
625, 1000, 450, 80, 5,
7776, 12960, 6480, 1440, 150, 6,
117649, 201684, 108045, 27440, 3675, 252, 7,

Mathematica

Table[Table[Binomial[n - 1, k - 1] n^(n - k) k, {k, 1, n}], {n, 1,
   8}] // Grid

Crossrefs

Sequence in context: A374303 A372641 A002880 * A248665 A066324 A143146

Adjacent sequences: A225462 A225463 A225464 * A225466 A225467 A225468

Keyword

nonn,tabl

Author

Geoffrey Critzer, May 08 2013

Status

approved