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

A267436 Number of self-inverse permutations of [2n] with longest increasing subsequence of length n.

Original entry on oeis.org

1, 1, 5, 31, 265, 2446, 26069, 294386, 3628517, 46938514, 645978814, 9265791393, 139408562319, 2174338555026, 35259402634616, 590187761512336, 10209739522685893, 181678453872654154, 3326776921054665350, 62485419303819431072, 1203772979032614462448

Offset: 0

Alois P. Heinz, Jan 15 2016

nonn

Also the number of 2n-length words w over n-ary alphabet {a1,a2,...,an} such that for every prefix z of w we have #(z,a1) >= #(z,a2) >= ... >= #(z,an) >= 1, where #(z,x) counts the letters x in word z. The a(2) = 5 words of length 4 over alphabet {a,b} are: aaab, aaba, abaa, aabb, abab.

			a(2) = 5: 1432, 2143, 3214, 3412, 4231.

Vaclav Kotesovec, Table of n, a(n) for n = 0..70 (terms 0..55 from Alois P. Heinz)

Cf. A047884, A267433, A293128.

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]), add(
                g(n-i*j, i-1, [l[], i$j]), j=0..n/i)):
a:= n-> g(n$2, [n]):
seq(a(n), n=0..25);

h[l_] := With[{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_] := If[n == 0 || i == 1, h[Join[l, Table[1, {n}]]], Sum[g[n - i*j, i - 1, Join[l, Table[i, {j}]]], {j, 0, n/i}]];
a[n_] := g[n, n, {n}];
a /@ Range[0, 25] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

a(n) = A047884(2n,n).

A126065 Triangle of numbers read by rows: T(n,k) = number of permutations sigma of (1,2,...,n) with n - {length of longest increasing subsequence in sigma} = k (0<=k<=n-1).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Mar 01 2007

T(n,k) is the number of permutations in S_n with Ulam distance from the identity equal to k.

Mirror image of triangle in A047874.

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

P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.
See A047874 for further references, etc.

Alois P. Heinz, Rows n = 1..60, flattened
E. Irurozki, Sampling and learning distance-based probability models for permutation spaces, PhD Dissertation, Department of Computer Science and Artificial Intelligence of the University of the Basque Country, 2015.
E. Irurozki, B. Calvo, J. Ceberio, and J. A. Lozano, Mallows model under the Ulam distance: a feasible combinatorial approach, 2014.
Ekhine Irurozki, B. Calvo, J. A. Lozano, PerMallows: An R Package for Mallows and Generalized Mallows Models, Journal of Statistical Software, August 2016, Volume 71, Issue 12. doi: 10.18637/jss.v071.i12

T(2n,n) gives A267433.

A230341 Number of permutations of [2n] in which the longest increasing run has length n.

Original entry on oeis.org

1, 1, 16, 293, 5811, 133669, 3574957, 109546009, 3788091451, 145957544981, 6201593613645, 288084015576169, 14525808779580645, 790129980885855401, 46120599397152203401, 2875600728737862162481, 190740227037467026439611, 13411608375592255857753781

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304.

Cf. A267433.

a:= proc(n) option remember; `if`(n<5, [1, 1, 16, 293, 5811][n+1],
      (2*(n+1)*(26615475780292426*n^4 +2862121494132556*n^3
        -240402559504315639*n^2 +79488454158677567*n
        +119546195807549142)*a(n-1)
      -n*(406022528821033256*n^4 -1031369150352151615*n^3
        +11028208356875758*n^2 -1654923205028490137*n
        +3900125789057762682)*a(n-2)
      +2*(n-1)*(421508861354067594*n^4 -1543365451253363033*n^3
        -602924004257000736*n^2 +6654606478117189961*n
        -5221800341103267066)*a(n-3)
      -4*(2*n-7)*(n-2)*(26655798868586248*n^3 +401269836638339496*n^2
        -2000296275137853913*n +2124466470996744981)*a(n-4)
      -8*(n-3)*(n-5)*(2*n-7)*(2*n-9)*(8655617328093650*n
        -14323734034655567)*a(n-5)) / (n*(n+2)*(13307737890146213*n^2
        -43906954139467620*n +22672341406878775)))
    end:
seq(a(n), n=0..25);

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1];
a[n_] := T[2n, n];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

a(n) = A008304(2*n,n).
Recurrence (of order 3): n*(n+2)*(12*n^7 - 101*n^6 + 355*n^5 - 668*n^4 + 631*n^3 - 71*n^2 - 344*n + 174)*a(n) = (n+1)*(48*n^9 - 272*n^8 + 453*n^7 - 10*n^6 - 518*n^5 - 741*n^4 + 4090*n^3 - 5810*n^2 + 3444*n - 720)*a(n-1) - 2*n*(2*n - 3)*(60*n^8 - 277*n^7 + 365*n^6 - 59*n^5 - 549*n^4 + 1619*n^3 - 2101*n^2 + 1228*n - 268)*a(n-2) + 4*(n-1)*(2*n - 5)*(2*n - 3)*(12*n^7 - 17*n^6 + n^5 + 12*n^4 - 91*n^3 + 101*n^2 - 12*n - 12)*a(n-3). - Vaclav Kotesovec, Jul 16 2014
a(n) ~ 2^(2*n+1/2)* n^(n+1) / exp(n). - Vaclav Kotesovec, Jul 16 2014

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

A267436 Number of self-inverse permutations of [2n] with longest increasing subsequence of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A126065 Triangle of numbers read by rows: T(n,k) = number of permutations sigma of (1,2,...,n) with n - {length of longest increasing subsequence in sigma} = k (0<=k<=n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A230341 Number of permutations of [2n] in which the longest increasing run has length n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula