The number of permutations of $\{1,2,\ldots,n\}$ that have exactly one ascent (rise).
Solution 1:
Let $f(n,k)$ count the number of permutations in $S_n$ with exactly $k-1$ ascents. I claim that $$\tag 1 f(n,k)=(n-k+1) f(n-1,k-1)+k f(n-1,k)$$
If we prove this, putting $k=2$ gives $f(n,2)=n-1+2 f(n-1,2)$, i.e. if $x_n$ denotes the number of permutations of $n$ with exactly one ascent, $x_n-2x_{n-1}=n-1$. This then can be used to prove the formula say by induction, or by using generating functions. Se let's try to prove $(1)$.
Suppose we have a permutation of $n-1$ letters with $k-1$ ascents. Picture it as $k$ monotone blocks $B_1,\ldots,B_k$. Then we may introduce $n$ in exactly $k$ ways such that no ascent is added, namely first in each of the $k$ blocks. Now suppose we have a permutation of $n-1$ letters with $k-2$ ascents. Then we may introduce $n$ in $n-k+1$ ways to add exactly one ascent, namely after any element of each of the $k-1$ blocks that is not the leading element.
In the first case, we're obtaining in a permutation in $S_n$ where $n$ is placed in the string $\dots a_i n a_{i+1}\dots$ with $a_i<a_{i+1}$. In the second case, we're obtaining a permutation where $n$ is placed in the string $\dots a_i na_{i+1}\dots$ and $a_i > a_{i+1}$. These are the only two possible cases we face when looking at a permutation, the above simply observes we're splitting $S_n$ into this two cases, noting each fiber in the surjection has exactly $k$ or $n-k+1$ elements, which proves the claim.
Solution 2:
We use the fact that we can get the same recurrence relation $a(n) = a(n-1) + 2^{n-1} - 1$ for both cases.
- In case of the permutations, we get this in the following way:
If n is the first element of the permutation, there must be exactly one ascent among the others. This gives us the a(n-1) term.
If n is not the first element, then the element before this is less than it. This itself adds an ascent. So there must be no other ascent. If we fix which elements come before n and which come after, their order is fixed (each of these sets must be in decreasing order). So for each of the other (n-1) elements, we choose which side of n it is on, giving $2^{n-1}$ to the count. We have to exclude the case where all of them come after, because we have already said that n is not the first element.
- In case of the binary words, we get this in the following way:
If the first element is 0, then the others must have at least two ones. This gives the a(n-1) term.
If the first element is 1, then the others can be anything except for the string with all zeros.
Now, we can use the similar way of getting the recurrence relation to get a bijection.
To get from binary words to permutations, do this:
if the first letter is 0, then in the permutation the first element is n. Now recursively go down to the (n-1) case.
if the first letter is 1, then for each of the other letters, if $a_i$ is 1 then (i-1) comes before n in the permutation. Else (i-1) comes after n in the permutation. Given this partition, the permutation is well defined.
We can easily see how to invert this.
Let me take an example for this:
Suppose I start with the binary string 011010. This will corresspond to a 6-item permutation. Let us find it.
The first letter is 0, so in the permutation the first letter is 6.
Next letter is 1. So the permutation of {1, 2, 3, 4, 5} that follows 6 is found in the following way.
Consider the string 1010. This means that: 1 will come before 5 2 is after 5 3 is before 5 4 is after 5
So the permutation of {1, 2, 3, 4, 5} is {3, 1, 5, 4, 2}. Add 6 at the beginning to get {6, 3, 1, 5, 4, 2}