Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


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.