2
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very nice and excellent exposition. Upvoted. $\endgroup$ Sep 17, 2013 at 3:38
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you give me a combinatorial proof ? $\endgroup$ Sep 19, 2013 at 15:17
  • $\begingroup$ I think Brian M. Scott's answer should do it, shouldn't it? Excellent work, fits the question and not difficult to read. $\endgroup$ Sep 19, 2013 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .