Problem 1. For an integer let
be the number of elements of order two in the symmetric group
It is clear that
Show that for any integer
we have
Solution. We know that every element of can be written uniquely as a product of disjoint cycles (here “uniquely” means up to the order in which the cycles are written down). We also know that the order of a product of disjoint cycles is the least common divisor of the order of the cycles. So an element of
has order two if and only if it’s a product of disjoint cycles of length two and that’s the number we need to find.
Let
be a product of disjoint cycles of length two. Then obviously Now, there are
ways to choose
and
ways to choose
and
ways to choose
and … finally
ways to choose
So there are
possibilities for and hence
Problem 2. For any integer let
be the number of solutions of the equation
in the symmetric group
where
is the identity element of
It is clear that
and
Show that for any integer
we have
Solution. It is clear that For
let
So
Let
and put
If
then there is
possibilities for
But if
then, since
we have
and hence there will be
possibilities for
So
Problem 3. Let be the sequences defined in Problem 1 and Problem 2, respectively. It is clear that
and so since, by Problem 2,
satisfies the recurrence relation
for all
the sequence
satisfies
for all Prove
using the formula for
given in Problem 1.
Solution. I prove for
even and I leave the proof for odd values of
to the reader. So let
where
is a positive integer. Then, by Problem 1,
Exercise. In the solution of Problem 1, to find the number of possibilities for explain why we divided
by
.