3
$\begingroup$

You can construct a sequence of 5 numbers $(a,b,c,d,e)$ with the following rule:

$a\in\{1\}$

$b\in\{2,3\}$

$c\in\{3,4,5\}$

$d\in\{4,5,6,7\}$

$e\in\{5,6,7,8,9\}$

How many sequence are strictly ordered?

I tried to solve this problem and with some empirical attempt I found that the answer is 42. Are anyone able to give an elegant proof about that?

$\endgroup$
3
  • 3
    $\begingroup$ The Catalan numbers are surely lurking here.... $\endgroup$ Nov 20 '15 at 23:05
  • 1
    $\begingroup$ If you stop at $a$, $b$, $c$, or $d$, the counts are $1$, $2$, $5$, $14$ respectively. $1, 2, 5, 14, 42$ are the first $5$ Catalan numbers. So I think there is a very high probability that Barry is right, but it's a bit too late in the evening for me to figure out why. $\endgroup$
    – Rob Arthan
    Nov 20 '15 at 23:47
  • 1
    $\begingroup$ I find an elegant solution using Catalan numbers. Thank you! $\endgroup$
    – bojica
    Nov 21 '15 at 0:11
3
$\begingroup$

The Catalan number $Cn$ is the number of monotonic lattice paths along the edges of a grid with $n × n$ square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards. Counting such paths is equivalent to counting our sequence as I show in the following picture: enter image description here

Indeed we have $C_5=42$.

$\endgroup$
1
$\begingroup$

Here's an idea. (Though not necessarily one that I'd call "elegant," it might still be an improvement.) For brevity, I will refer to strictly ordered sequences as "good," and the rest as "bad."

If $d=4,$ then there are $5$ distinct ways that $a,b,c$ could have been chosen such that regardless of our choice of $e,$ the sequence is bad. The remaining possible choice of $a,b,c$ will necessarily yield a good sequence. Hence, there are $5$ good sequences such that $d=4.$

If $d=5,$ there are $3$ possible ways to choose $a,b,c$ such regardless of our choice of $e$, the sequence is bad. For each of the remaining three possible ways to choose $a,b,c,$ there are $4$ ways to choose $e$ so that the sequence is good. This gives us $12$ good sequences such that $d=5.$

If $d=6,$ there is only one way to choose $a,b,c$ such that regardlessof pur choice of $e$, the sequence is bad. For each of the remaining $5$ ways to choose $a,b,c,$ there are $3$ ways to choose $e$ so that the sequence is good. This gives us $15$ good sequences such that $d=6$.

The $d=7$ case is similar to the $d=6$ case, and gives us $10$ more good sequences.

Hence, there are $42$ good sequences.

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