Number of a certain type of permutations

Question

I'm trying to count the number of permutation $\pi:\{1,\ldots,n\}\rightarrow\{1,\ldots,n\}$ such that $\pi(i+1)\leq\pi(i)+1$ for all $1\leq i\leq n-1$. From an inductive argument it seems to me that this number should be $2^{n-1}$. Could you help me to find a bijective proof, please?

Answer 1

A bijective proof isn’t the easiest way to go $-$ Ross Millikan has shown you an easier argument $-$ but if you’re required to produce one, here’s a start.

Call your permutations almost decreasing. For each almost decreasing permutation $\pi$ let $U(\pi) =$ $\{i:\pi(i+1)=\pi(i)+1\} \subseteq \{1,2,\dots,n-1\}$; $U(\pi)$ is the set of indices at which $\pi$ is about to increase. Clearly $U(\pi)$ is uniquely determined by $\pi$. In other words, $U$ is a function from $D$, the set of almost decreasing permutations, to $\wp(I)$, where $I=\{1,\dots,n-1\}$; clearly $\wp(I)$ has cardinality $2^{n-1}$, so to finish the proof you ‘just’ have to show that $U$ is actually a bijection.

The easier part is showing that $U$ is a surjection. Suppose, for example, that $n=5$ and $V = \{1,3,4\}$. To find a $\pi\in D$ such that $U(\pi)=V$, start with the descending permutation $(54321)$. We want $\pi$ to increase from index $1$ to index $2$, and also from index $3$ through index $5$; this suggests simply reversing the segment consisting of positions $1$ and $2$ and the segment consisting of positions $3$ through $5$ to get $\pi=(45123)$. A quick check shows that indeed $U(\pi)=V$. What you need to do is generalize from this example; this shouldn’t be too hard to do.

The harder part is showing that $U$ is injective, i.e., that if $\pi$ and $\varphi$ are almost descending permutations, and $U(\pi)=U(\varphi)$, then $\pi=\varphi$.

Hint: Given a set $V\subseteq I$ and a $\pi \in D$ such that $U(\pi)=V$, let $m = \min (I \setminus V)$, and show that the first $m$ elements of $\pi$ must be the same as the first $m$ elements of the descending permutation $(n\dots 21)$, but in the opposite order. (What happens if $I \setminus V = \varnothing$?)

This won't give you the complete argument, but it’s a good start.

Answer 2

If $N(n)$ is the number of permutations of $n$ objects satisfying $\pi(i+1)\leq\pi(i)+1$, we can show that $N(n)=2^{n-1}$. If $\pi(1)=n$, you can append any of the $N(n-1)=2^{n-2}$ permutations and have a legal one. If $\pi(1)=1$, the only legal permutation is the identity. If $\pi(1)=k \in (1, n)$, you have to append all the numbers from $k+1$ through $n$, then you can have any permutation of the numbers $1$ through $k-1$, which is $2^{k-2}$ of them. So $N(n)=1 + \sum_{i=2}^n2^{i-2}=2^{n-1}$