A350227 Triangular array read by rows. T(n,k) is the number of partial permutations on [n] with exactly k connected components, n>=0, 0<=k<=n.

1, 0, 2, 0, 3, 4, 0, 8, 18, 8, 0, 30, 91, 72, 16, 0, 144, 540, 590, 240, 32, 0, 840, 3718, 5085, 2900, 720, 64, 0, 5760, 29232, 47516, 34230, 12040, 2016, 128, 0, 45360, 258732, 484092, 416857, 186480, 44576, 5376, 256, 0, 403200, 2547360, 5368184, 5340888, 2869314, 876960, 151872, 13824, 512

Offset

0,3

Links

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

Formula

T(n,n) = 2^n = A000079(n) (counts the idempotent elements).

For n>=1, T(n,1) = (n-1)! + n! = A001048(n) (the component is a cycle or a directed path to a point with a self loop).

E.g.f.: exp(y*log(1/(1-x)))*exp(y*x/(1-x)).

Example

Triangle begins:
  1;
  0,   2;
  0,   3,   4;
  0,   8,  18,   8;
  0,  30,  91,  72,  16;
  0, 144, 540, 590, 240, 32;
  ...

Mathematica

nn = 9; Table[Take[(Range[0, nn]! CoefficientList[Series[1/(1 - x)^y Exp[y x/(1 - x)], {x, 0, nn}], {x, y}])[[i, All]], i], {i, 1, nn + 1}] // Grid

Crossrefs

Cf. A000079, A132393, A001048, A002720 (row sums).

Sequence in context: A340991 A013584 A307320 * A137372 A212844 A066439

Adjacent sequences: A350224 A350225 A350226 * A350228 A350229 A350230

Keyword

nonn,tabl

Author

Geoffrey Critzer, Dec 20 2021

Status

approved