# Alternating Sequences of Length five

A finite sequence of numbers $$(a_1, \dots, a_n)$$ is said to be $$alternating$$ if $$a_1>a_2,\hspace{.2cm} a_2a_4,\hspace{.2cm} a_4 $$\mbox{or } a_1a_3,\hspace{.2cm} a_3a_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.

• I think the basic idea is, given $5$ distinct integers, find how many ways there are to arrange them into an alternating list. Then just multiply this result by ${}_{20}\mathrm{C}_5$. – K.defaoite Sep 21 '20 at 15:56
• I think different combinations can give different results. – Sayantan Sep 21 '20 at 16:00

## 1 Answer

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

• Doesn't seem correct suppose selection of 5 is 1,2,3,4,5 then for alternating patternof second type a/q OP ,let a2 and a4 be 3 and 5 now let a3 be 4 clearly inequality is violated. – Aditya Prakash Sep 22 '20 at 21:13
• @AdityaPrakash you are right, that was overseeing on my part. I'll correct it up. – Fawkes4494d3 Sep 22 '20 at 22:18