A208956 Triangular array read by rows. T(n,k) is the number of n-permutations that have at least k fixed points with n >= 1 and 1 <= k <= n.

1, 1, 1, 4, 1, 1, 15, 7, 1, 1, 76, 31, 11, 1, 1, 455, 191, 56, 16, 1, 1, 3186, 1331, 407, 92, 22, 1, 1, 25487, 10655, 3235, 771, 141, 29, 1, 1, 229384, 95887, 29143, 6883, 1339, 205, 37, 1, 1, 2293839, 958879, 291394, 68914, 13264, 2176, 286, 46, 1, 1

Offset

1,4

Comments

Row sums = n!

Links

Alois P. Heinz, Rows n = 1..141, flattened

Formula

E.g.f. for column k: 1/(1-x) - D(x)*Sum_{i=0..k-1} x^i/i! where D(x) is the e.g.f. for A000166.

T(n,k) = Sum_{i=k..n} C(n,i)*A000166(n-i). - Alois P. Heinz, Apr 22 2013

Example

Triangle begins:
     1;
     1,    1;
     4,    1,   1;
    15,    7,   1,  1;
    76,   31,  11,  1,  1;
   455,  191,  56, 16,  1, 1;
  3186, 1331, 407, 92, 22, 1, 1;
  ...

Maple

b:= proc(n) b(n):= `if`(n<2, 1-n, (n-1)*(b(n-1)+b(n-2))) end:
T:= (n, k)-> add(binomial(n, i)*b(n-i), i=k..n):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Apr 22 2013

Mathematica

f[list_] := Select[list, #>0&]; Map[f, Transpose[Table[nn=10; d=Exp[-x]/(1-x); p=1/(1-x); s=Sum[x^i/i!, {i, 0, n}]; Drop[Range[0, nn]! CoefficientList[Series[p-s d, {x, 0, nn}], x], 1], {n, 0, 9}]]]//Flatten

Crossrefs

Cf. A002467 (column 1), A155521 (column 2).

Sequence in context: A157013 A346876 A141724 * A271705 A320280 A343804

Adjacent sequences: A208953 A208954 A208955 * A208957 A208958 A208959

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 03 2012

Status

approved