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.

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

Triangle begins:
  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

Row sums give A000312.

Cf. A000169.

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