A216520 Triangular array read by rows, T(n,k) = number of partial functions on {1,2,...,n} with exactly k cycles.

1, 1, 1, 3, 5, 1, 16, 35, 12, 1, 125, 328, 149, 22, 1, 1296, 3894, 2125, 425, 35, 1, 16807, 56221, 35044, 8555, 970, 51, 1, 262144, 958152, 661878, 186809, 26180, 1918, 70, 1, 4782969, 18849384, 14145858, 4467092, 731059, 66836, 3430, 92, 1

Offset

0,4

Comments

Here we consider the directed graphs of partial functions on {1,2,...,n} where the undefined points are mapped to a special value (forming a forest).

Row sums = (n+1)^n.

Links

Table of n, a(n) for n=0..44.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132.

Formula

E.g.f.: exp(T(x))/(1 - T(x))^y where T(x) is the e.g.f. for A000169.

Example

1,
1, 1,
3, 5, 1,
16, 35, 12, 1,
125, 328, 149, 22, 1,
1296, 3894, 2125, 425, 35, 1,
16807, 56221, 35044, 8555, 970, 51, 1

Mathematica

nn=6; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0, nn]! CoefficientList[Series[Exp[t]/(1-t)^y, {x, 0, nn}], {x, y}] //Grid

Crossrefs

Sequence in context: A084833 A204020 A265649 * A204161 A346711 A278968

Adjacent sequences: A216517 A216518 A216519 * A216521 A216522 A216523

Keyword

nonn,tabl

Author

Geoffrey Critzer, Sep 08 2012

Status

approved