**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 .