Counting Permutations in S₂ₙ and S₂ₙ₊₁

Let α(n) denote the number of perfect square permutations in the symmetric group Sₙ. The conjecture α(2n+1) = (2n+1) α(2n), provided by Stanley[4], was proved by Blum[1] using a generating function. This paper presents a combinatorial proof for this conjecture. At the same time, we demonstrate that all permutations with an even number of even cycles in both S₂ₙ and S₂ₙ₊₁ can be categorized into three distinct types that correspond to each other.