OFFSET
0,6
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.
LINKS
Alois P. Heinz, Rows n = 0..200, flattened
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).
EXAMPLE
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;
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 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Sep 08 2010
STATUS
approved