Problem:
Let be a positive integer, and be a function such that for every .
a) Prove that the number is even.
b) Find the number of all functions with the required property.
Problem:
Let be a positive integer, and be a function such that for every .
a) Prove that the number is even.
b) Find the number of all functions with the required property.
Solution:
a.
Let and . Since and , it follows easily that if then either or . Moreover, we obtain for .
Further, if , then , i.e. . Also, gives and then . Therefore for which means that splits into disjoint quadruples. In particular, the number is even.
b.
Let and be a function with the desired property. Set . We note that and, in particular, . Hence for either or . This means that the quadruple is uniquely determined by a pair of distinct numbers from — or . Therefore induces a pairing of into ordered pairs.
Conversely, any pairing of into ordered pairs defines a function with the required properties by setting
It remains to count the number of the pairings of into ordered pairs. Ordering all pairs of a given pairing one after another (this can be done in ways) we obtain a permutation of the numbers . This gives classes of "equivalent" permutations of elements. Therefore the required number is equal to .