A047874 -id:A047874 - cp's OEIS frontend

A001455 Number of permutations of length n with longest increasing subsequence of length 4.

1, 16, 181, 1821, 17557, 167449, 1604098, 15555398, 153315999, 1538907306, 15743413076, 164161815768, 1744049683213, 18865209953045, 207591285198178, 2321616416280982, 26362085777156567, 303635722412859447, 3544040394934246209, 41881891423602685193

Offset: 4

N. J. A. Sloane

nonn

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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 4..300
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.

Column k=4 of A047874.

Recurrence: (n-4)*(n+2)^2*(n+3)^2*(n+4)*(225*n^5 - 180*n^4 - 1713*n^3 + 1354*n^2 + 3326*n - 1604)*a(n) = (n+2)^2*(6750*n^9 - 4500*n^8 - 128025*n^7 + 28068*n^6 + 758512*n^5 - 184396*n^4 - 1719825*n^3 + 606292*n^2 + 573428*n - 274224)*a(n-1) - (n-1)*(61425*n^10 - 39915*n^9 - 1118034*n^8 + 644778*n^7 + 5929529*n^6 - 4355935*n^5 - 10322152*n^4 + 7841792*n^3 + 4333856*n^2 - 3087760*n - 58944)*a(n-2) + 2*(n-2)^2*(n-1)*(92250*n^8 - 88875*n^7 - 1380300*n^6 + 1835846*n^5 + 4241004*n^4 - 9250339*n^3 + 4259094*n^2 + 1427720*n - 1155840)*a(n-3) - 576*(n-3)^2*(n-2)^3*(n-1)*(225*n^5 + 945*n^4 - 183*n^3 - 2615*n^2 + 1300*n + 1408)*a(n-4). - Vaclav Kotesovec, Mar 15 2014

a(n) ~ 3 * 2^(4*n+9) / (Pi^(3/2) * n^(15/2)). - Vaclav Kotesovec, Mar 15 2014

More terms from Alois P. Heinz, Jul 01 2012

Name of the sequence clarified by Vaclav Kotesovec, Mar 18 2014

A001456 Number of permutations of length n with longest increasing subsequence of length 5.

Original entry on oeis.org

1, 25, 421, 6105, 83029, 1100902, 14516426, 192422979, 2579725656, 35098717902, 485534447114, 6835409506841, 97966603326993, 1429401763567226, 21226755241285022, 320692032888290224, 4926576077469905280, 76913478420068425515, 1219520974164038038455

Offset: 5

N. J. A. Sloane

nonn

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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 5..700 (first 100 terms from Alois P. Heinz)
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.

Column k=5 of A047874.

Recurrence: (n-5)*(n+3)^3*(n+4)^2*(n+6)^2*(11025*n^8 + 25515*n^7 - 286443*n^6 - 161641*n^5 + 2585080*n^4 - 59048*n^3 - 7819612*n^2 + 146328*n + 7254720)*a(n) = (n+3)^2*(606375*n^14 + 6629175*n^13 - 3194685*n^12 - 243068077*n^11 - 448185134*n^10 + 2897169968*n^9 + 6909605819*n^8 - 18854806947*n^7 - 49141228309*n^6 + 52949408689*n^5 + 157003723774*n^4 - 31022236184*n^3 - 177627829824*n^2 - 22499155440*n + 46832450400)*a(n-1) - (n-1)*(11278575*n^15 + 107036370*n^14 - 128493459*n^13 - 3499379232*n^12 - 3757671198*n^11 + 38759610078*n^10 + 60611718946*n^9 - 233170832954*n^8 - 421914005785*n^7 + 715791177016*n^6 + 1483014906497*n^5 - 861954416990*n^4 - 2293879983512*n^3 + 206528474736*n^2 + 1232273843856*n + 13490305056)*a(n-2) + (n-2)^2*(n-1)*(84286125*n^13 + 498481200*n^12 - 2434626540*n^11 - 13242031168*n^10 + 26565838790*n^9 + 116444106688*n^8 - 166166829480*n^7 - 520627558844*n^6 + 548244457053*n^5 + 1265779705376*n^4 - 798189974324*n^3 - 1219994476884*n^2 + 526747368888*n + 238058922240)*a(n-3) - 2*(n-3)^2*(n-2)^2*(n-1)*(116181450*n^11 + 631786995*n^10 - 3196642374*n^9 - 12497984441*n^8 + 40113159004*n^7 + 67582342915*n^6 - 249420026774*n^5 - 74467478051*n^4 + 592968590146*n^3 - 201054848490*n^2 - 142917171372*n - 573108048)*a(n-4) + 14400*(n-4)^2*(n-3)^3*(n-2)^2*(n-1)*(11025*n^8 + 113715*n^7 + 200862*n^6 - 727084*n^5 - 854995*n^4 + 4446427*n^3 + 2445184*n^2 - 7589778*n + 1695924)*a(n-5). - Vaclav Kotesovec, Mar 16 2014

