A220234 Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k recurrent elements whose preimage contains only one element, n>=0, 0<=k<=n.

0, 0, 1, 2, 0, 2, 9, 12, 0, 6, 88, 72, 72, 0, 24, 985, 1000, 540, 480, 0, 120, 13956, 13980, 10080, 4320, 3600, 0, 720, 233149, 243684, 169470, 104160, 37800, 30240, 0, 5040, 4519824, 4835824, 3544128, 2049600, 1142400, 362880, 282240, 0, 40320, 99606609, 109239120, 81840024, 50452416, 25779600, 13426560, 3810240, 2903040, 0, 362880

Offset

0,4

Comments

A functional digraph of a function f:{1,2,...,n}->{1,2,...,n} is a directed graph on vertex set {1,2,...,n} with an arrow from i to j if f(i)=j. Every connected component of the digraph contains a unique cycle and every vertex i of this cycle is the root of a rooted tree directed towards i. T(n,k) is the number k of rooted trees that consist of a single vertex over all cycles in all functional digraphs on {1,2,...,n}. Definition from Stanley, page 83.

Row sums = n^n

References

R. Stanley, Enumerative Combinatorics Vol II, Cambridge Univ. Press, 1999.

Links

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

Formula

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

Example

0,
0,     1,
2,     0,     2,
9,     12,    0,     6,
88,    72,    72,    0,    24,
985,   1000,  540,   480,  0,    120,
13956, 13980, 10080, 4320, 3600, 0,   720

Mathematica

nn=6; f[list_]:=Select[list, #>0&]; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Prepend[Drop[Map[Insert[#, 0, -2]&, Map[f, Range[0, nn]!CoefficientList[Series[1/(1-x(Exp[t]-1+y)), {x, 0, nn}], {x, y}]]], 1], {0}]//Grid

Crossrefs

Sequence in context: A332628 A091518 A096734 * A038020 A211910 A250406

Adjacent sequences: A220231 A220232 A220233 * A220235 A220236 A220237

Keyword

nonn,tabl

Author

Geoffrey Critzer, Dec 08 2012

Status

approved