Find the number of ways to arrange the numbers $\{1,2,...,n\}$ in a row so that for all number $x$:

Question

Find the number of ways to arrange the numbers $\{1,2,...,n\}$ in a row so that for all number $x$ (except for the very left one), at least one of the numbers $x\pm 1$ is to the left of $x$ (not necessarily adjacent).

Hey all. I've been thinking about this question for a while, and to be honest, I don't really know how to approach this. These are the possible answers:

1) $2^{n-1}$

2) $\sum^4_{k=0}\binom{n-1}{k}$

3) $\binom{n}{4} +n+\binom{n-1}{2}$

I would be happy to get some help on this question, I feel like I'm lost... Thanks in advance.

Answer 1

Let's start constructing the sequence from left to right. Our first (leftmost) choice has no restrictions. Let's say it's $k$. The second choice has to be either $k-1$ or $k+1$. If it's $k-1$, the third choice has to be either $k-2$ or $k+1$; if the second choice is $k+1$, the third choice has to be either $k-1$ or $k+2$.

A pattern begins to emerge, and we have a better way to describe the rule in terms of constructing the sequence: the first $i-1$ numbers in the sequence must form a contiguous block, and so the $i$th number must be either the number immediately preceding or immediately following the block. That is to say, each choice after the first is one of at most two choices: down or up. Some thought confirms that this rule is equivalent to the rule as you stated it.

Now if we choose $k$ as the leftmost number, we have to then place $n-k$ "ups" and $k-1$ "downs" in any order, which can be done in $\binom{n-1}{k-1}$ ways. Thus the total number of ways is $\sum_{k=1}^n\binom{n-1}{k-1} = 2^{n-1}$.

Answer 2

Start small. How many arrangements are there when $n =1$? $n= 2$?

You can then gradually try larger sets, for example $n = 3,$ then $n= 4.$ Maybe $n = 5.$

You may notice that not every number can occur in every position in the list. Which numbers are excluded from which positions? Can you deduce a reason why?

Eventually you should try to find a pattern that continues as $n$ gets larger so that you can apply it as a general rule. Then you can count the number of sequences that fit that rule.

That's a rather general way to approach a problem like this, but it tends to be effective. I think it is effective in this case.

---

By the way, the pattern I observe for this particular problem is that if you have a solution for a particular $n$, you can extend it to a solution for $n+1$ just by appending $n+1$ at the end of the list; or you can add $1$ to every number in the list and then append $1$ at the end. And there's no other way to do it except by inserting the last element at the top or bottom of the range, because in order to go in the middle there would have to be a gap between the numbers already in the list, and at least one of the numbers wouldn't satisfy the $x+1, x-1$ rule.