login
A180192
Triangle read by rows: T(n,k) is the number of permutations of [n] having k fixed blocks.
2
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,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
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
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.
Sequence in context: A095059 A021419 A338168 * A369019 A066529 A052080
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Sep 08 2010
STATUS
approved