A321316 Number T(n,k) of permutations of [n] whose difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence equals k; triangle T(n,k), n >= 1, 1-n <= k <= n-1, read by rows.

1, 1, 0, 1, 1, 0, 4, 0, 1, 1, 0, 9, 4, 9, 0, 1, 1, 0, 16, 25, 36, 25, 16, 0, 1, 1, 0, 25, 81, 125, 256, 125, 81, 25, 0, 1, 1, 0, 36, 196, 421, 1225, 1282, 1225, 421, 196, 36, 0, 1, 1, 0, 49, 400, 1225, 4292, 9261, 9864, 9261, 4292, 1225, 400, 49, 0, 1

Offset: 1

Author

Alois P. Heinz, Nov 03 2018

Keywords

• nonn
• tabf

Examples

			:                                1                             ;
:                          1,    0,    1                       ;
:                    1,    0,    4,    0,   1                  ;
:               1,   0,    9,    4,    9,   0,   1             ;
:          1,   0,  16,   25,   36,   25,  16,   0,  1         ;
:      1,  0,  25,  81,  125,  256,  125,  81,  25,  0, 1      ;
:   1, 0, 36, 196, 421, 1225, 1282, 1225, 421, 196, 36, 0, 1   ;
		

Links

• Alois P. Heinz, Rows n = 1..80, flattened
• Wikipedia, Longest increasing subsequence

Crossrefs

Column k=0 gives A321313.

Row sums give A000142.

T(n+1,n-2) gives A000290.

Cf. A303697, A321277, A321278, A321314, A321315.

Programs

Maple

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*x^(l[1]-nops(l)) :
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
b:= proc(n) option remember; g(n$2, []) end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=1-n..n-1), n=1..10);

Mathematica

h[l_] := With[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[j > l[[k]], 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
f[l_] := h[l]^2*x^(l[[1]] - Length[l]);
g[n_, i_, l_] := If[n == 0 || i == 1, f[Join[l, Table[1, {n}]]], g[n, i - 1, l] + g[n - i, Min[i, n - i], Append[l, i]]];
b[n_] := b[n] = g[n, n, {}];
T[n_, k_] := Coefficient[b[n], x, k];
Table[Table[T[n, k], {k, 1 - n, n - 1}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Feb 27 2021, after Alois P. Heinz *)

Formula

T(n,k) = T(n,-k).

Sum_{k=1..n-1} T(n,k) = A321314(n).

Sum_{k=0..n-1} T(n,k) = A321315(n).

(1/2) * Sum_{k=1-n..n-1} abs(k) * T(n,k) = A321277(n).

(1/2) * Sum_{k=1-n..n-1} k^2 * T(n,k) = A321278(n).