Question

求所有这样的正整数的个数，它在n进制中表示的数字各不相同，并且除去最左边的数字外每个数字均和他左边某

（接上）个数相差+1或-1

Answer 1

不妨把问题用数列来叙述, 即求满足如下条件的数列的个数.
① 数列各项为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, 1~k, 2~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个.