Alternating Sequences of Length five

Question

A finite sequence of numbers $(a_1, \dots, a_n)$ is said to be $alternating$ if $$ a_1>a_2,\hspace{.2cm} a_2<a_3,\hspace{.2cm} a_3>a_4,\hspace{.2cm} a_4<a_5, \dots $$ $$ \mbox{or } a_1<a_2,\hspace{.2cm} a_2>a_3,\hspace{.2cm} a_3<a_4,\hspace{.2cm} a_4>a_5, \dots $$ How many alternating sequences of length $5$, with distinct numbers $a_1,a_2, \dots, a_5$ can be formed such that $a_i \in \{1,2,\dots,20\}$ for $i=1, \dots, 5$?

Source: ISI BMATH, BSTAT Entrance Exa, 2020: https://fractionshub.com/i-s-i-b-stat-b-math-2020/ (Problem 8)

Tried this question in the exam but failed. Any help will be truly appreciated.

Answer 1

Let us choose any $5$ numbers $b_1,b_2,b_3,b_4,b_5$ from $\{1,2,\cdots, 20\}$ such that $$b_1<b_2<b_3<b_4<b_5$$ We can do this in $N=\binom{20}5$ ways. For each of these $N$ ways, we need to find how many alternating sequences can be made out of $b_1,b_2,b_3,b_4,b_5$.

Now, for a sequence $a_1,a_2,a_3,a_4,a_5$ to be an alternating sequence of the second type in the question, we need $$a_2>a_1,a_3 \text{ and } a_4>a_3,a_5 $$

i.e.
1. $a_2$ has at least two elements in the set $\{a_i| 1\le i \le 5\}$ less than $a_2$
2. $a_4$ has at least two elements in the set $\{a_i| 1\le i \le 5\}$ less than $a_4$

So, to make an alternating sequence of the second type out of $b_1,b_2,b_3,b_4,b_5$ (note that $b_i<b_j \iff i<j$ by our choice of naming)

$a_2 \in \{b_3,b_4,b_5\}, \ a_4 \in \{b_3,b_4,b_5\}\implies $ We have $3$ options for $a_2$ and since $a_2\ne a_4$, only $2$ remaining choices for $a_4$.
Thus $a_2,a_4$ can be chosen in $3.2=6$ ways.

• If one of $a_2,a_4$ is chosen to be $b_3$, then the two elements on either sides of it $\underline{\text{need to be}}$ $b_1$ and $b_2$, so in such a case, we can have two places for $b_3$ to be in the alternating sequence, as $a_2$ or as $a_4$, in either case, the left and right elements of $b_3$ can be $(b_1,b_2)$ or $(b_2,b_1)$, and the remaining two elements $b_4,b_5$ having a strict order between are automatically assigned as $a_5,a_4$ respectively or $a_1,a_2$ respectively, correspondingly as $b_3$ is assigned as $a_2$ or $a_4$.
  Thus, if $b_3\in\{a_2,a_4\}$, we have $2\times 2=4$ ($2$ for $b_3$, $2$ for $b_1$ and $b_2$) choices to form an alternating sequence.
• If $a_2$ and $a_4$ are from the set $\{b_4,b_5\}$, then the remaining elements $b_1,b_2,b_3$ all being smaller than them can be assigned to $a_1,a_3,a_5$ however we want, thus we have to assign one value each from $\{b_1,b_2,b_3\}$ to $\{a_1,a_3,a_5\}$, which can be done in $3!=6$ ways, and one value each from $\{b_4,b_5\}$ to $\{a_2,a_4\}$ which can be done in $2!=2$ ways, which, being independent choices, can be multiplied to give a total for $6\times 2=12$ choices for this case.

So there are $12+4=16$ alternating sequences of the second type for each choice of $5$ distinct numbers $b_1,\cdots,b_5$, i.e. there are $16\times \binom{20}5$ alternating sequences of the second type.

Similarly, try to find the number of alternating sequences of the first type in the question (by trying to find a set of rules like 1. and 2. above and counting the number of ways) and add these two numbers.