0,3

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 S. Myers (jsm(AT)polyomino.org.uk), Jan 04 2003

Claude Lenormand (claude.lenormand(AT)free.fr) confirms that 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. [From Michael Lugo (mlugo(AT)math.upenn.edu), Mar 25 2009]

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]

Eric Weisstein's World of Mathematics, Link to a section of The World Of Mathematics

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) = (A067700(n)/2)^2.

Sequence in context: A030253 A160225 A141090 this_sequence A160300 A024060 A004815

Adjacent sequences: A079399 A079400 A079401 this_sequence A079403 A079404 A079405

nonn,easy

Dean Hickerson (dean.hickerson(AT)yahoo.com), Jan 06 2003