Permutations of numbers $1, 2, 3,\dots,n$ How many permutations do the numbers $1, 2, 3,\dots,n$ have,
a) in which there is exactly one occurrence of a number being greater than the adjacent number on the right of it?
b) in which there are exactly two occurrences of a number being greater than the adjacent number on the right of it?
 A: a) As mentioned by @algamest, in order to get a desired permutation, you would divide the numbers into two subsets of sizes $k$ and $n-k$, where $k$ can be any integer from $1$ to $n-1$, and list each subset in increasing order. For each size $k$, there are $n\choose k$ possible subsets.  However, one of them won't work, namely the subset ($1,2,..,k$).
Therefore, the total number of permutations is $$\sum_{k=1}^{n-1}({n\choose k}-1)=(\sum_{k=1}^{n-1}{n\choose k})-(n-1)$$ In general, it can be shown that $\sum_{k=1}^{n-1}{n\choose k}=2^n-2$ so the solution can be simplified to $$2^n-1-n$$
b) Here we will need to divide the numbers into 3 subsets of sizes $k$, $j$, and $n-j-k$, where $k$ can be any integer from $1$ to $n-2$, and $j$ can be any integer from $1$ to $n-k-1$. Again, we would list the three subsets in order, each in increasing order. For each size $k$ and $j$, there are ${n\choose k}{n-k\choose j}$ possible combinations of subsets.
Here, however, it is a bit more complicated to calculate the number of subset combinations that won't work. There are two possible reasons that a collection of subsets wouldn't work. Either the values in subset 1 are all less than all the values in subset 2, or the values in subset 2 are all less than all the values in subset 3.
Let's first look at the first case.  For each possible set of values for $j,k$, there are ${n\choose j+k}$ combinations of which numbers are included in the first two subsets.  For each of these combinations, there is one way of splitting that won't work. So we must remove ${n\choose j+k}$ possibilities.
Now let's look at the second case.  For each possible set of values for $j,k$, there are ${n\choose k}$ combinations of which numbers are included in the last two subsets, and again for each of these combinations, there is one split up that won't work. So we must remove ${n\choose k}$ possibilities.
We now must consider the cases that have both problems and have been subtracted twice, and therefore must be added once back in. For each possible set of values for $j,k$ there is only one way to have both problems (smallest $k$ numbers in first set, next smallest numbers in second set).
Putting this together, for each possible set of values for $j,k$ we must add $-{n\choose j+k}-{n\choose k}+1$.  This gives us a permutation total of $$\sum_{k=1}^{n-2}\sum_{j=1}^{n-k-1}({n\choose k}{n-k\choose j}-{n\choose j+k}-{n\choose k}+1)$$
A: The Eulerian number $\left\langle n\atop m\right\rangle$ is the number of permutations of $[n]$ with $m$ ascents; this is clearly the same as the number of permutations of $[n]$ with $m$ descents. Thus, we want $\left\langle n\atop 1\right\rangle$ for the first problem and $\left\langle n\atop 2\right\rangle$ for the second. The Eulerian numbers satisfy the recurrence
$$\left\langle n\atop m\right\rangle=(n-m)\left\langle {n-1}\atop {m-1}\right\rangle+(m+1)\left\langle {n-1}\atop m\right\rangle\;,$$
with initial values $\left\langle 0\atop 0\right\rangle=1$, $\left\langle 0\atop m\right\rangle=0$ if $m>0$, and $\left\langle n\atop m\right\rangle=0$ if $m<0$. From this (or by other means) it is not hard to determine that
$$\left\langle n\atop 1\right\rangle=2^n-n-1\tag{1}$$
and thence that
$$\left\langle n\atop 2\right\rangle=3^n-(n+1)2^n+\frac{n(n+1)}2\;;\tag{2}$$
the resulting sequences are OEIS A000295 and OEIS A000460, respectively.
The derivation of $(2)$ from $(1)$ is quite tedious; verifying it from the recurrence, on the other hand, is straightforward.
To derive the recurrence, let $\pi=p_1p_2\ldots p_{n-1}$ be any permutation of $[n-1]$. By inserting $n$ into any of the $n$ available slots, we can generate $n$ permutations of $n$. Suppose that we insert $n$ after $p_k$. The number of descents remains unchanged if $k=n-1$, or if $p_k>p_{k+1}$; otherwise it increases by $1$. Thus, the permutations of $[n]$ with $k$ descents arise in two ways:


*

*from permutations $p_1p_2\ldots p_{n-1}$ of $[n-1]$ with $m$ descents, by placing $n$ at the end or after some $p_k$ such that $p_k>p_{k+1}$, and  

*from permutations $p_1p_2\ldots p_{n-1}$ of $[n-1]$ with $m-1$ descents, by placing $n$ at the beginning or after some $p_k$ such that $p_k<p_{k+1}$.


There are $\left\langle {n-1}\atop m\right\rangle$ permutations of $[n-1]$ with $m$ descents, and in each there are $m+1$ places to insert the $n$ produce a permutation of $[n]$ with $m$ descents, so the first case accounts for $(m+1)\left\langle {n-1}\atop m\right\rangle$ of the permutation of $[n]$ with $m$ descents.
There are $\left\langle {n-1}\atop {m-1}\right\rangle$ permutations of $[n-1]$ with $m-1$ descents, and in each there are $n-m$ places to insert the $n$ produce a permutation of $[n]$ with $m$ descents, so the second case accounts for $(n-m)\left\langle {n-1}\atop {m-1}\right\rangle$ of the permutation of $[n]$ with $m$ descents. Combining the two cases yields the recurrence.