a(n) ~ 9 * 5^(2*n+25/2) / (2^9 * Pi^2 * n^12). - Vaclav Kotesovec, Mar 16 2014

More terms from Alois P. Heinz, Jul 01 2012

Name of the sequence clarified by Vaclav Kotesovec, Mar 18 2014

A001457 Number of permutations of length n with longest increasing subsequence of length 6.

Original entry on oeis.org

1, 36, 841, 16465, 296326, 5122877, 87116283, 1477363967, 25191909848, 434119587475, 7583461369373, 134533482045389, 2426299018270338, 44506885647682026, 830512607486659272, 15764082963927084216, 304295666452406076997, 5971518739677370493811

Offset: 6

N. J. A. Sloane

nonn

In general, for column k of A047874 is a_k(n) ~ (Product_{j=0..k-1} j!) * k^(2*n + k^2/2) / (2^((k-1)*(k+2)/2) * Pi^((k-1)/2) * n^((k^2-1)/2)) [Regev, 1981]. - Vaclav Kotesovec, Mar 18 2014

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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 6..175 (first 100 terms from Alois P. Heinz)
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.
A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115-136.

Column k=6 of A047874.

a(n) ~ 5 * 2^(2*n+6) * 3^(2*n+21) / (Pi^(5/2) * n^(35/2)). - Vaclav Kotesovec, Mar 18 2014

More terms from Alois P. Heinz, Jul 01 2012

Name of the sequence clarified by Vaclav Kotesovec, Mar 18 2014

A001458 Number of permutations of length n with longest increasing subsequence of length 7.

Original entry on oeis.org

1, 49, 1513, 38281, 874886, 18943343, 399080475, 8312317976, 172912977525, 3615907795025, 76340522760097, 1631788075873114, 35378058306185002, 778860477345867008, 17423197016288134608, 396169070839236609236, 9157097111888617643722, 215143361542096212159897

Offset: 7

N. J. A. Sloane

nonn

In general, for column k of A047874 is a_k(n) ~ (Product_{j=0..k-1} j!) * k^(2*n + k^2/2) / (2^((k-1)*(k+2)/2) * Pi^((k-1)/2) * n^((k^2-1)/2)) [Regev, 1981]. - Vaclav Kotesovec, Mar 18 2014

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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 7..150 (first 75 terms from Alois P. Heinz)
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.
A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115-136.

Column k=7 of A047874.

a(n) ~ 6075 * 7^(2*n+49/2) / (32768 * Pi^3 * n^24). - Vaclav Kotesovec, Mar 18 2014

More terms from Alois P. Heinz, Jul 01 2012

Name of the sequence clarified by Vaclav Kotesovec, Mar 18 2014

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.

A054676 Numerator of expected length of longest increasing subsequence of a permutation of length n.

Original entry on oeis.org

1, 3, 2, 29, 67, 2261, 499, 7601, 163673, 3146141, 16688347, 232429801, 1220661809, 1475887019, 96968880223, 5041994433457, 25104916552337, 4417388168138681, 279381762131009, 383174447010300497, 24854210193336894641, 2271390683068712389, 8081231165699623062227

Offset: 1

Eric M. Rains (rains(AT)caltech.edu), Apr 19 2000

			A054676/A054677 = 1/1, 3/2, 2/1, 29/12, 67/24, 2261/720, 499/144, 7601/2016, 163673/40320, 3146141/725760, 16688347/3628800, 232429801/47900160, ... .

Alois P. Heinz, Table of n, a(n) for n = 1..60
A. M. Odlyzko and E. M. Rains, On longest increasing subsequences in random permutations, pp. 439-451 in Analysis, Geometry, Number Theory: The Mathematics of Leon Ehrenpreis, E. L. Grinberg, S. Berhanu, M. Knopp, G. Mendoza and E. T. Quinto, eds., Amer. Math. Soc., Contemporary Math. #251, 2000.

