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.
(In reply to
Most of a proof by Larry)
Larry's proof works for me.
We can prove by induction that the last k digits must be consective in some order:
The last 2 digits must be consecutive (in some order), because digit n-1 is 1 more or one less than digit n.
Then the last 3 digits must be consecutive (in some order) because digit n-2 is either 1 more than the maximum or 1 less than the minimum of the 2 consecutive digits that follow it.
Then the last 4 digits must be consecutive (in some order) because digit n-3 is either 1 more than the maximum or 1 less than the minimum of the 3 consecutive digits that follow it.
By induction, the last k digits must be consecutive (in some order) because digit n-(k-1) is either 1 more than the maximum or 1 less than the minimum of the (k-1) consecutive digits that follow it
And since the last n-1 digits are consecutive in some order, the first digit must either be 1 or n.
re: Most of a proof
