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

Author

Geoffrey Critzer, Mar 03 2012

Keywords

• nonn
• tabl

Comments

Row sums = n!

Examples

			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;
  ...
		

Links

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

Crossrefs

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

Programs

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

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