login
Rectangular array of numbers a(n,k) = number of permutations of n things with longest increasing subsequence of length <= k (1 <= k <= oo), read by antidiagonals.
8

%I #51 Sep 04 2023 11:36:18

%S 1,1,1,1,2,1,1,5,2,1,1,14,6,2,1,1,42,23,6,2,1,1,132,103,24,6,2,1,1,

%T 429,513,119,24,6,2,1,1,1430,2761,694,120,24,6,2,1,1,4862,15767,4582,

%U 719,120,24,6,2,1,1,16796,94359,33324,5003,720,120,24,6,2,1,1,58786,586590

%N Rectangular array of numbers a(n,k) = number of permutations of n things with longest increasing subsequence of length <= k (1 <= k <= oo), read by antidiagonals.

%C Also a(n,k) is the dimension of the space of SL(k)-invariants in V^n tensor (V^*)^n, where V is the standard k-dimensional representation of SL(k) and V^* is its dual. - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

%H Alois P. Heinz, <a href="/A047888/b047888.txt">Antidiagonals n = 1..44, flattened</a>

%H Ira M. Gessel, <a href="http://dx.doi.org/10.1016/0097-3165(90)90060-A">Symmetric functions and P-recursiveness</a>, J. Combin. Theory A 53, no. 2, (1990), 257-285.

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

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

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

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

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

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

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

%t rows = 12; h[l_List] := Module[{n = Length[l]}, Total[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_List] := 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_] := Table[g[n-k, Min[n-k, k], {k}], {k, 1, rows}] // Accumulate; A047888 = Table[T[n], {n, 1, rows}]; Table[A047888[[n-k+1, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Mar 06 2014, after _Alois P. Heinz_ *)

%o (PARI)

%o b(n, k) = {

%o my(x = 'x + O('x^(2*n)));

%o sum(i = 0, n, x^(2*i+k)/(i!*(i+k)!));

%o };

%o u(n, k) = {

%o my(v = Vec(matdet(matrix(k, k, i, j, b(n, abs(i-j))))));

%o return(vector((#v-1)\2, i, v[2*i+1] * i!^2));

%o };

%o A(n, k) = {

%o my(m = [;]);

%o for (i = 1, k, m = concat(m, u(n, i)~));

%o return(m);

%o };

%o A(6, 6) \\ _Gheorghe Coserea_, Feb 02 2016

%Y Rows of the array are partial sums of A047874. Cf. A047887.

%Y Subarray of A214015.

%K nonn,easy,nice,tabl

%O 1,5

%A Eric Rains (rains(AT)caltech.edu), _N. J. A. Sloane_

%E More terms from _Naohiro Nomoto_, Mar 01 2002