Question 2 (20 marks) An involution on a set X is a bijection f : X gt; X such that f o f = id. Equivalently, the orbit graph of an involution...

Question in the picture.

Discrete Structures 2.

MATH 340 in McGill.

Question 2 (20 marks)An involution on a set X is a bijection f : X —> X such that f o f = id. Equivalently, the orbit graph of an involution consists only of self-loops and cycles of length 2. An examplewith X = {1, 2, 3,4, 5, 6, 7} is given by the following table. 1 2 3 4 5 6 7f(x) 3 5 1 4 2 7 6Let an be the number of involutions on a set with n elements. (a) Find a recurrence for the sequence (anlnzo- (b) Use your recurrence to find a closed form for the exponential generating functionof that sequence.