A combinatorial approach to the power of 2 in the number of involutions (Q1957962)

We denote the set of permutations of size \(n\) by \(S_n\). Let \(p\) be any prime number and \(n\) be any positive integer. We denote the number of permutations \(\pi\in S_n\) such that \(\pi^p=1\) by \(\tau_p(n)\). We denote the largest integer \(k\) such that \(p^k\) divides \(n\) by \(\text{ord}_p(n)\). In 1951, \textit{S. Chowla, I. N. Herstein}, and \textit{W. K. Moore} [Can. J. Math. 3, 328--334 (1951; Zbl 0043.25904)] showed that \[ \text{ord}_2(\tau_2(n))\geq \lfloor n/2\rfloor-\lfloor n/4\rfloor. \] More generally, in 1994, \textit{M. Grady} and \textit{M. Newman} [Contemp. Math. 166, 265--273 (1994; Zbl 0822.20026)] proved that \[ \text{ord}_p(\tau_p(n))\geq \lfloor n/p\rfloor-\lfloor n/p^2\rfloor. \] Later, in 1999, \textit{H. Ochiai} [Hokkaido Math. J. 28, No. 1, 71--85 (1999; Zbl 0930.11084)] showed that \[ \text{ord}_2(t_n)=\lfloor n/2\rfloor-2\lfloor n/4\rfloor+\lfloor(n+1)/4\rfloor, \] where \(t_n\) is the number of involutions in \(S_n\). In this paper, the authors provide combinatorial proof for the result of Grady and Newman and result of Ochiai. Moreover, the authors study \(\tau_2(t_n^e)\) and \(\tau_2(t_n^o)\), where \(t_n^e\) (\(t_n^o\)) is the number of even (odd) involutions in \(S_n\).