A003316 -id:A003316 - 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

A214152 Number of permutations T(n,k) in S_n containing an increasing subsequence of length k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 2, 1, 6, 5, 1, 24, 23, 10, 1, 120, 119, 78, 17, 1, 720, 719, 588, 207, 26, 1, 5040, 5039, 4611, 2279, 458, 37, 1, 40320, 40319, 38890, 24553, 6996, 891, 50, 1, 362880, 362879, 358018, 268521, 101072, 18043, 1578, 65, 1, 3628800, 3628799, 3612004, 3042210, 1438112, 337210, 40884, 2603, 82, 1

Offset: 1

Alois P. Heinz, Jul 05 2012

			T(3,2) = 5.  All 3! = 6 permutations of {1,2,3} contain an increasing subsequence of length 2 with the exception of 321.
Triangle T(n,k) begins:
     1;
     2,    1;
     6,    5,    1;
    24,   23,   10,    1;
   120,  119,   78,   17,   1;
   720,  719,  588,  207,  26,  1;
  5040, 5039, 4611, 2279, 458, 37,  1;
  ...

Alois P. Heinz, Rows n = 1..55, flattened
Eric Weisstein's World of Mathematics, Permutation Pattern
Wikipedia, Longest increasing subsequence problem
Wikipedia, Young tableau

