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

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, 429, 513, 119, 24, 6, 2, 1, 1, 1430, 2761, 694, 120, 24, 6, 2, 1, 1, 4862, 15767, 4582, 719, 120, 24, 6, 2, 1, 1, 16796, 94359, 33324, 5003, 720, 120, 24, 6, 2, 1, 1, 58786, 586590

Offset: 1

Author

Eric Rains (rains(AT)caltech.edu), N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• tabl

Comments

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

Examples

			Square array a(n,k) begins:
  1,   1,    1,    1,    1,    1, ...
  1,   2,    2,    2,    2,    2, ...
  1,   5,    6,    6,    6,    6, ...
  1,  14,   23,   24,   24,   24, ...
  1,  42,  103,  119,  120,  120, ...
  1, 132,  513,  694,  719,  720, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 1..44, flattened
• Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53, no. 2, (1990), 257-285.

Crossrefs

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

Subarray of A214015.

Programs

Mathematica

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

PARI

b(n, k) = {
  my(x = 'x + O('x^(2*n)));
  sum(i = 0, n, x^(2*i+k)/(i!*(i+k)!));
};
u(n, k) = {
  my(v = Vec(matdet(matrix(k, k, i, j, b(n, abs(i-j))))));
  return(vector((#v-1)\2, i, v[2*i+1] * i!^2));
};
A(n, k) = {
  my(m = [;]);
  for (i = 1, k, m = concat(m, u(n, i)~));
  return(m);
};
A(6, 6)  \\ Gheorghe Coserea, Feb 02 2016

Extensions

More terms from Naohiro Nomoto, Mar 01 2002