6
$\begingroup$

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

  • 0
    You don't exactly want a bijection, you want a $2n+1$-to-one mapping, right?2012-08-23
  • 1
    @Gerry: the two sets are not necessarily the sets counted by $\omega(n)$...2012-08-23
  • 0
    @Qiaochu, good point.2012-08-23

1 Answers 1

2

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.

  • 0
    Link didn't work for me.2012-08-23
  • 0
    @Gerry For some reason it stopped working for me earlier soon after I posted, but now works again. Anyway, you could try [this](http://ng-st.esnips.com/file_serve.php?file_id=userfolders/esnips/central/users10/users16/ada/ada3d41d-da8b-46da-ad82-0b2e8b026e4e/fol/6d3725b8-fb54-4a8d-946e-8f93b9d639f8/doc/d1c93565-58d4-487a-a792-8441467f25f6.pdf&key=ba468894e9d971216d2643396d9b8205&ts=1345728340) new link.2012-08-23
  • 0
    Say, what? The new link just gave me some incomprehensible photograph.2012-08-23
  • 0
    @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.2012-08-24