一个群里的计数问题

2009

有一个8位数字密码，组合“00”正好出现一次．这样的密码共有多少个？

kuing

记事件 `A` 表示密码中没有组合“00”，事件 `B` 表示密码中正好有一个组合“00”。

设密码为 `n` 位时，属于 `A` 的共有 `f(n)` 个，属于 `B` 的共有 `g(n)` 个。

先解决 `f` 的，用递推法，显然 `f(1)=10`, `f(2)=99`，当 `n\geqslant3` 时：

（1）若第一位非 0，则后面不受影响，有 `f(n-1)` 个，所以这种情况共 `9f(n-1)` 个；

（2）若第一位是 0，则第二位非 0，后面有 `f(n-2)` 个，所以这种情况共 `9f(n-2)` 个。

综上有
\[f(n)=9f(n-1)+9f(n-2),\quad(*)\]
这样就可以把 `f(n)` 解出来，不过表达式比较复杂，暂且不写。


接下来用同样的方法解决 `g` 的，显然 `g(2)=1`, `g(3)=18`，当 `n\geqslant4` 时：

（1）若第一位非 0，则后面不受影响，有 `g(n-1)` 个，所以这种情况共 `9g(n-1)` 个；

（2）若第一位是 0，需再分类：

    （2-1）若第二位非 0，则后面有 `g(n-2)` 个，所以这种情况共 `9g(n-2)` 个；

    （2-2）若第二位是 0，则第三位非 0，此时后面变成不能出现组合“00”，所以这种情况共 `9f(n-3)` 个。

综上有
\[g(n)=9g(n-1)+9g(n-2)+9f(n-3), \quad(**)\]
将此式与前面的式 (*) 联立或许也可以把这个 `g(n)` 求出来，不过这里也暂且不去尝试了，即便能求估计表达式也非常复杂。这里就直接利用俩递推式逐步算上去好了，由于只需 8 位，所以先计算 `f(n)` 的前 5 项，随即可计算 `g(n)` 的前 8 项：
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
n&1&2&3&4&5&6&7&8\\
\hline
f(n)&10&99&981&9720&96309\\
\hline
g(n)&&1&18&261&3402&41796&494262&5691303\\
\hline
\end{array}
\]
所以原题所求的答案就是 `5691303`。

kuing

试着求了一下 `g(n)`，发现也并没有想象中复杂，因为两个递推很相近，都是 9，所以 `f` 的特征根也可用于 `g`。

首先记 `x^2=9(x+1)` 的两根为 `x_1`, `x_2`，则根据特征方程理论，`f(n)` 必可写成 `f(n)=ax_1^n+bx_2^n` 的形式，具体数值留到最后再说。

由于 `x_1x_2=-9`, `x_1+x_2=9`，所以式 (**) 可以写成
\[g(n+3)=(x_1+x_2)g(n+2)-x_1x_2g(n+1)+9(ax_1^n+bx_2^n),\]
整理为
\begin{align*}
g(n+3)-x_2g(n+2)&=x_1\bigl(g(n+2)-x_2g(n+1)\bigr)+9(ax_1^n+bx_2^n),\\
\frac{g(n+3)-x_2g(n+2)}{x_1^n}&=\frac{g(n+2)-x_2g(n+1)}{x_1^{n-1}}+9a+9b\left( \frac{x_2}{x_1} \right)^n,\\
\frac{g(n+3)-x_2g(n+2)}{x_1^n}&=g(3)-x_2g(2)+9na+9b\cdot\frac{x_2}{x_1}\cdot\frac{1-(x_2/x_1)^n}{1-x_2/x_1},\\
g(n+3)-x_2g(n+2)&=(18-x_2+9na)x_1^n+9bx_2\frac{x_1^n-x_2^n}{x_1-x_2},
\end{align*}
同理有
\[g(n+3)-x_1g(n+2)=(18-x_1+9nb)x_2^n+9ax_1\frac{x_1^n-x_2^n}{x_1-x_2},\]
两式相减化简得
\[(x_1-x_2)g(n+2)=9\left( 2-\frac{ax_1-bx_2}{x_1-x_2} \right)(x_1^n-x_2^n)+9(x_1^{n-1}-x_2^{n-1})+9n(ax_1^n-bx_2^n),\]
现在开始代具体数值进去，根据 `f(1)`, `f(2)` 的值可计算出
\[x_1,x_2=\frac{9\pm3\sqrt{13}}2, a,b=\frac12\pm\frac{11}{6\sqrt{13}}, x_1-x_2=3\sqrt{13}, ax_1-bx_2=\frac{36}{\sqrt{13}},\]
代入化简，最终得
\begin{align*}
g(n+2)={}&\left( \frac{45}{26\sqrt{13}}+\frac12+\frac{3n}{\sqrt{13}}\left( \frac12+\frac{11}{6\sqrt{13}} \right) \right)\left( \frac{9+3\sqrt{13}}2 \right)^n \\
& - \left( \frac{45}{26\sqrt{13}}-\frac12+\frac{3n}{\sqrt{13}}\left( \frac12-\frac{11}{6\sqrt{13}} \right) \right)\left( \frac{9-3\sqrt{13}}2 \right)^n.
\end{align*}

