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