How many possible bijections f on {1, 2, ... , n} are there such that for each i = 2, 3, ... , n we can find j < n with f(i) - f(j) = ± 1?
Solution
Answer: 2n-1.
Consider the last element f(n). Suppose it is m, not 1 or n. Then the earlier elements fall into two non-empty sets A = {1, 2, ... , m-1} and B = {m+1, m+2, ... , n}. But the difference between an element of A and an element of B is at least 2. So if f(1) is in A, then the first time we get an element of B it has only elements of A preceding it. Contradiction. Similarly, if f(1) is in B.
So we conclude that the last element is always 1 or n. We can now prove the result by induction. Clearly given an arrangement for n we can derive one for n+1 by adding n+1 at the end. We can also derive one for n+1 by increasing each element by 1 and adding 1 at the end. Equally it is clear that all these are distinct and that there are no other arrangements for n+1 that end in 1 or n+1. So thee are twice as many arrangements for n+1 as for n.
© John Scholes
jscholes@kalva.demon.co.uk
25 Jan 2002