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
    @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
    @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