EngineeringRise

The number of functions f from 1, 2, 3, 4, 5, 6 to itself such that f(f(x)) = x for every x is

Answer: 76 Status: Verified (T3). Checked by code and independent solves on 2026-11-20.

Solution

  1. If f(f(x)) = x for all x, f is its own inverse, so it is a bijection that splits the set into fixed points and 2-cycles (swaps).
  2. Number of swaps k = 0, 1, 2, 3 gives 1, C(6,2) = 15, C(6,2) C(4,2)/2 = 45 and C(6,2) C(4,2)/6 = 15 functions.
  3. Total = 1 + 15 + 45 + 15 = 76.

Fast method

Count involutions by number of swaps: 1 + 15 + 45 + 15 = 76 (recurrence a(n) = a(n-1) + (n-1) a(n-2): 1, 2, 4, 10, 26, 76).

Expected time: about 170 seconds. Difficulty: hard.

Topic page: Functions: one-one, onto and composition

Test your answers now

Report an error

Think the question, answer or a step is wrong? One tap tells us. We check it and publish the correction.