A184183 - OEIS

%I #20 Feb 16 2021 08:57:43

%S 1,1,1,1,4,2,14,9,1,65,46,9,366,285,66,3,2451,2006,539,44,18949,16054,

%T 4776,530,11,166033,144128,46230,6224,265,1624948,1436322,487573,

%U 75269,4635,53,17561350,15740718,5584332,954116,74430,1854,207650171,188194591,69157935,12776470,1177625,44499,309

%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k blocks of length 2 (0 <= k <= floor(n/2)). 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; one of them is of length 2.

%C Number of entries in row n is 1+floor(n/2).

%C Sum of entries in row n is n!.

%C T(2n+1,n) = d(n+2), where d(i)=A000166(n) are the derangement numbers.

%C T(2n,n) = d(n-1) + d(n), where d(i)=A000166(n) are the derangement numbers.

%C Sum_{k>=0} k*T(n,k) = A001565(n-3) (n>=3).

%H Alois P. Heinz, <a href="/A184183/b184183.txt">Rows n = 0..175</a>

%F T(n,k) = Sum_{i=0..n} b(n,i,k), where b(n,i,j) = number of permutations of {1,2,...,n} having i blocks of length 1 and j blocks of length 2 is given by

%F b(n,i,j) = Sum_{q=i+j+1..(1/3)*(n+2i+j)} binomial(n+i-2q-1, q-i-j-1)*q!*(d(q) + d(q-1))/(i!j!(q-i-j)!) if i+2j < n,

%F b(n,i,j) = binomial(i+j,i)*(d(q) + d(q-1)) if i+2j=n,

%F b(n,i,j) = 0 if i+2j > n, where

%F d(m) = A000166(m) are the derangement numbers.

%e T(4,1) = 9 because we have 1243, 2314, 3421, 3124, 4231, 1342, 4312, 1423, and 2134.

%e T(6,3) = 3 because we have 563412, 341256, and 125634.

%e Triangle starts:

%e     1;

%e     1;

%e     1,   1;

%e     4,   2;

%e    14,   9,  1;

%e    65,  46,  9;

%e   366, 285, 66, 3;

%e   ...

%p d[-1] := 0: d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: b := proc (n, i, j) if i+2*j < n then add(binomial(n+i-2*q-1, q-i-j-1)*factorial(q)*(d[q]+d[q-1])/(factorial(i)*factorial(j)*factorial(q-i-j)), q = i+j+1 .. (1/3)*n+(2/3)*i+(1/3)*j) elif i+2*j = n then factorial(i+j)*(d[i+j]+d[i+j-1])/(factorial(i)*factorial(j)) else 0 end if end proc: T := proc (n, k) options operator, arrow; add(b(n, i, k), i = 0 .. n) end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

%t d = Subfactorial;

%t b[n_, i_, j_] := Which[i+2j < n, Sum[Binomial[n+i-2q-1, q-i-j-1]*q!*(d[q]+ d[q-1])/(i!*j!*(q-i-j)!), {q, i+j+1, n/3 + 2i/3 + j/3}], i+2j == n, (i+j)!*((d[i+j] + d[i+j-1])/(i!*j!)), True, 0];

%t T[n_, k_] := Sum[b[n, i, k], {i, 0, n}]; T[0, 0] = 1;

%t Table[T[n, k], {n, 0, 12}, {k, 0, Quotient[n, 2]}] // Flatten (* _Jean-François Alcover_, Feb 16 2021, after Maple *)

%Y Cf. A000166, A180196, A001565.

%K nonn,tabf

%O 0,5

%A _Emeric Deutsch_, Feb 14 2011