Show that the difference of the number of cycles of even and odd permutations is $(-1)^n (n-2)!$, using a bijective mapping (combinatorial proof).

Suppose to convert a permutation from odd to even we always flip 1 and 2. Then the difference can be easily calculated.

Thus, if I can find the number of cycles of all even permutations of $[n]$ that have $\{1,2\}$ in the same cycle., I can compute the difference. Can somebody show me a way?

up vote 2 down vote accepted

This isn’t quite a bijective proof in the usual sense, since one of the quantities involved can be negative. However, it uses a bijection to reduce the problem to a very simple counting problem, so I think that it qualifies. I’ve left the final step to you.

Let $$E_n=\{\langle\pi,\sigma\rangle:\pi\text{ is an even permutation of }n\text{ and }\sigma\text{ is a cycle of }\pi\}$$ and $$O_n=\{\langle\pi,\sigma\rangle:\pi\text{ is an odd permutation of }n\text{ and }\sigma\text{ is a cycle of }\pi\}\;;$$ we want to show that $|E_n|-|O_n|=(-1)^n(n-2)!$.

Let $E_n^*=\{\langle\pi,\sigma\rangle\in E_n:|\sigma|\le n-2\}$ and $O_n^*=\{\langle\pi,\sigma\rangle\in O_n:|\sigma|\le n-2\}$. For any $p=\langle\pi,\sigma\rangle\in E_n^*\cup O_n^*$ let $i_p$ and $j_p$ be the two smallest elements of $[n]$ not in $\sigma$, and define

$$f_n\big(\langle\pi,\sigma\rangle\big)=\big\langle\pi(i_pj_p),\sigma\big\rangle\;.$$

then $f_n$ is an involution on $E_n^*\cup O_n^*$ mapping $E_n^*$ to $O_n^*$ (and vice versa), and $|E_n^*|=|O_n^*|$, so we need only show that $|E_n\setminus E_n^*|-|O_n\setminus O_n^*|=(-1)^n(n-2)!$. Let $E_n^{**}=E_n\setminus E_n^*$ and $O_n^{**}=O_n\setminus O_n^*$.

The members of $E_n^{**}\cup O_n^{**}$ are the $\langle\pi,\sigma\rangle\in E_n\cup O_n$ such that $\sigma$ is an $n$-cycle or an $(n-1)$-cycle, and in each case we must have $\pi=\sigma$. Thus,

$$E_n^{**}\cup O_n^{**}=\{\langle\sigma,\sigma\rangle:\sigma\text{ is a cycle of length }n\text{ or }n-1\}\;.$$

Now just count the $n$-cycles and $(n-1)$-cycles, categorize them as even or odd, and do a little arithmetic, and you’ll find that indeed $|E_n^{**}|-|O_n^{**}|=(-1)^n(n-2)!$.

Added: I forgot to mention that this answer combines an idea from this answer of mine with a comment on that answer by joriki.

  • Very nice and excellent exposition. Upvoted. – Marko Riedel Sep 17 '13 at 3:38

Here is an answer using generating functions that may interest you. Recall that the sign $\sigma(\pi)$ of a permutation $\pi$ is given by $$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$$ where the product ranges over the cycles $c$ from the disjoint cycle composition of $\pi$.

It follows that the combinatorial species $\mathcal{Q}$ that reflects the signs and the cycle count of the set of permutations is given by $$\mathcal{Q} = \mathfrak{P}(\mathcal{V}\mathfrak{C}_1(\mathcal{Z}) +\mathcal{U}\mathcal{V}\mathfrak{C}_2(\mathcal{Z})) +\mathcal{U}^2\mathcal{V}\mathfrak{C}_3(\mathcal{Z}) +\mathcal{U}^3\mathcal{V}\mathfrak{C}_4(\mathcal{Z}) +\mathcal{U}^4\mathcal{V}\mathfrak{C}_5(\mathcal{Z}) +\cdots)$$ where we have used $\mathcal{U}$ to mark signs and $\mathcal{V}$ for the cycle count.

Translating to generating functions we have $$Q(z, u, v) = \exp\left(v\frac{z}{1} + vu\frac{z^2}{2} + vu^2\frac{z^3}{3} + vu^3\frac{z^4}{4} + vu^4\frac{z^5}{5} +\cdots\right).$$ This simplifies to $$Q(z,u,v) = \exp\left(\frac{v}{u} \left( \frac{zu}{1} + \frac{z^2 u^2}{2} + \frac{z^3 u^3}{3} + \frac{z^4 u^4}{4} + \frac{z^5 u^5}{5} + \cdots \right)\right) \\ = \exp\left(\frac{v}{u} \log \frac{1}{1-uz}\right) = \left(\frac{1}{1-uz}\right)^{\frac{v}{u}}.$$

Now the two generating functions $Q_1(z, v)$ and $Q_2(z, v)$ of even and odd permutations by cycle count are given by $$Q_1(z,v) = \frac{1}{2} Q(z,+1,v) + \frac{1}{2} Q(z,-1,v) = \frac{1}{2}\left(\frac{1}{1-z}\right)^v +\frac{1}{2}\left(\frac{1}{1+z}\right)^{-v}$$ and $$Q_2(z,v) = \frac{1}{2} Q(z,+1,v) - \frac{1}{2} Q(z,-1,v) = \frac{1}{2}\left(\frac{1}{1-z}\right)^v -\frac{1}{2}\left(\frac{1}{1+z}\right)^{-v}.$$

We require the quantity $$G(z, v) = \left.\frac{d}{dv} (Q_1(z,v)-Q_2(z,v))\right|_{v=1} \\= \left.\frac{d}{dv} \left(\frac{1}{1+z}\right)^{-v}\right|_{v=1} = - \left.\log \frac{1}{1+z} \left(\frac{1}{1+z}\right)^{-v}\right|_{v=1} = -(1+z)\log \frac{1}{1+z}.$$

Finally extracting coeffcients from this generating function we obtain $$- n! [z^n] (1+z)\log \frac{1}{1+z} = - n! \left(\frac{(-1)^n}{n} + \frac{(-1)^{n-1}}{n-1}\right) \\= - n! (-1)^{n-1} \left(-\frac{1}{n} + \frac{1}{n-1}\right) = n! (-1)^n \frac{n-(n-1)}{n(n-1)} \\= n! (-1)^n \frac{1}{n(n-1)} = (-1)^n (n-2)!$$ This concludes the proof. I do think this is rather pretty.

  • Can you give me a combinatorial proof ? – UnadulteratedImagination Sep 19 '13 at 15:17
  • I think Brian M. Scott's answer should do it, shouldn't it? Excellent work, fits the question and not difficult to read. – Marko Riedel Sep 19 '13 at 16:22

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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