A214015 - OEIS

%I #39 Jan 12 2024 14:10:15

%S 1,1,0,1,1,0,1,1,1,0,1,1,2,1,0,1,1,2,5,1,0,1,1,2,6,14,1,0,1,1,2,6,23,

%T 42,1,0,1,1,2,6,24,103,132,1,0,1,1,2,6,24,119,513,429,1,0,1,1,2,6,24,

%U 120,694,2761,1430,1,0,1,1,2,6,24,120,719,4582,15767,4862,1,0

%N Number of permutations A(n,k) in S_n with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C A(n,k) is also the sum of the squares of numbers of standard Young tableaux (SYT) of height <= k over all partitions of n.

%C This array is a larger and reflected version of A047888.

%C Column k>1 is asymptotic to (Product_{j=1..k} j!) * k^(2*n + k^2/2) / (Pi^((k-1)/2) * 2^((k-1)*(k+2)/2) * n^((k^2-1)/2)). - _Vaclav Kotesovec_, Sep 10 2014

%H Alois P. Heinz, <a href="/A214015/b214015.txt">Antidiagonals n = 0..70, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem">Longest increasing subsequence problem</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Young_tableau">Young tableau</a>

%e A(4,2) = 14 because 14 permutations of {1,2,3,4} do not contain an increasing subsequence of length > 2: 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.  Permutation 1423 is not counted because it contains the noncontiguous increasing subsequence 123.

%e A(4,2) = 14 = 2^2 + 3^2 + 1^2 because the partitions of 4 with <= 2 parts are [2,2], [3,1], [4] with 2, 3, 1 standard Young tableaux, respectively:

%e   +------+  +------+  +---------+  +---------+  +---------+  +------------+

%e   | 1  3 |  | 1  2 |  | 1  3  4 |  | 1  2  4 |  | 1  2  3 |  | 1  2  3  4 |

%e   | 2  4 |  | 3  4 |  | 2 .-----+  | 3 .-----+  | 4 .-----+  +------------+

%e   +------+  +------+  +---+        +---+        +---+

%e Square array A(n,k) begins:

%e   1,  1,   1,    1,    1,    1,    1,    1, ...

%e   0,  1,   1,    1,    1,    1,    1,    1, ...

%e   0,  1,   2,    2,    2,    2,    2,    2, ...

%e   0,  1,   5,    6,    6,    6,    6,    6, ...

%e   0,  1,  14,   23,   24,   24,   24,   24, ...

%e   0,  1,  42,  103,  119,  120,  120,  120, ...

%e   0,  1, 132,  513,  694,  719,  720,  720, ...

%e   0,  1, 429, 2761, 4582, 5003, 5039, 5040, ...

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

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

%p     end:

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

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

%p A:= (n, k)-> `if`(k>=n, n!, g(n, k, [])):

%p seq(seq(A(n, d-n), n=0..d), d=0..14);

%t 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}]];

%t 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 A[n_, k_] := If[k >= n, n!, g[n, k, {}]];

%t Table [Table [A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Dec 09 2013, translated from Maple *)

%Y Columns k=0-10 give: A000007, A000012, A000108, A005802, A047889, A047890, A052399, A072131, A072132, A072133, A072167.

%Y Differences between A000142 and columns k=0-9 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.

%Y Main diagonal and first lower diagonal give: A000142, A033312.

%Y A(2n,n-1) gives A269042(n) for n>0.

%Y Cf. A047887, A047888, A182172, A208447, A214152, A267479.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Jul 01 2012