Skip to main content
better link
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Such sequences do exist. It suffices to generate a large enough random sequence. If you check Dan Romik's book, https://www.math.ucdavis.edu/~romik/download-book.phpThe Surprising Mathematics of Longest Increasing Subsequences, Theorem 1.1 states that

$$\frac {\ell_n} {\sqrt n} \to 2,$$

where $\ell_n$ is an expected length of increasing subsequence in a random permutation of size $n$. The same for decreasing. Therefore, for large enough $n$ there must exist a sequence with both increasing and decreasing sequences of lengths at most $5 \sqrt n$, otherwise:

$$2 E[\ell_n] = E[|decr_n| + |incr_n|] \ge 5 \sqrt n,$$

which contradicts the theorem.

Such sequences do exist. It suffices to generate a large enough random sequence. If you check https://www.math.ucdavis.edu/~romik/download-book.php, Theorem 1.1 states that

$$\frac {\ell_n} {\sqrt n} \to 2,$$

where $\ell_n$ is an expected length of increasing subsequence in a random permutation of size $n$. The same for decreasing. Therefore, for large enough $n$ there must exist a sequence with both increasing and decreasing sequences of lengths at most $5 \sqrt n$, otherwise:

$$2 E[\ell_n] = E[|decr_n| + |incr_n|] \ge 5 \sqrt n,$$

which contradicts the theorem.

Such sequences do exist. It suffices to generate a large enough random sequence. If you check Dan Romik's book, The Surprising Mathematics of Longest Increasing Subsequences, Theorem 1.1 states that

$$\frac {\ell_n} {\sqrt n} \to 2,$$

where $\ell_n$ is an expected length of increasing subsequence in a random permutation of size $n$. The same for decreasing. Therefore, for large enough $n$ there must exist a sequence with both increasing and decreasing sequences of lengths at most $5 \sqrt n$, otherwise:

$$2 E[\ell_n] = E[|decr_n| + |incr_n|] \ge 5 \sqrt n,$$

which contradicts the theorem.

Source Link
user114966
user114966

Such sequences do exist. It suffices to generate a large enough random sequence. If you check https://www.math.ucdavis.edu/~romik/download-book.php, Theorem 1.1 states that

$$\frac {\ell_n} {\sqrt n} \to 2,$$

where $\ell_n$ is an expected length of increasing subsequence in a random permutation of size $n$. The same for decreasing. Therefore, for large enough $n$ there must exist a sequence with both increasing and decreasing sequences of lengths at most $5 \sqrt n$, otherwise:

$$2 E[\ell_n] = E[|decr_n| + |incr_n|] \ge 5 \sqrt n,$$

which contradicts the theorem.