Permutation of numbers in a specific order.

Question

How to calculate number of permutations from $1$ to $N$ such that for some $j$ these properties hold : $$ P(i)>P(i-1)\;\;\; \ $$ $$ P(i) > P(i+1)\;\;\; \ $$ For $N=3$ it can be $(1,3,2)$ For $N=4$ it can be $(1,3,4,2)$.

Answer 1

HINT: If, as your later question suggests, you require that $2\le j\le N-1$, then you are trying to count the permutations of $\{1,\ldots,N\}$ that increase from position $1$ to a maximum at some position $j<N$ and then decrease to position $N$.

It never hurts to collect some numerical data. For $N=3$ there are just $2$ acceptable permutations, $\langle 1,3,2\rangle$ and $\langle 2,3,1\rangle$, since the $3$ clearly has to go in the middle. What about $N=4$? We must have the $4$ in position $2$ or position $3$. If it’s in position $2$, we can have $\langle 1,4,3,2\rangle$, $\langle 2,4,3,1\rangle$, or $\langle 3,4,2,1\rangle$, and if it’s in position $3$, we can have $\langle 1,2,4,3\rangle$, $\langle 1,3,4,2\rangle$, or $\langle 2,3,4,1\rangle$.

For $N=5$ the maximum of $5$ must be in position $2,3$, or $4$, but instead of counting the possibilities for those positions separately, let’s see if we can find a way to count them all at once. We’ll have to put $1,2$, or $3$ of the other $4$ numbers before the $5$. Say we decide to put the $1$ and $3$ before the $5$ and the $2$ and $4$ after it; do we have any further choice in how we arrange these numbers? No: the once before the $5$ must be in increasing order, and the ones after the $5$ must be in decreasing order, so that we get the permutation $\langle 1,3,5,4,2\rangle$. Once we decide which numbers go before the $5$, we’ve completely determined the permutation: those numbers must be arranged in increasing order, and the remaining numbers, the ones that go after the $5$, must be arranged in decreasing order. We can put any non-empty proper subset of $\{1,2,3,4\}$ before the $5$: non-empty, since we require at least one number before the $5$, and proper, because we need to leave at least one number to go after the $5$. The set $\{1,2,3,4\}$ has $4$ elements, so it has $2^4$ subsets. One of those subsets, however, is the empty set, and another is the whole set $\{1,2,3,4\}$; we can’t use either of those as the set of numbers before the $5$, so we’re left with $2^4-2=14$ subsets that we can use, and they give rise to the following $14$ permutations:

$$\begin{align*} &\langle 1,5,4,3,2\rangle,\langle 2,5,4,3,1\rangle,\langle 3,5,4,2,1\rangle,\langle 4,5,3,2,1\rangle,\\ &\langle 1,2,5,4,3\rangle,\langle 1,3,5,4,2\rangle,\langle 1,4,5,3,2\rangle,\langle 2,3,5,4,1\rangle,\langle 2,4,5,3,1\rangle,\langle 3,4,5,2,1\rangle,\\ &\langle 1,2,3,5,4\rangle,\langle 1,2,4,5,3\rangle,\langle 1,3,4,5,2\rangle,\langle 2,3,4,5,1\rangle \end{align*}$$

Now try to generalize the reasoning that I just employed in the case $N=5$ to get a formula for the number of acceptable permutations in terms of $N$.