Self-Inverting Relations Challenge Solved!

24 Sep, 2016

Challenge 4 has been solved by Henry Spece!

Challenge 4. (From Class 9) How many self-inverting relations, R: N_k → N_k, are there? (Where N_k is the set of all non-negative integers less than k, and a relation is self-inverting if R = R^-1.)

Henry’s answer is below:

2^n*(n+1)/2

For each element in the domain, the number of “connection” possibilities for that element to each element of the codomain (given that it can either be related or not related to a codomain element) is 2n, where n is the number of codomain elements.

This includes the possibility of the element connecting to itself, because there are two possibilities involving self connection, and 2^(n-1) possibilities for connection to non-identical elements. The product of these two results in 2*2^(n-1) = 2ⁿ.

For each following element in the domain, the relationship with all previous elements which have been assigned relationships is fixed. For example, if element a in the domain is related to element b in the codomain, then element b in the domain must be related to element a in the codomain. This applies equally if element a in the domain is not related to element b in the codomain, because then element b in the domain must also not be related to element a in the codomain, or the relation would not be self-inverting.

All other relationships between our second element and elements of the codomain are still free to change, though, leaving 2^n-1 combinations for the second element considered.

This pattern continues n times in total, and by multiplying these possibilities, we get

2ⁿ * 2^n-1 * 2 ^n-2 … * 2¹

Which is the same as 2^{n + (n-1) + (n-2)
+ … + 2 + 1}.

By reversing the addition sequence we get that the exponent of 2 is the sum of all numbers from 1 to n, which is equal to n*(n+1)/2.

Hence, the number of self-inverting relations for a set of size n must be 2^(n*(n+1)/2).

Congratulations to Henry Spece for solving the challenge!