

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 ErdosSzekeres 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 RobinsonSchensted 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, AddisonWesley, 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Å‘sHajnal analogue for permutation classes, arXiv:1511.01076 [math.CO], 2015.
Eric Weisstein's World of Mathematics, ErdosSzekeres Theorem
Wikipedia, RobinsonSchensted correspondence
Index entries for sequences related to Young tableaux.


FORMULA

a(n) = ((n^2)! * Product_{k=0..n1} 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^27/6)), where A is the GlaisherKinkelin 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 3term 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..n1))^2:
seq(a(n), n=0..8); # Alois P. Heinz, Jan 25 2014


MATHEMATICA

Table[( (n^2)! Product[k!/(n+k)!, {k, 0, n1}] )^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



