A134433 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} in which the last entry of the first increasing run is equal to k (1 <= k <= n).

1, 0, 2, 0, 1, 5, 0, 2, 6, 16, 0, 6, 16, 33, 65, 0, 24, 60, 114, 196, 326, 0, 120, 288, 522, 848, 1305, 1957, 0, 720, 1680, 2952, 4632, 6850, 9786, 13700, 0, 5040, 11520, 19800, 30336, 43710, 60672, 82201, 109601

Offset: 1

Author

Emeric Deutsch, Nov 22 2007

Keywords

• nonn
• tabl

Comments

T(n,n) = A000522(n-1) (number of arrangements of {1,2,...,n-1}).

T(n,2) = (n-2)! for n >= 3.

Sum_{k=1..n} k*T(n,k) = A056542(n+1).

Examples

			T(4,3)=6 because we have 3124, 3142, 3214, 3241, 1324 and 2314.
Triangle starts:
  1;
  0,   2;
  0,   1,   5;
  0,   2,   6,  16;
  0,   6,  16,  33,  65;
  0,  24,  60, 114, 196, 326;
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150, flattened.)

Crossrefs

Cf. A000522, A056542.

Programs

Maple

T:=proc(n,k): if k < n then sum(factorial(k-1)*factorial(n-j-1)/(factorial(j-1)*factorial(k-j-1)), j=1..k-1) elif k = n then factorial(n-1)*(sum(1/factorial(j), j = 0 .. n-1)) else 0 end if end proc: for n to 9 do seq(T(n, k),k=1..n) end do; # yields sequence in triangular form

Mathematica

Table[If[k < n, Sum[(n - j - 1)!*(k - j)*Binomial[k - 1, j - 1], {j, k - 1}], (n - 1)!*Sum[1/j!, {j, 0, n - 1}]], {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Nov 15 2019 *)

Formula

T(n,k) = Sum_{j=1..k-1} (n-j-1)!*(k-j)*binomial(k-1,j-1) for k < n;

T(n,n) = (n-1)!*Sum_{j=0..n-1} 1/j!.