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.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email