Problem 2134

$\binom{4030}{2015} - 2015$

In the following, by a subsequence of the given sequence of positive integers we mean a sequence obtained by choosing entries from the original sequence and retaining the order of the choices.

There are $\binom{4030}{2015}$ ways of choosing $2015$ numbers from the given sequence. We assume that the given sequence is lined up from left to right, and we define a new sequence $f(1), f(2), \dots, f(4030)$ by setting $f(i) = j$ and $f(j) = i$ for $i < j$ if the number on the $i$-th spot from the left equals the number on the $j$-th spot from the left in the original sequence. If there exists an $i$ for which $0 < f(i) - i < 2015$, then there must exist at least $2015$ numbers occupying $1$st, $2$nd $\dots$, $(i-1)$-th spots from the left or $(f(i)+1)$-th, $(f(i)+2)$-th, $\dots$, $4030$-th spots from the left on the original sequence, and therefore, there are at least $2015$ ways of choosing $2014$ numbers. Suppose we consider one such sequence of $2014$ numbers, and we insert the number lying at the $i$-th spot from left in the original sequence to this sequence at the correct spot to get another subsequence consisting of $2015$ elements and do the same by inserting the number lying at the $f(i)$-th spot from left in the original sequence to the sequence at the correct spot to obtain two half-sequences. But it is clear these half-sequences are identical. Therefore, the number of distinct half-sequences is at most $\binom{4030}{2015} - 2015$ if there exists $i$ satisfying $0 < f(i) - i < 2015$. The same conclusion holds if there exists $i$ satisfying $0 < i - f(i) < 2015$.

In the sequel, we assume that for each $i$, $1 \le i \le 4030$, $|f(i) - i| \ge 2015$ is satisfied. Then, we have $f(2015 + i) \le i$ ($i = 1, 2, \dots, 2015$), from which we obtain inductively $f(2016) = 1$, $f(2017) = 2$, $\dots$, $f(4030) = 2015$. By symmetry, we may assume that the original sequence is $1, 2, 3, \dots, 2015, 1, 2, 3, \dots, 2015$. Call this sequence $A$. Now suppose two distinct subsequences formed by selecting $2015$ elements from $A$ give the same half-sequence. Select one integer lying on the same spot as an entry of half-sequence but chosen from different location from $A$, and call this number $n$. If this $n$ was chosen from the left-half of $A$, then the entries in the half-sequence lying to the left of $n$ must form a subsequence of $1, 2, \dots, n-1$, and the entries in the half-sequence lying to the right form a subsequence of $n+1, n+2, \dots, 2015$. Consequently, we conclude that this half-sequence must be $1, 2, \dots, 2015$. On the other hand, suppose we consider the way of choosing $2015$ elements from $A$ to form the half-sequence $1, 2, \dots, 2015$. If $n$ is chosen from the left-half of $A$, then we must choose any number less than $n$ also from the left-half of $A$, and if $n$ is chosen from the right-half of $A$, then any number greater than $n$ must also be chosen from the right half of $A$. Therefore, there are $2016$ ways of choosing the half-sequence $1, 2, \dots, 2015$ from $A$, and we conclude that the number of distinct half-sequences is $\binom{4030}{2015} - 1 = 4030C_{2015-1}$, which gives the answer we seek.