1,2

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

Eric Weisstein's World of Mathematics, Permutation Pattern

Wikipedia, Longest increasing subsequence problem

Wikipedia, Young tableau

T(n,k) = Sum_{i=k..n} A047874(n,i).

T(n,k) = A000142(n) - A214015(n,k-1).

T(3,2) = 5. All 3! = 6 permutations of {1,2,3} contain an increasing subsequence of length 2 with the exception of 321.

Triangle T(n,k) begins:

1;

2, 1;

6, 5, 1;

24, 23, 10, 1;

120, 119, 78, 17, 1;

720, 719, 588, 207, 26, 1;

5040, 5039, 4611, 2279, 458, 37, 1;

...

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j

+add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)

end:

g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,

add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):

T:= (n, k)-> n! -g(n, k-1, []):

seq(seq(T(n, k), k=1..n), n=1..12);

h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]! / Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}] ]; g[n_, i_, l_] := If[n == 0 || i === 1, h[Join[l, Array[1&, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; t[n_, k_] := n! - g[n, k-1, {}]; Table[Table[t[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Columns k=1-10 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.

Row sums give: A003316.

T(2n,n) gives A269021.

Diagonal and lower diagonals give: A000012, A002522, A217200, A217193.

Cf. A047874, A214015.

Sequence in context: A159924 A133367 A179456 * A121575 A121576 A049444

Adjacent sequences: A214149 A214150 A214151 * A214153 A214154 A214155

nonn,tabl

Alois P. Heinz, Jul 05 2012

approved