OFFSET
0,5
COMMENTS
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
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Feb 14 2011
STATUS
approved