cp's OEIS Frontend

A180193 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of odd length (0<=k<=n).

%I A180193 #10 May 19 2024 08:10:43
%S A180193 1,0,1,1,0,1,0,3,0,3,2,0,11,0,11,0,14,0,53,0,53,6,0,96,0,309,0,309,0,
%T A180193 78,0,724,0,2119,0,2119,24,0,852,0,6070,0,16687,0,16687,0,504,0,9300,
%U A180193 0,56418,0,148329,0,148329,120,0,8040,0,106170,0,577556,0,1468457,0
%N A180193 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of odd length (0<=k<=n).
%C A180193 A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67.
%H A180193 A. N. Myers, <a href="https://doi.org/10.1006/jcta.2002.3279">Counting permutations by their rigid patterns</a>, J. Combin. Theory, Series A, Vol. 99, No. 2 (2002), pp. 345-357.
%F A180193 T(n,k) = Sum(binomial(k+j,j)*binomial((n+k+2)/2,k+j-1)*[d(k+j)+d(k+j-1)], j=0..(n-k)/2) if n and k are of the same parity; T(n,k)=0 if n and k have opposite parities (0<=k<=n).
%F A180193 T(n,n) = T(n,n-2) = d(n)+d(n-1) = A000255(n-1), where d(i)=A000166(i) are the derangement numbers.
%F A180193 T(2n+1,1) = A001564(n).
%F A180193 Sum(k*T(n,k),k>=0) = A180195(n).
%F A180193 Sum of entries in row n = n! = A000142(n).
%e A180193 T(3,1)=3 because we have (123), 23(1), and (3)12 (the blocks of odd length are shown between parentheses). T(4,0)=2 because we have 1234 and 3412.
%e A180193 Triangle starts:
%e A180193   1;
%e A180193   0,1;
%e A180193   1,0,1;
%e A180193   0,3,0,3;
%e A180193   2,0,11,0,11;
%e A180193   0,14,0,53,0,53;
%p A180193 d[ -1] := 0: d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if `mod`(n+k, 2) = 1 then 0 else sum(binomial(k+j, j)*binomial((1/2)*n+(1/2)*k-1, k+j-1)*(d[k+j]+d[k+j-1]), j = 0 .. (1/2)*n-(1/2)*k) end if end proc; for n from 0 to 10 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form
%Y A180193 Cf. A000166, A000255, A001564, A180194, A180195
%K A180193 nonn,tabl
%O A180193 0,8
%A A180193 _Emeric Deutsch_, Sep 09 2010