不妨把问题用数列来叙述,即求满足如下条件的数列的个数.
① 数列各项为0~n-1的整数,且各不相同.
② 除首项外,每一项均与前面某项相差±1.
③ 数列的首项不为0.
过程分三步.
首先,设满足①,②且长度为n的数列的个数为a[n].
对于长为n的数列,考虑其前n-1项,可不重不漏的分为两种情况.
(1) 各项为0~n-2的整数,且各不相同.
(2) 各项为1~n-1的整数,且各不相同.
由a[n]的定义,满足(1),②且长度为n-1的数列的个数为a[n-1].
而满足(2),②且长度为n-1的数列的个数也为a[n-1].
易见,这些长为n-1的数列可以唯一的延长为一个满足①,②的长度为n的数列.
不同的数列延长后仍不同,且所有满足①,②的长度为n的数列都能这样延长得到.
于是a[n] = 2a[n-1].由a[2] = 2 (包括01和10),可得a[n] = 2^(n-1).
其次,考虑满足①,②的长度不限的数列的个数.
其中长度为k的数列可以分为n-k+1类.分别由0~k-1,k,k+1,...,n-k~n-1的整数组成.
每类有a[k] = 2^(k-1)个数列,总共有(n-k+1)·2^(k-1)个.
总数为2^(n-1)+2·2^(n-2)+3·2^(n-3)+...+n·2^0 = (2^n-1)+(2^(n-1)-1)+...+(2^1-1) = 2^(n+1)-n-2.
最后,在上述数列中,首项为0的有n个:0,01,012,...,012...(n-1).
于是满足①,②,③的数列共有2^(n+1)-2n-2个.
即满足条件的n进制整数有2^(n+1)-2n-2个.