这个是书上的答案。

假设j在最左边，j＞1, 2, …, j-2, j-1
那1只能排在2的右边，不然1左边就没有和它相差为1的数了，1又不在最左边
1在2的右边，那2只能在3的右边 (假设中j≠2)，…，同理一直到j-2都只能排在j-1的右边
也就是j-1, j-2, …, , 2, 1是从左到右递减排列的，同理j+1, j+2, …, n-1, n 也只能从左到右递增排列

这样想：假设1,2,...,n是n个格子拍成一排。我们每一次涂黑一个格子，每次涂的必须和前面已经黑了的连起来。
除了第一次以外，每次涂有两种选择“往左延伸一个”和“往右延伸一个”。每次都可以在这两者之间任意选，全选完之后就知道初始是哪一个了。一共做了n-1次选择，所以排法有2^(n-1)种。

假设有n个格子，把1到n排成一排就是把n个数填到n个格子中，下面把除第一个格子外的其他格子都填上±1，正1表示与左边某个数大1，负1反之。我们要论证题中的每一种排法一一对应±1的填法。