isee

回复 2# kuing


这么大的数，难怪没人理的

kuing

回复 4# isee

没人理主要是枚举也不容易吧，如果位数少一点还好。
下面来试试枚举 5 位和 6 位，顺便用来检验 2#。
用 [x-y] 表示某位可取 x 至 y。
5 位：
00*** = 00[1-9]ab，其中 ab 除了 00 外都可取，所以这类共 9×99 个；
*00** = [1-9]00[1-9][0-9]，共 9×9×10 个；
由对称性知 **00* 和 ***00 也和上面的一样，所以 5 位时结果为 (9×99+9×9×10)×2=3402，与 2# 相符。
6 位：
00**** = 00[1-9]abc，其中 abc 不能出现 00，需排除 00[1-9]、[1-9]00 及 000，所以这类共 9×(1000-9-9-1) 个；
*00*** = [1-9]00[1-9]ab，其中 ab 除了 00 外都可取，所以这类共 9×9×99 个；
**00** = [0-9][1-9]00[1-9][0-9]，共 10×9×9×10 个；
由对称性知 ***00* 和 ****00 也和上面的一样，所以 6 位时结果为 (9×(1000-9-9-1)+9×9×99)×2+10×9×9×10=41796，同样与 2# 相符。

kuing

`g(n)` 与 `f(n)` 的另一种关系：

沿用楼上的记法：
00[1-9]**……*（`n-3` 个 *），共 `9f(n-3)` 个；
[1-9]00[1-9]**……*（`n-4` 个 *），共 `9^2f(n-4)` 个；
……
**……*[1-9]00[1-9]**……*（前面 `k` 个 *，后面 `n-k-4` 个 *），共 `9^2f(k)f(n-k-4)` 个；
……
综上，有
\[g(n)=9f(n-3)+9^2f(n-4)+9^2\sum_{k=1}^{n-5}f(k)f(n-k-4)+9^2f(n-4)+9f(n-3),\]
若记 `f(0)=1`，则上式可写成
\[g(n)=18f(n-3)+9^2\sum_{k=0}^{n-4}f(k)f(n-k-4), \quad(*{*}*)\]
这样就完全可以根据 `f(0)` 至 `f(5)` 直接算出 `g(8)` 了，计算上应该方便一点。

MMC代码验证一下：

1. f[0] = 1;
2. f[1] = 10;
3. Do[f[n + 1] = 9 (f[n] + f[n - 1]), {n, 4}]
4. g[n_] := 18 f[n - 3] + 9^2 Sum[f[k] f[n - k - 4], {k, 0, n - 4}]
5. g[8]

Copy the Code

瞬间得出 `5691303`。

kuing

咦，从楼上的式 (***) 也可以推出 `g(n)` 的具体表达式，而且过程比 3# 还简单一点。

