A047887 -id:A047887 - cp's OEIS frontend

A047874 Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n).

1, 1, 1, 1, 4, 1, 1, 13, 9, 1, 1, 41, 61, 16, 1, 1, 131, 381, 181, 25, 1, 1, 428, 2332, 1821, 421, 36, 1, 1, 1429, 14337, 17557, 6105, 841, 49, 1, 1, 4861, 89497, 167449, 83029, 16465, 1513, 64, 1, 1, 16795, 569794, 1604098, 1100902, 296326, 38281, 2521, 81, 1

Offset: 1

Eric Rains (rains(AT)caltech.edu)

Mirror image of triangle in A126065.
T(n,m) is also the sum of squares of n!/(product of hook lengths), summed over the partitions of n in exactly m parts (Robinson-Schensted correspondence). - Wouter Meeussen, Sep 16 2010
Table I "Distribution of L_n" on p. 98 of the Pilpel reference. - Joerg Arndt, Apr 13 2013
In general, for column k is a(n) ~ product(j!, j=0..k-1) * k^(2*n+k^2/2) / (2^((k-1)*(k+2)/2) * Pi^((k-1)/2) * n^((k^2-1)/2)) (result due to Regev) . - Vaclav Kotesovec, Mar 18 2014

			T(3,2) = 4 because 132, 213, 231, 312 have longest increasing subsequences of length 2.
Triangle T(n,k) begins:
  1;
  1,   1;
  1,   4,    1;
  1,  13,    9,    1;
  1,  41,   61,   16,   1;
  1, 131,  381,  181,  25,  1;
  1, 428, 2332, 1821, 421, 36,  1;
  ...

Leonid Petrov, Rows n = 1..120, flattened (first 60 rows from Alois P. Heinz)
P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.
FindStat - Combinatorial Statistic Finder, The length of the longest increasing subsequence of the permutation.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.
J. M. Hammersley, A few seedings of research, in Proc. Sixth Berkeley Sympos. Math. Stat. and Prob., ed. L. M. le Cam et al., Univ. Calif. Press, 1972, Vol. I, pp. 345-394.
Guo-Niu Han, A promenade in the garden of hook length formulas, Slides, 61st SLC Curia, Portugal - September 22, 2008. [From _Wouter Meeussen_, Sep 16 2010]
J. Hunt and T. Szymanski, A fast algorithm for computing longest common subsequences, Commun. ACM, 20 (1977), 350-353.
E. Irurozki, B. Calvo, and J. A. Lozano, Sampling and learning the Mallows model under the Ulam distance, Technical Report, 2014.
S. Pilpel, Descending subsequences of random permutations, J. Combin. Theory, A 53 (1990), 96-116.
A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115-136.
C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179-191.
Richard P. Stanley, Increasing and Decreasing Subsequences of Permutations and Their Variants, arXiv:math/0512035 [math.CO], 2005.
Wikipedia, Longest increasing subsequence problem

Cf. A047887 and A047888.
Columns k=1-10 give: A000012, A001453, A001454, A001455, A001456, A001457, A001458, A239432, A245665, A245666.
Row sums give A000142.
Cf. A047884. - Wouter Meeussen, Sep 16 2010
Cf. A224652 (Table II "Distribution of F_n" on p. 99 of the Pilpel reference).
Cf. A245667.
T(2n,n) gives A267433.
Cf. A003316.

h:= proc(l) local n; n:= nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n) end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
T:= n-> seq(g(n-k, min(n-k, k), [k]), k=1..n):
seq(T(n), n=1..12);  # Alois P. Heinz, Jul 05 2012

Table[Total[NumberOfTableaux[#]^2&/@ IntegerPartitions[n,{k}]],{n,7},{k,n}] (* Wouter Meeussen, Sep 16 2010, revised Nov 19 2013 *)
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, n}]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Mar 06 2014, after Alois P. Heinz *)

Sum_{k=1..n} k * T(n,k) = A003316(n). - Alois P. Heinz, Nov 04 2018

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

Original entry on oeis.org

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, 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, 120, 694, 2761, 1430, 1, 0, 1, 1, 2, 6, 24, 120, 719, 4582, 15767, 4862, 1, 0

Offset: 0

Alois P. Heinz, Jul 01 2012

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.
This array is a larger and reflected version of A047888.
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

			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.
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:
  +------+  +------+  +---------+  +---------+  +---------+  +------------+
  | 1  3 |  | 1  2 |  | 1  3  4 |  | 1  2  4 |  | 1  2  3 |  | 1  2  3  4 |
  | 2  4 |  | 3  4 |  | 2 .-----+  | 3 .-----+  | 4 .-----+  +------------+
  +------+  +------+  +---+        +---+        +---+
Square array A(n,k) begins:
  1,  1,   1,    1,    1,    1,    1,    1, ...
  0,  1,   1,    1,    1,    1,    1,    1, ...
  0,  1,   2,    2,    2,    2,    2,    2, ...
  0,  1,   5,    6,    6,    6,    6,    6, ...
  0,  1,  14,   23,   24,   24,   24,   24, ...
  0,  1,  42,  103,  119,  120,  120,  120, ...
  0,  1, 132,  513,  694,  719,  720,  720, ...
  0,  1, 429, 2761, 4582, 5003, 5039, 5040, ...

Alois P. Heinz, Antidiagonals n = 0..70, flattened
Wikipedia, Longest increasing subsequence problem
Wikipedia, Young tableau

Columns k=0-10 give: A000007, A000012, A000108, A005802, A047889, A047890, A052399, A072131, A072132, A072133, A072167.
Differences between A000142 and columns k=0-9 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.
Main diagonal and first lower diagonal give: A000142, A033312.
A(2n,n-1) gives A269042(n) for n>0.
Cf. A047887, A047888, A182172, A208447, A214152, A267479.

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
A:= (n, k)-> `if`(k>=n, n!, g(n, k, [])):
seq(seq(A(n, d-n), n=0..d), d=0..14);

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}]];
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}]]];
A[n_, k_] := If[k >= n, n!, g[n, k, {}]];
Table [Table [A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)

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.

Original entry on oeis.org

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

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

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

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

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.

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

Subarray of A214015.

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

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

More terms from Naohiro Nomoto, Mar 01 2002

A331883 The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.

Original entry on oeis.org

0, 1, 1, 5, 26, 132, 834, 6477, 56242

Offset: 1

Ildar Gainullin, Jan 30 2020

Only permutations whose longest increasing subsequence is at most n/2 need to be considered.

			a(3) = 1 because the only permutation whose longest increasing subsequence is 1 is [3,2,1] and this contains two disjoint increasing subsequences of length 1.
The a(4) = 5 permutations are:
  [2,1,4,3],
  [2,4,1,3],
  [3,1,4,2],
  [3,4,1,2],
  [4,3,2,1].

Wikipedia, Longest increasing subsequence problem

Cf. A047874, A047887, A167995.

cp's OEIS Frontend

A047874 Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A331883 The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs