The number of permutations of $\{1,2,\ldots,n\}$ that have exactly one ascent (rise).

Question

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?

Answer 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.

Answer 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}

Answer 3

Imagine trying to build a permutation of length n which has exactly one ascent. If the set of numbers before the ascent point is A and the set of numbers after the ascent point is B, the order that we place the elements of A and B in the permutation is unique. Therefore, the permutation can be identified uniquely using a subdivision of n into 2 sets A and B.

(We just choose a subset A of {1, ..., n}, give B the rest, write down elements of A in descending order, and then write elements of B in in descending order.)

However, not all such divisions can lead to a valid permutation. If all elements of A are greater than all elements of B, the permutation built this way will not have an ascent. There are n+1 ways to choose such an A. (Because it means choosing A = {k, k+1, k+2, ..., n}) (Including the cases where A is empty or B is empty.)

Answer 4

Viewing permutations as words, a permutation with exactly one ascent is the concatenation of two decreasing sequences with each symbol in $[n] = \{1,2,\ldots,n\}$ occurring exactly once. Call these sets of elements in these sequences $A$ and $B$.

For each permutation, construct a binary string $x$ such that $x_1 = 1$ iff $1 \in A$, and for $2,\ldots,n$, $x_i = 1$ iff $i-1$ and $i$ are in different sets.

EDIT: Should be $1 \in A$, not $1 \in B$.