How many permutations of the integers 1, 2, …, n are there such that every integer (last excluded) is followed by (not necessarily immediately) by an integer which differs from it by 1?

For example if n=4 the permutation 1432 is an acceptable one, while 2431 is not.

The required number of permutations = 2^(n-1)

Posted by K Sengupta on 2024-04-02 22:01:16