The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A079402 Number of permutations of n^2 distinct integers free of any monotonic increasing or decreasing (n+1)-subsequence. 2
1, 1, 4, 1764, 577152576, 491609948246960400, 2794390432234620616607526201600, 225695005480541203944756162668572542540719673600, 487587121568323060029971679617336086880787102621519060769151477760000 (list; graph; refs; listen; history; text; internal format)



Conjecture: this is equal to the number of permutations of n^2 distinct integers free of any monotonic increasing or decreasing (n+1)-subsequence. (By the Erdos-Szekeres Theorem, every permutation of n^2+1 distinct integers has such a subsequence.) - Joseph Myers, Jan 04 2003

Claude Lenormand (claude.lenormand(AT)free.fr) confirms this conjecture. - Jan 06, 2002.

a(n) is equal to the number of permutations of n^2 distinct integers having no monotonic sequences of length more than n. [Michael Lugo (mlugo(AT)math.upenn.edu), Mar 25 2009]

By Robinson-Schensted correspondance, equals the square of the number of square standard Young tableaux. [Wouter Meeussen, Jan 25 2014]


Martin Gardner, Riddles of The Sphinx, MAA, NML vol. 32, 1987, p. 6.

D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting ang Searching, Addison-Wesley, 1973, p. 69. [From Michael Lugo (mlugo(AT)math.upenn.edu), Mar 25 2009]


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

Stanley Rabinowitz (proposer), Richard Stanley (solver), Advanced Problem 5641, Amer. Math. Monthly 76 (1969), no. 10, 1153.

Vincent Vatter, An Erdős--Hajnal analogue for permutation classes, arXiv:1511.01076 [math.CO], 2015.

Eric Weisstein's World of Mathematics, Erdos-Szekeres Theorem

Wikipedia, Robinson-Schensted correspondence

Index entries for sequences related to Young tableaux.


a(n) = ((n^2)! * Product_{k=0..n-1} k!/(n+k)!)^2.

a(n) = (A067700(n)/2)^2 = A039622(n)^2.

a(n) ~ Pi * n^(2*n^2+11/6) * exp(n^2 + 1/6) / (A^2 * 2^(4*n^2-7/6)), where A is the Glaisher-Kinkelin constant A074962. - Vaclav Kotesovec, Dec 17 2016


The case n=2: only a(2)=4 of the 24 permutations of {1,2,3,4} are devoid of any 3-term increasing or decreasing subsequence, namely {2,1,4,3}, {2,4,1,3}, {3,1,4,2}, {3,4,1,2}.


a:= n-> ((n^2)! *mul(k!/(n+k)!, k=0..n-1))^2:

seq(a(n), n=0..8);  # Alois P. Heinz, Jan 25 2014


Table[( (n^2)! Product[k!/(n+k)!, {k, 0, n-1}] )^2, {n, 0, 5}] (* Wouter Meeussen, Jan 25 2014 *)


Cf. A039622, A067700.

Sequence in context: A141090 A307580 A255268 * A198975 A160300 A024060

Adjacent sequences:  A079399 A079400 A079401 * A079403 A079404 A079405




Dean Hickerson, Jan 06 2003


Better name from Wouter Meeussen, Jan 25 2014



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 24 18:11 EST 2020. Contains 338616 sequences. (Running on oeis4.)