Sloane's OEIS A000295 counts the number of $n$-permutations with exactly one ascent. For example $a(3)=4$ because we have: $1\wedge32$, $21\wedge3$, $2\wedge31$, $31\wedge2$ where I have marked the unique ascent with $\wedge$.
The same sequence also counts the number of length $n$ binary words that contain at least two $1$'s. For example $a(3)=4$ because we have: $011, 101, 110, 111.$
Is there a simple bijection between these two classes?
The formula for the sequence is $a(n) = 2^n – n – 1$. I see how this counts the number of such binary words. Is there a combinatorial derivation of this formula demonstrating that it counts the number of such n-permutations?
Both the exponential and ordinary generating functions of the sequence are given. Again, I understand their symbolic derivation for enumeration of such binary words but can these functions be derived symbolically by considering the structure of such n-permutations?
Best Answer
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.