Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
yeah, let's say number of a certain type of permutations –  Alex M Sep 10 '11 at 1:41

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.