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

Links

Alois P. Heinz, Rows n = 1..80, flattened

Wikipedia, Longest increasing subsequence

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

Example

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

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

Crossrefs

Column k=0 gives A321313.

Row sums give A000142.

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

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

Sequence in context: A263655 A329078 A059064 * A185690 A298248 A250204

Adjacent sequences: A321313 A321314 A321315 * A321317 A321318 A321319

Keyword

nonn,tabf

Author

Alois P. Heinz, Nov 03 2018

Status

approved