KAIST Discrete Math Seminar

We prove combinatorially that the largest power of 2 in the number of involutions of length n is equal to [n/2]-2[n/4] +[(n+1)/4]. We show that the smallest period of the sequence of odd factors in the number of involutions modulo 2^s is 2^s+1 for s>2. We also consider the largest power of 2 in the number of even and odd involutions.