每日一题[1543]映射计数

已知正整数 $n$ 都可以唯一表示为

$$n=a_0+a_1\cdot 9+a_2\cdot 9^2+\cdots +a_m\cdot 9^m$$ 的形式，其中 $m$ 为非负整数，$a_j\in\{0,1,\cdots,8\}$（$j=0,1,\cdots,m-1$），$a_m\in\{1,\cdots,8\}$．试求使得上述等式中的数列 $a_0,a_1,a_2,\cdots,a_m$ 严格单调递增或严格单调递减的所有正整数 $n$（包含对应的数列只有一项的情形）的和．

答案       $984374748$．

解析       记 $p(n)$ 为正整数 $n$ 对应的数列 $a_0,a_1,a_2,\cdots,a_m$，设 $A$ 和 $B$ 分别表示使 $p(n)$ 单调递增和单调递减的正整数 $n$ 构成的集合，用 $S(M)$ 表示集合 $M$ 中的所有数之和，并记

$$n=\overline{a_ma_{m-1}\cdots a_1 a_0}.$$ 接下来尝试获得 $S(A)$ 与 $S(B)$ 的联系．

第一个方程       把集合 $A$ 做如下分划：

$$\begin{split} A_0&=\{n\in A\mid a_0=0\},\\ A_1&=\{n\in A\mid a_0\ne 0\},\end{split}$$ 则 $f:n\mapsto 9n$ 是 $A_1$ 到 $A_0$ 的一一映射，于是 $$S(A_0)=9S(A_1)\implies S(A)=10S(A_1).$$ 又 $$g:\overline{a_m a_{m-1}\cdots a_1a_0}\mapsto \overline{(9-a_m)(9-a_{m-1})\cdots(9-a_1)(9-a_0)}$$ 是 $B$ 到 $A_1$ 的一一映射，且 $$\overline{a_m a_{m-1}\cdots a_1a_0}+\overline{(9-a_m)(9-a_{m-1})\cdots(9-a_1)(9-a_0)}=\dfrac 98\left(9^{m+1}-1\right),$$ 于是 $$\begin{split} S(B)+S(A_1)&=\sum_{m=0}^7\left(\mathop{\rm C}\nolimits_8^{m+1}\cdot \dfrac 98\left(9^{m+1}-1\right)\right)\\ &=\dfrac 98\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k9^k-\dfrac 98\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k\\ &=\dfrac 98\left(10^8-2^8\right).\end{split}$$ 这样我们就得到了方程 $$S(B)+\dfrac1{10}S(A)=\dfrac 98\left(10^8-2^8\right).$$

第二个方程       把集合 $A$ 做如下分划：

$$\begin{split} A_2&=\{n\in A\mid a_m=8\},\\ A_3&=\{n\in A\mid a_m\ne 8\},\end{split}$$ 则 $$h:\overline{a_m a_{m-1}\cdots a_1a_0}\mapsto \overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)}$$ 是 $B$ 到 $A_3$ 的一一映射，且 $$\overline{a_m a_{m-1}\cdots a_1a_0}+\overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)}=9^{m+1}-1,$$ 所以 $$\begin{split} S(B)+S(A_3)&=\sum_{m=0}^7\mathop{\rm C}\nolimits_8^{m+1}\left(9^{m+1}-1\right)\\ &=\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k9^k-\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k\\ &=10^8-2^8.\end{split}$$ 同时考虑集合 $A_2\backslash\{8\}$ 到 $B$ 的一一映射 $$h':\overline{8a_m a_{m-1}\cdots a_1a_0}\mapsto \overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)},$$ 且 $$\overline{8a_m a_{m-1}\cdots a_1a_0}+ \overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)}=9^{m+2}-1,$$ 所以 $$\begin{split} S(B)+S(A_2)&=8+\sum_{m=0}^7\mathop{\rm C}\nolimits_8^{m+1}\left(9^{m+2}-1\right)\\ &=8+9\sum_{k=1}^8\mathop{\rm C}\nolimits_8^k9^k-\sum_{k=1}^8\mathop{\rm C}\nolimits_8^k\\ &=9\cdot 10^8-2^8.\end{split}$$ 这样就得到了方程 $$2S(B)+S(A)=10^9-2^9.$$

综合以上，有

$$\begin{cases} S(B)+\dfrac1{10}S(A)=\dfrac 98\left(10^8-2^8\right),\\ 2S(B)+S(A)=10^9-2^9,\end{cases}\iff \begin{cases} S(A)=968750080,\\ S(B)=15624704,\end{cases}$$ 于是所求正整数的和为 $$S(A)+S(B)-(1+2+\cdots+8)=984374748.$$