# 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