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

 Hints (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)
 OFFSET 0,3 COMMENTS 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] REFERENCES 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] LINKS 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 FORMULA 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 EXAMPLE 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}. MAPLE 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 MATHEMATICA Table[( (n^2)! Product[k!/(n+k)!, {k, 0, n-1}] )^2, {n, 0, 5}] (* Wouter Meeussen, Jan 25 2014 *) CROSSREFS Cf. A039622, A067700. Sequence in context: A141090 A307580 A255268 * A198975 A160300 A024060 Adjacent sequences:  A079399 A079400 A079401 * A079403 A079404 A079405 KEYWORD nonn,easy AUTHOR Dean Hickerson, Jan 06 2003 EXTENSIONS Better name from Wouter Meeussen, Jan 25 2014 STATUS approved

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.

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