MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi Guys. The problem here seems like a homework, but I think that it is not that easy.It comes from a theorem I recently proved.The content of the theorem is not important, the issue is that I have no idea how to counting the number of the index sets that satisfy the constraint the theorem restricted.

Theorem: Suppose a sequence of integers has distinct $n^2+1$ numbers and have exactly t one monotone subsequence of length $n+1$,(Note Erdos Szekeres Theorem guarantees the existence of the unique subsequence.),the index set $C$ of the unique monotone subsequence of length n+1 must satisfy following properties.

(Constraint of index set)

Let $C_i$ denotes the $i$th element of the index set $C$ where $2 \leq i \leq n$.Then

(0) $ C_1 < C_2 < \dots < C_i < C_{n+1}$

(1) $j< C_1 <(j-1)n+1$

(2) $ij < C_i<(j-1)n+i+(i-2)(n-j)$

(3) $ nj+1 < C_{n+1} < (j-1)n + n + 1 + (n-1)(n-j) $

where $j$ is any integer for $1$ to $n$ .

(End of the Constraint)

The meaning of the $j$ is that if the elements of $C$ satisfies the group of constraints above for any $j$, we say that it satisfies the constraints.

END of the theorem.


How many index sets C satisfy the constraint above are there?

Or could someone provide an approximation of the numbers of qualified index set $C$s. Even the ration of the qualified index sets to the trivial bound $ { n^2 +1 \choose n+1 }$ would be very desirable.

IF you are reading this, thank you for you patient for at least arriving here. I would also thank for anyone that might suggest some people might know a method to the problem.

share|cite|improve this question
Your last constraint expression might be easier to grok if written as n^2+1-(n-j). Also, there have been a few questions asked on related matters recently on specialized combnations, which is what your sets appear to be. You might check those out. (Link to be provided later.) Gerhard "Search Engines Stole My Memory" Paseman, 2012.08.10 – Gerhard Paseman Aug 10 '12 at 22:04
Here is the first in a chain of links that might be of interest.… . My answer has a comment from me which contains the next link. My guess is that parking functions and Gessel-Viennot (somewhere after the third link) will be relevant to your problem. Gerhard "Ring Around The Web References" Paseman, 2012.08.10 – Gerhard Paseman Aug 11 '12 at 2:12
Hi Gerhard. Thanks very much about your links.It seems that I need time to dig it out. – WangYao Aug 11 '12 at 6:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.