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,5

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

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.

Example

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

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

Prog

(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

Crossrefs

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

Subarray of A214015.

Sequence in context: A098885 A106270 A319171 * A330964 A128704 A075259

Adjacent sequences: A047885 A047886 A047887 * A047889 A047890 A047891

Keyword

nonn,easy,nice,tabl

Author

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

Extensions

More terms from Naohiro Nomoto, Mar 01 2002

Status

approved