Columns k=1-10 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.
Row sums give: A003316.
T(2n,n) gives A269021.
Diagonal and lower diagonals give: A000012, A002522, A217200, A217193.
Cf. A047874, A214015.

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, k)-> n! -g(n, k-1, []):
seq(seq(T(n, k), k=1..n), n=1..12);

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}]]]; t[n_, k_] := n! - g[n, k-1, {}]; Table[Table[t[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

T(n,k) = Sum_{i=k..n} A047874(n,i).

T(n,k) = A000142(n) - A214015(n,k-1).

A321273 Sum over all permutations of [n] of the maximum of the lengths of increasing or decreasing subsequences.

Original entry on oeis.org

1, 4, 14, 70, 396, 2628, 20270, 175392, 1686374, 17920528, 208454628, 2629931688, 35774761662, 522351495684, 8149929922408, 135284126840592, 2380119357533974, 44243729657494640, 866599471539160876, 17839886344238238784, 385065445154671172880, 8695565142604747421416

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..60
Wikipedia, Longest increasing subsequence

Cf. A003316, A321274, A321275, A321276, A321277, A321278.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*max(l[1], nops(l)):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

h[l_] := Function[n, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[j > l[[k]], 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]][Length[l]];
f[l_] := h[l]^2 Max[l[[1]], Length[l]];
g[n_, i_, l_] := If[n == 0 || i == 1, f[Join[l, Table[1, {n}]]], g[n, i - 1, l] + g[n - i, Min[i, n - i], Append[l, i]]];
a[n_] := g[n, n, {}];
Table[a[n], {n, 1, 23}] (* Jean-François Alcover, Oct 31 2021, after Alois P. Heinz *)

A321274(n) < A003316(n) < a(n) for n > 1.

A321274 Sum over all permutations of [n] of the minimum of the lengths of longest increasing subsequence and longest decreasing subsequence.

Original entry on oeis.org

1, 2, 10, 46, 274, 1894, 14660, 128648, 1259740, 13540882, 158689006, 2018664332, 27699652406, 407457326286, 6395402111042, 106731605965344, 1887716456363316, 35269257369001618, 694027051724655398, 14346767204627002964, 310852440258761877068, 7045172291061429434354

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..70
Wikipedia, Longest increasing subsequence

Cf. A003316, A321273, A321275, A321276, A321277, A321278.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*min(l[1], nops(l)):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

a(n) < A003316(n) < A321273(n) for n > 1.

A321277 One half of the sum over all permutations of [n] of the absolute difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

Original entry on oeis.org

0, 1, 2, 12, 61, 367, 2805, 23372, 213317, 2189823, 24882811, 305633678, 4037554628, 57447084699, 877263905683, 14276260437624, 246201450585329, 4487236144246511, 86286209907252739, 1746559569805617910, 37106502447954647906, 825196425771658993531

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Cf. A003316, A321273, A321274, A321275, A321276, A321278, A321316.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*abs(l[1]-nops(l))/2:
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

a(n) = (1/2) * Sum_{k=1-n..n-1} abs(k) * A321316(n,k).

A321278 One half of the sum over all permutations of [n] of the squared difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

Original entry on oeis.org

0, 1, 4, 18, 105, 699, 5285, 45128, 431223, 4540775, 52268029, 653096124, 8810538490, 127622293057, 1975379879871, 32537074533872, 568268861724191, 10490690233451583, 204118868130889733, 4174977363687339452, 89554055679215605982, 2010207472655266461533

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Cf. A003316, A321273, A321274, A321275, A321276, A321277, A321316.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*(l[1]-nops(l))^2/2:
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

a(n) = (1/2) * Sum_{k=1-n..n-1} k^2 * A321316(n,k).

A321275 Sum over all permutations of [n] of the product of the lengths of longest increasing subsequence and longest decreasing subsequence.

Original entry on oeis.org

1, 4, 22, 132, 890, 6812, 58422, 555900, 5819658, 66554180, 825839718, 11054124886, 158795559000, 2437248222710, 39809464449676, 689538524084168, 12625142440334342, 243656361772961292, 4943801229819987022, 105212500452414418118, 2343513475564027153128

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..70
Wikipedia, Longest increasing subsequence

Cf. A003316, A321273, A321274, A321276, A321277, A321278.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*l[1]*nops(l):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

A321276 Sum over all permutations of [n] of the length of the longest increasing subsequence raised to the power of the length of the longest decreasing subsequence.

Original entry on oeis.org

1, 3, 20, 174, 1915, 25861, 407691, 7330188, 148016449, 3312032213, 81207824255, 2162810487154, 62125097028962, 1913156511113517, 62839800627095263, 2191735865280260976, 80859575674731497805, 3144804693463679033629, 128550453029684197431607

Offset: 1

Alois P. Heinz, Nov 01 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..70
Wikipedia, Longest increasing subsequence

Cf. A003316, A321273, A321274, A321275, A321277, A321278.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*l[1]^nops(l):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

A321313 Number of permutations of [n] with equal lengths of the longest increasing subsequence and the longest decreasing subsequence.

Original entry on oeis.org

1, 0, 4, 4, 36, 256, 1282, 9864, 99976, 970528, 9702848, 113092200, 1500063930, 20985500212, 305177475748, 4733232671056, 79461918315024, 1427464201289584, 26955955609799728, 531536672155429792, 10980840178654738496, 238597651836121062824, 5446220581860028853936

Offset: 1

Alois P. Heinz, Nov 03 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Column k=0 of A321316.

Cf. A000142, A003316, A321314, A321315.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> `if`(l[1]=nops(l), h(l)^2, 0):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

h[l_] := With[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[j > l[[k]], 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
f[l_] := If[l[[1]] == Length[l], h[l]^2, 0];
g[n_, i_, l_] := If[n == 0 || i == 1, f[Join[l, Table[1, {n}]]], g[n, i - 1, l] + g[n - i, Min[i, n - i], Append[l, i]]];
a[n_] := g[n, n, {}];
Array[a, 25] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

a(n) = n! - 2 * A321314(n).
a(n) = A321315(n) - A321314(n).
a(n) = A321316(n,0).

A321314 Number of permutations of [n] where the length of the longest increasing subsequence is larger than the length of the longest decreasing subsequence.

Original entry on oeis.org

0, 1, 1, 10, 42, 232, 1879, 15228, 131452, 1329136, 15106976, 182954700, 2363478435, 33096395494, 501248446126, 8094778608472, 138112754890488, 2487454752219208, 47344572399516136, 950682668010605104, 20055050996527350752, 442701537970743308588, 10202898078512473893032

Offset: 1

Alois P. Heinz, Nov 03 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..80
Wikipedia, Longest increasing subsequence

Cf. A000142, A003316, A321313, A321315, A321316.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> `if`(l[1] `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

h[l_] := With[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[j > l[[k]], 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
f[l_] := If[l[[1]] < Length[l], h[l]^2, 0];
g[n_, i_, l_] := If[n == 0 || i == 1, f[Join[l, Table[1, {n}]]], g[n, i - 1, l] + g[n - i, Min[i, n - i], Append[l, i]]];
a[n_] := g[n, n, {}];
Array[a, 25] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

a(n) = Sum_{k=1..n-1} A321316(n,k).
a(n) = (n! - A321313(n))/2.
a(n) = A321315(n) - A321313(n).

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

A214152 Number of permutations T(n,k) in S_n containing an increasing subsequence of length k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A321273 Sum over all permutations of [n] of the maximum of the lengths of increasing or decreasing subsequences.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A321274 Sum over all permutations of [n] of the minimum of the lengths of longest increasing subsequence and longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A321277 One half of the sum over all permutations of [n] of the absolute difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A321278 One half of the sum over all permutations of [n] of the squared difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A321275 Sum over all permutations of [n] of the product of the lengths of longest increasing subsequence and longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A321276 Sum over all permutations of [n] of the length of the longest increasing subsequence raised to the power of the length of the longest decreasing subsequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A321313 Number of permutations of [n] with equal lengths of the longest increasing subsequence and the longest decreasing subsequence.

Views

Author