将式 (***) 的 `n` 写成 `n+4`，即
\[g(n+4)=18f(n+1)+9^2\sum_{k=0}^nf(k)f(n-k),\]
沿用 3# 的设定，有
\begin{align*}
f(k)f(n-k)&=(ax_1^k+bx_2^k)(ax_1^{n-k}+bx_2^{n-k})\\
&=a^2x_1^n+b^2x_2^n+ab(x_1^kx_2^{n-k}+x_1^{n-k}x_2^k),
\end{align*}
求和即
\begin{align*}
\sum_{k=0}^nf(k)f(n-k)&=(n+1)(a^2x_1^n+b^2x_2^n)+2ab\sum_{k=0}^nx_1^kx_2^{n-k}\\
&=(n+1)(a^2x_1^n+b^2x_2^n)+2ab\frac{x_1^{n+1}-x_2^{n+1}}{x_1-x_2},
\end{align*}
所以
\[g(n+4)=18(ax_1^{n+1}+bx_2^{n+1})+81(n+1)(a^2x_1^n+b^2x_2^n)+162ab\frac{x_1^{n+1}-x_2^{n+1}}{x_1-x_2},\]
再将 `n` 写为 `n-1`，第二项系数 `81` 写成 `-9x_1x_2`，可得
\[g(n+3)=9\left( 2a-na^2x_2+\frac{18ab}{x_1-x_2} \right)x_1^n+9\left( 2b-nb^2x_1-\frac{18ab}{x_1-x_2} \right)x_2^n,\]
最后代入具体数值化简，最终得
\begin{align*}
g(n+3)={}&9\left( 1+\frac{47}{13\sqrt{13}}+\frac{18+5\sqrt{13}}{39}\cdot n \right)\left( \frac{9+3\sqrt{13}}2 \right)^n\\
&+9\left( 1-\frac{47}{13\sqrt{13}}+\frac{18-5\sqrt{13}}{39}\cdot n \right)\left( \frac{9-3\sqrt{13}}2 \right)^n.
\end{align*}

这个结果和 3# 的是等价的。

游客

记8位中共有 $k$ 个 的密码有 $n_k$ 个符合条件，则用＂插空＂法可得：
\begin{aligned}
& n_2=9^6 \times C_1^4, \quad n_3=9^5 \times C_6^2 \times C_2^1, \\
& n_4=9^4 \times C_5^3 \times C_3^4, n_5=9^3 \times C_4^4 \times C_4^1, \\
& N=n_2+n_3+n_4+n_3=5691303 .
\end{aligned}

kuing

回复 8# 游客

看了半天才理解了那些 C 的意思……
下面按我自己的理解来解释一下（不一定与楼上的想法相同）。
比如 `n_4`，先考虑 7 位中有 3 个 0 且都不相邻，那么在前两个 0 的后面都捆绑一个非 0，所以是 `C_5^3`，然后在 3 个 0 中选一个变成 00，所以再乘 `C_3^1`，而剩余的 4 个非 0 自然就是 `9^4`，所以 `n_4=9^4C_5^3C_3^1`。

这个计算方法也不错，而且同样具有一般性：
设位数为 `n`，共有 `k` 个 0 的密码有 `n_k` 个符合条件，则 `n_2=9^{n-2}C_{n-1}^1=9^{n-2}(n-1)`，当 `k\geqslant3` 且 `k\leqslant\lfloor n/2\rfloor+1` 时，有 `n_k=9^{n-k}C_{n-1-(k-2)}^{k-1}C_{k-1}^1=9^{n-k}C_{n-k+1}^{k-1}(k-1)`，所以总数
\[g(n)=9^{n-2}(n-1)+\sum_{k=3}^{\lfloor n/2\rfloor+1}9^{n-k}C_{n-k+1}^{k-1}(k-1).\]

游客

当0有4个时，因为有且只有2个0在一起，所以有3组0插空。

其妙

递推计数，蛮喜欢的，不过可能不止一种递推关系，也许还有简单的递推关系。但我只会说说而已，过过嘴瘾

业余的业余

考虑7位数字密码，有至少一个'0'但没有2个连续的‘0’的情形， 并通过把其中一个‘0’变成‘00’得到有且仅有一个‘00’的八位密码。

记'0' 的个数为 $i$, 显然 $1\le i \le 4$. 非‘0’数位有 $7-i$ 个， 故有$9^{7-i}$ 种可能。这些非'0'数位中间及前后有 $8-i$ 个位置，从中选取 $i$ 个 放 '0', 有 $C_{8-i}^i$ 种可能。之后再从 $i$ 个'0' 中选一个变为 '00', 有 $i$ 种可能， 综上，为 $9^{7-i}i C_{8-i}^i$.

总数为 $\displaystyle \sum_{i=1}^4 9^{7-i}i C_{8-i}^i$

没细查是否有重复。
-------------

噢，和 9 楼思路一致