免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 一个群里的计数问题

有一个8位数字密码,组合“00”正好出现一次.这样的密码共有多少个?
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

记事件 `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`。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

试着求了一下 `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*}
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 2# kuing


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

TOP

回复 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# 相符。

TOP

`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]
复制代码
瞬间得出 `5691303`。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

咦,从楼上的式 (***) 也可以推出 `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# 的是等价的。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

无标题.png
2018-12-17 18:41

TOP

回复 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).\]
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

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

TOP

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

TOP

本帖最后由 业余的业余 于 2018-12-23 04:28 编辑

考虑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 楼思路一致

TOP

返回列表 回复 发帖