3
$\begingroup$

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?

  • 0
    yeah, le$t$'s say number of a cer$t$ain type of permutations2011-09-10

3 Answers 3

0

Such permutations are concatenations of a decreasing sequence of blocks every one of which is an increasing permutation. Equivalently, those are permutations that avoid patterns $132$ and $213$, or, put differently, reversals of layered permutations. Why? Partition your permutation into ascending runs (maximal blocks of consecutive ascents). Every such block consists of a sequence of ascents by 1. Replace each such block by a single entry in the same relative order as the order of the blocks. Now the resulting permutation can have no ascents (since every ascent would be by at least 2, which is forbidden), so it must be the decreasing permutation, i.e. the anti-identity. Therefore, the blocks are completely determined by the list of their sizes, so you are essentially counting compositions with positive parts.

Yet another way to see this is recursively. Let the number of such permutations of length $n$ be $f(n)$. Obviously, $f(1)=1$. Suppose you have a permutation $\pi$ of length $n$ that satisfies this property. Where could you insert $n+1$ to preserve it? Only at the beginning and immediately after $n$ (i.e. you either start a new block or extend the current leftmost block). Therefore, $f(n+1)=2f(n)$ for all $n\ge 1$.

3

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

3

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.