Let $$A\_n=\{(x\_1,x\_2,x\_3,\cdots,x\_n):x\_i \in [q] \text{ for } i \in [n], x\_1 < x\_2, x\_2 > x\_3, x\_3 < x\_4, \cdots , (-1)^{n}x\_{n-1} < (-1)^{n} x\_n\}.$$ What is the cardinality of $A\_n$?


I have 2 observations. First, let $$B\_n=\{(x\_1,x\_2,x\_3,\cdots,x\_n):x\_i \in [q] \text{ for } i \in [n], x\_1 \leq \frac{q}{2}, x\_2 > \frac{q}{2}, x\_3 \leq \frac{q}{2}, \cdots\}.$$ We have $B\_n \subset A\_n$, so $|A\_n| \geq |B\_n| \geq (\frac{q}{2}-1)^n$.


Second, let $\boldsymbol{x}=(x\_1,x\_2,x\_3,\cdots,x\_n)$ be a uniform random variable in $\mathbb{F}\_q^n$, and event $E\_i$ represents $(-1)^{i+1}x\_i<(-1)^{i+1}x\_{i+1}$. We have $$Pr(E\_i)=\frac{1}{2}, Pr(\boldsymbol{x}\in A\_n)=Pr(E\_1 E\_2 \cdots E\_{n-1}).$$ If $E\_i$'s were independent, then $Pr(\boldsymbol{x}\in A\_n)=(\frac{1}{2})^{n-1}$, i.e. $|A\_n| = (\frac{1}{2})^{n-1}q^{n}$. However, $E\_i$'s are not independent.


**My question is**, can we find an upper bound of $|A\_n|$? Say, can we prove $|A\_n| \leq (\frac{3}{4})^{n-1}q^{n}$?



Upper bound of the number of oscillatory sequences
In the terminology of Chapter 3 of *Enumerative Combinatorics*,
vol. 1, second ed., you are asking for the value of the strict order
polynomial of the zigzag poset $Z\_n$ at $q$ (see Exercise
3.66). Equivalently, it is equal to $(-1)^n\Omega\_{Z\_n}(-q)$, where
$\Omega\_{Z\_n}$ is the ordinary order polynomial. The number of linear
extensions of $Z\_n$ is the Euler number $E\_n$. It follows that for
fixed $n$, $A\_n \sim \frac{E\_n}{n!} q^n$. Moreover, it is well known
that $\frac{E\_n}{n!} \sim 2\left( \frac{2}{\pi}\right)^{n+1}$.


