A184183 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.

1, 1, 1, 1, 4, 2, 14, 9, 1, 65, 46, 9, 366, 285, 66, 3, 2451, 2006, 539, 44, 18949, 16054, 4776, 530, 11, 166033, 144128, 46230, 6224, 265, 1624948, 1436322, 487573, 75269, 4635, 53, 17561350, 15740718, 5584332, 954116, 74430, 1854, 207650171, 188194591, 69157935, 12776470, 1177625, 44499, 309

Offset: 0

Author

Emeric Deutsch, Feb 14 2011

Keywords

• nonn
• tabf

Comments

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

Sum of entries in row n is n!.

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

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

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

Examples

			T(4,1) = 9 because we have 1243, 2314, 3421, 3124, 4231, 1342, 4312, 1423, and 2134.
T(6,3) = 3 because we have 563412, 341256, and 125634.
Triangle starts:
    1;
    1;
    1,   1;
    4,   2;
   14,   9,  1;
   65,  46,  9;
  366, 285, 66, 3;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..175

Crossrefs

Cf. A000166, A180196, A001565.

Programs

Maple

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

Mathematica

d = Subfactorial;
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[n_, k_] := Sum[b[n, i, k], {i, 0, n}]; T[0, 0] = 1;
Table[T[n, k], {n, 0, 12}, {k, 0, Quotient[n, 2]}] // Flatten (* Jean-François Alcover, Feb 16 2021, after Maple *)

Formula

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

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,

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

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

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