|
%I #14 Feb 16 2021 08:11:53
%S 1,0,1,1,1,2,4,0,9,12,3,44,57,18,1,265,321,123,11,1854,2176,888,120,2,
%T 14833,17008,7218,1208,53,133496,150505,65460,12550,860,9,1334961,
%U 1485465,657690,137970,12405,309,14684570,16170036,7257240,1623440
%N Triangle read by rows: T(n,k) is the number of permutations of [n] having k fixed blocks.
%C 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.
%C Row n has 1 + ceiling(n/2) entries.
%H Alois P. Heinz, <a href="/A180192/b180192.txt">Rows n = 0..200, flattened</a>
%F 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.
%F 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.
%F Sum_{k>=0} k*T(n,k) = (n-1)!*(n-1) = A001563(n-1).
%e 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).
%e Triangle starts:
%e 1;
%e 0, 1;
%e 1, 1;
%e 2, 4, 0;
%e 9, 12, 3;
%e 44, 57, 18, 1;
%e 265, 321, 123, 11;
%p # yields sequence in triangular form:
%p d[0] := 1: for n to 50 do d[n] := n*d[n-1] + (-1)^n od:
%p T := (n, k) -> add(binomial(j-1, k-1)*binomial(n+1-j, k)*d[n-j], j = k .. n+1-k):
%p for n from 0 to 11 do seq(T(n, k), k = 0..ceil((1/2)*n)) od;
%t d = Subfactorial;
%t T[n_, k_] := Sum[Binomial[j-1, k-1] Binomial[n-j+1, k] d[n-j] , {j, k, n-k+1}];
%t Table[T[n, k], {n, 0, 11}, {k, 0, Ceiling[n/2]}] // Flatten (* _Jean-François Alcover_, Feb 16 2021 *)
%Y T(n,0) = d(n) = A000166(n).
%Y T(n,1) = A177265(n).
%Y T(2n-1,n) = d(n-1).
%Y T(2n,n) = d(n+1) + d(n) = A000255(n).
%Y Sum of entries in row n is n! = A000142(n).
%Y Cf. A001563.
%K nonn,tabf
%O 0,6
%A _Emeric Deutsch_, Sep 08 2010
|
