# Partial recurrence relation for the number of permutations in $S_n$ which have a square root.

I ran into this problem the other day. The proof is supposed to be done by exhibiting an explicit bijection between two sets, without using induction, recurrence, or generating functions.

Denote by $\omega(n)$ the number of permutations $\sigma\in S_n$ so that $\sigma$ has a square root (that is, there exists $\tau\in S_n$ so that $\tau^2 = \sigma$). Prove that $\omega(2n+1) = (2n+1)\omega(2n)$.

-
You don't exactly want a bijection, you want a $2n+1$-to-one mapping, right? –  Gerry Myerson Aug 23 '12 at 7:13
@Gerry: the two sets are not necessarily the sets counted by $\omega(n)$... –  Qiaochu Yuan Aug 23 '12 at 7:17
@Qiaochu, good point. –  Gerry Myerson Aug 23 '12 at 7:23

The problem features as exercise 59 in chapter 3 of Miklos Bona's Combinatorics of permutations.

The solution to the exercise is on page 337 of the book, which is not included in the Google preview but can be found here. The proof is due to Dennis White.

-
Link didn't work for me. –  Gerry Myerson Aug 23 '12 at 13:09
@Gerry For some reason it stopped working for me earlier soon after I posted, but now works again. Anyway, you could try this new link. –  Ragib Zaman Aug 23 '12 at 13:27
Say, what? The new link just gave me some incomprehensible photograph. –  Gerry Myerson Aug 23 '12 at 23:17
@Gerry The link most likely expired, the website only gives temporary links for downloading the document. The original link is working fine from several computers I've tried, but just in case it still doesn't work I've sent the pdf to your work email. –  Ragib Zaman Aug 24 '12 at 3:03