$\underline{\text { Ans } A .}$

Numbers $1,2,3, \ldots, N$ are written in a row in such an order that if a number $i$ is written somewhere (not in the first place), then at least one of the numbers $i+1$ and $i-1$ will be found somewhere to its left. In how many ways can this be done?
Let the first position be occupied by the number $k$. Note that if $k>1$, then the numbers $k-1, k-2, \ldots, 1$ are in our permutation in descending order (if moving from left to right). Indeed, by the condition, to the left of the number 1 must be 2, to the left of 2 must be 1 or 3, that is, 3, to the left of 3 must be 2 or 4, that is, 4, and so on. Similarly, if $k<N$, the numbers $k+1, k+2, \ldots, N$ are in ascending order, since to the left of $N$ must be $N-1$, to the left of $N-1$ must be $N-2$, and so on. Therefore, any of the permutations under consideration is uniquely determined by the set of positions occupied by the numbers $1,2, \ldots, k-1$ (such positions may not exist at all if $k=1$, that is, for the permutation $1,2, \ldots, N$). The number of these sets is equal to the number of subsets of a set of $N-1$ elements - all positions except the first, which is $2^{N-1}$. The number of elements in the subset uniquely determines the number $k$ that stands in the first position.

## Answer

$2^{N-1}$ ways.

Send a comment