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

 

Logo

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

Index entries for sequences related to Young tableaux.

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.

License Agreements, Terms of Use, Privacy Policy. .

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