1
$\begingroup$

Find the number of sequences containing $5$ distinct terms $x_1,x_2,x_3,x_4,x_5$ from the set $A=\left\{1,2,3,4....20\right\}$ such that $x_1<x_2>x_3<x_4>x_5$.

My try:

The total number of sequences with $5$ distinct terms is $5!\times \binom{20}{5}$, among which there are $\binom{20}{5}$ strictly increasing sequences and $\binom{20}{5}$ strictly decreasing sequences. But now I am stuck in finding the sequences with $x_1<x_2>x_3<x_4>x_5$ among $5!\times \binom{20}{5}-2\times \binom{20}{5}$

$\endgroup$
3
$\begingroup$

Note that for any set of five distinct numbers, the number of ways of arranging them so that they satisfy the given condition must be the same as for any other five distinct numbers. Thus we really only need to count the number of ways of ordering $\{1,2,3,4,5\}$ to satisfy the given condition.

Note that $5$ has to be either $x_2$ or $x_4$; note also that whichever of $x_2$ or $x_4$ is not $5$, it will have to be either $3$ or $4$.

Suppose $(x_2, x_4) \in \{(4,5),(5,4)\}$; in each case, there are $3!$ ways of arranging the other three numbers. Now suppose $(x_2, x_4) \in \{(3,5),(5,3)\}$; then the $4$ has to go in the outside position next to the position containing the $5$, which leaves $2!$ ways of arranging the other numbers.

Thus the number of arrangements of $\{1,2,3,4,5\}$ satisfying the given condition is $2 \cdot 3! + 2 \cdot 2! = 16$. But then the number of ways of sequences from $\{1,2,3,4,...,20\}$ satisfying the condition will just be

$$16 \binom{20}{5} = \boxed{248,064}$$

$\endgroup$
2
  • $\begingroup$ +1. Editing my answer, silly miss. $\endgroup$
    – cosmo5
    Nov 5 '20 at 8:12
  • $\begingroup$ Happens to the best of us! $\endgroup$
    – A.J.
    Nov 5 '20 at 8:55
1
$\begingroup$

After choosing five numbers, relabel them ${1,\ldots,5}$ from smallest to largest.

Observe now

  • $5$ can only be placed at $x_2$ or $x_4$
  • When $5$ is placed at $x_4$, $4$ can go to $x_2$ or $x_5$ $$ \square < 4 > \square < 5 > \square$$ $$ \square < 3 > \square < 5 > 4$$

These are only two valid ways possible. This corresponds to number of ways $3! + 2! = 8$ (filling ${1,2,3}$ in remaining boxes).

Similarly when $5$ is placed at $x_2$, we have $8$ more ways.

Hence answer is $$16 \cdot \binom{20}{5}$$

Credits to @A.J. for considering all cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.