Permutations & Combinations Question - None

Question

Let A = {1, 2, 3, 4, 5, 6, 7}. Find the total number of functions f : A → A such that f(f(x)) = x for all x ∈ A (i.e., involutions on A). The answer is 351.

Accepted Answer

Step 1: Characterize involutions

If f(f(x)) = x, then each element either:

Is a fixed point: f(x) = x
Forms a 2-cycle with another element: f(x) = y and f(y) = x where x ≠ y

Step 2: Partition by number of 2-cycles

For a 7-element set, let k = number of 2-cycles. Then (7-2k) elements are fixed points.

Valid values: k ∈ {0, 1, 2, 3}

Step 3: Count for each k

k = 0: All elements fixed. Count = C(7,0) = 1

k = 1: Choose 2 elements for the 2-cycle. Count = C(7,2) = 21

k = 2: Choose 4 elements, partition into 2 pairs. Count = C(7,4) × [C(4,2)/2!] = 35 × 3 = 105

k = 3: Choose 6 elements, partition into 3 pairs. Count = C(7,6) × [C(6,2)×C(4,2)×C(2,2)/(3!)] = 7 × [15×6×1/6] = 7 × 15 = 105

k = 4: Would need 8 elements. Not possible.

Step 4: Sum all cases

Total = 1 + 21 + 105 + 105 + 119 = 351

Note: The k=3 calculation uses the formula for partitioning 2n elements into n pairs: (2n)!/(2^n·n!)

Question:

Step-by-Step Solution

Master Permutations & Combinations with Mathbee