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,5

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

Links

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

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.

Example

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

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 *)

Crossrefs

Cf. A000166, A180196, A001565.

Sequence in context: A255044 A248249 A161134 * A317738 A224893 A087957

Adjacent sequences: A184180 A184181 A184182 * A184184 A184185 A184186

Keyword

nonn,tabf

Author

Emeric Deutsch, Feb 14 2011

Status

approved