Cf. A047874, A054677.

More terms from Alois P. Heinz, Feb 14 2016

A054677 Denominator of expected length of longest increasing subsequence of a permutation of length n.

Original entry on oeis.org

1, 2, 1, 12, 24, 720, 144, 2016, 40320, 725760, 3628800, 47900160, 239500800, 276756480, 17435658240, 871782912000, 4184557977600, 711374856192000, 43553562624000, 57926238289920000, 3649353012264960000, 324386934423552000, 1124000727777607680000

Offset: 1

Eric M. Rains (rains(AT)caltech.edu), Apr 19 2000

Alois P. Heinz, Table of n, a(n) for n = 1..60
A. M. Odlyzko and E. M. Rains, On longest increasing subsequences in random permutations, pp. 439-451 in Analysis, Geometry, Number Theory: The Mathematics of Leon Ehrenpreis, E. L. Grinberg, S. Berhanu, M. Knopp, G. Mendoza and E. T. Quinto, eds., Amer. Math. Soc., Contemporary Math. #251, 2000.

Cf. A047874, A054676.

More terms from Alois P. Heinz, Feb 14 2016

A141824 Antidiagonals of table A047888 (which counts longest increasing subsequences and pattern avoidances).

Original entry on oeis.org

1, 2, 4, 9, 24, 75, 269, 1095, 5039, 26084, 150356, 952526, 6553011, 48553418, 385693800, 3277413802, 29741002168, 287555932433, 2952769116993, 32079033571080, 367336668735826, 4419518218479215, 55733223965845539, 735448682261126767, 10142738983005750681

Offset: 1

Alford Arnold, Jul 08 2008

nonn

Note that:
A000108 avoids string "123"
A005808 avoids string "1234"
A047889 avoids string "12345"
Note also that the left half and central diagonal of A047888 are partial sums of table A047874.

			We can write A141824(n) = 1 2 4 9 24 ... because A047888 begins
  1;
  1,  1;
  1,  2,  1;
  1,  5,  2,  1;
  1, 14,  6,  2,  1;
etc.

Cf. A000108 (Catalan numbers), A005808, A047889, A047874.

a(12)-a(25) from Alois P. Heinz, Apr 10 2012

A239432 Number of permutations of length n with longest increasing subsequence of length 8.

Original entry on oeis.org

1, 64, 2521, 79861, 2250887, 59367101, 1508071384, 37558353900, 927716186325, 22904111472825, 568209449266202, 14216730315766814, 359666061054003144, 9216708503647774264, 239524408949706575548, 6317740398995612513164, 169207499997274346326579, 4602911809939402715164066

Offset: 8

Vaclav Kotesovec, Mar 18 2014

nonn

In general, for column k of A047874 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)) [Regev, 1981].

Vaclav Kotesovec, Table of n, a(n) for n = 8..135
A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115-136.

Cf. A047874, A001453, A001454, A001455, A001456, A001457, A001458.

a(n) ~ 1913625 * 2^(6*n+77) / (Pi^(7/2) * n^(63/2)).

A245665 Number of permutations of length n with longest increasing subsequence of length 9.

Original entry on oeis.org

1, 81, 3961, 153341, 5213287, 164060352, 4927007100, 143938455225, 4142847526101, 118504614869214, 3389618010035458, 97376389179852540, 2818543211543628620, 82388635477750176388, 2436180769576352799396, 72958306889459609898731, 2214789502139053994814716

Offset: 9

Alois P. Heinz, Jul 28 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 9..60

Column k=9 of A047874.

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-> g(n-9, min(n-9, 9), [9]):
seq(a(n), n=9..30);

cp's OEIS Frontend

A001455 Number of permutations of length n with longest increasing subsequence of length 4.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A001456 Number of permutations of length n with longest increasing subsequence of length 5.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A001457 Number of permutations of length n with longest increasing subsequence of length 6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A001458 Number of permutations of length n with longest increasing subsequence of length 7.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

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

A054676 Numerator of expected length of longest increasing subsequence of a permutation of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A054677 Denominator of expected length of longest increasing subsequence of a permutation of length n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A141824 Antidiagonals of table A047888 (which counts longest increasing subsequences and pattern avoidances).

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A239432 Number of permutations of length n with longest increasing subsequence of length 8.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A245665 Number of permutations of length n with longest increasing subsequence of length 9.