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 Stanley4, was proved by Blum1 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.