The number of SDR of (n-1)-element sets
Task number: 3997
Consider the system of all \( (n-1) \)-element subsets of the set \( \{1, \ldots, n \} \). How many systems of distinct representatives exist for this set system?
Solution
Denote \( A_i = \{1, \ldots, n \} \setminus i \). Every system of different representatives, where the set \( A_i \) is represented by an element \( r (A_1) \in A_i \) corresponds to the permutation \( (r (A_1), r (A_2),…, r (A_n)) \) without fixed points and vice versa.
Answer
This set system has \(c(n)\) different SDRs, where \(c(n) \) is the solution of the cloakroom problem.
