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.
Problem
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.
