cp's OEIS Frontend

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

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