A180192 Triangle read by rows: T(n,k) is the number of permutations of [n] having k fixed blocks.

1, 0, 1, 1, 1, 2, 4, 0, 9, 12, 3, 44, 57, 18, 1, 265, 321, 123, 11, 1854, 2176, 888, 120, 2, 14833, 17008, 7218, 1208, 53, 133496, 150505, 65460, 12550, 860, 9, 1334961, 1485465, 657690, 137970, 12405, 309, 14684570, 16170036, 7257240, 1623440

Offset: 0

Author

Emeric Deutsch, Sep 08 2010

Keywords

• nonn
• tabf

Comments

A fixed block of a permutation p is a maximal sequence of consecutive fixed points of p. For example, the permutation 213458769 has 3 fixed blocks: 345, 7, and 9.

Row n has 1 + ceiling(n/2) entries.

Examples

			T(4,2)=3 because we have (1)4(3)2, (1)32(4), and 3(2)1(4) (the fixed blocks are shown between parentheses).
Triangle starts:
    1;
    0,   1;
    1,   1;
    2,   4,   0;
    9,  12,   3;
   44,  57,  18,   1;
  265, 321, 123,  11;
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened

Crossrefs

T(n,0) = d(n) = A000166(n).

T(n,1) = A177265(n).

T(2n-1,n) = d(n-1).

T(2n,n) = d(n+1) + d(n) = A000255(n).

Sum of entries in row n is n! = A000142(n).

Cf. A001563.

Programs

Maple

# yields sequence in triangular form:
d[0] := 1: for n to 50 do d[n] := n*d[n-1] + (-1)^n od:
T := (n, k) -> add(binomial(j-1, k-1)*binomial(n+1-j, k)*d[n-j], j = k .. n+1-k):
for n from 0 to 11 do seq(T(n, k), k = 0..ceil((1/2)*n)) od;

Mathematica

d = Subfactorial;
T[n_, k_] := Sum[Binomial[j-1, k-1] Binomial[n-j+1, k] d[n-j] , {j, k, n-k+1}];
Table[T[n, k], {n, 0, 11}, {k, 0, Ceiling[n/2]}] // Flatten (* Jean-François Alcover, Feb 16 2021 *)

Formula

T(n,k) = Sum_{j=k..n+1-k} binomial(j-1,k-1)*binomial(n+1-j,k)*d(n-j), where d(i) = A000166(i) are the derangement numbers.

The term binomial(j-1,k-1)*binomial(n+1-j,k)*d(n-j) in the above sum gives the number of permutations of [n] having k fixed blocks and a total number of j fixed points.

Sum_{k>=0} k*T(n,k) = (n-1)!*(n-1) = A001563(n-1).