The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 a(n) = ( (n^2)!*BarnesG(n+1)^2/BarnesG(2*n+1) )^2, where BarnesG(n) = A000178(n). - G. C. Greubel, May 04 2021 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 *) Table[((n^2)!*BarnesG[n+1]^2/BarnesG[2n+1])^2, {n, 0, 10}] (* G. C. Greubel, May 04 2021 *) PROG (Magma) [n eq 0 select 1 else ( Round(Factorial(n^2)*(&*[ Gamma(j+1)/Gamma(n+j+1): j in [0..n-1]])) )^2: n in [0..10]]; // G. C. Greubel, May 04 2021 (Sage) [( factorial(n^2)*product( gamma(j+1)/gamma(n+j+1) for j in (0..n-1) ) )^2 for n in (0..10)] # G. C. Greubel, May 04 2021 CROSSREFS Cf. A000178, 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 October 28 04:24 EDT 2021. Contains 348313 sequences. (Running on oeis4.)