用包容排斥原理计算7位二进制位串不包含5个连续的0的个数。 |A1| **00000|A2l*00000*|A3/ 00000** IA,NA3I= |A2NA3/= IANA2NA3I= 由包容排斥原理,含5个连续的0的个数: (AIUAzUA3I=/AIIHA2HA3 -0AIDA2HHAINA3/ +|A2NA3/)H]AINA2N 不含5个连续的0的个数为
时间: 2023-08-12 08:23:07 浏览: 213
首先,总共有 $2^7=128$ 个 7 位二进制位串。然后我们考虑计算包含至少 5 个连续的 0 的串的个数。
设 $A_1$ 表示第一个 0 的位置,$A_2$ 表示第二个 0 的位置,以此类推,$A_5$ 表示第五个 0 的位置。注意到 $A_i$ 取值范围为 $\{1,2,\ldots,3\}$,因为如果 $A_i\geq 4$,那么 $A_{i+1}$ 无法取到任何值。因此,我们可以列出如下的计数式子:
$$
|A_1A_2A_3A_4A_5|=\sum_{i=1}^3\sum_{j=i+1}^3\cdots\sum_{k=j+3}^3 1=3^5
$$
其中 $\sum_{i=1}^3$ 表示 $A_1$ 可以取到 $1,2,3$ 中的任意一个值,$\sum_{j=i+1}^3$ 表示 $A_2$ 可以在 $A_1$ 的后面取到 $1,2,3$ 中的任意一个值,以此类推,$\sum_{k=j+3}^3 1$ 表示 $A_5$ 可以在 $A_4$ 的后面取到 $1,2,3$ 中的任意一个值。
但是上面的计数式子会把一些串计算多次。具体来说,如果 $A_1=A_2=1$,那么这个串会被上面的式子计算 $3$ 次,即当 $A_3=1,2,3$ 时分别计算一次。同理,当 $A_1=A_2=2$ 或者 $A_1=A_2=3$ 时也会出现这种情况。因此,我们需要减去这些被重复计算的串的个数。
设 $B_1$ 表示第一个 0 的位置,$B_2$ 表示第二个 0 的位置,以此类推,$B_4$ 表示第四个 0 的位置。注意到 $B_i$ 取值范围为 $\{1,2\}$,因为如果 $B_i\geq 3$,那么 $B_{i+1}$ 无法取到任何值。因此,我们可以列出如下的计数式子:
$$
|B_1B_2B_3B_4|=\sum_{i=1}^2\sum_{j=i+1}^2\cdots\sum_{k=j+2}^2 1=2^4
$$
其中 $\sum_{i=1}^2$ 表示 $B_1$ 可以取到 $1,2$ 中的任意一个值,$\sum_{j=i+1}^2$ 表示 $B_2$ 可以在 $B_1$ 的后面取到 $1,2$ 中的任意一个值,以此类推,$\sum_{k=j+2}^2 1$ 表示 $B_4$ 可以在 $B_3$ 的后面取到 $1,2$ 中的任意一个值。
但是上面的计数式子会把一些串计算多次。具体来说,如果 $B_1=B_2=1$,那么这个串会被上面的式子计算 $2$ 次,即当 $B_3=1,2$ 时分别计算一次。同理,当 $B_1=B_2=2$ 时也会出现这种情况。因此,我们需要加上这些被重复计算的串的个数。
设 $C_1$ 表示第一个 0 的位置,$C_2$ 表示第二个 0 的位置,以此类推,$C_3$ 表示第三个 0 的位置。注意到 $C_i$ 取值范围为 $\{1,2\}$,因为如果 $C_i\geq 3$,那么 $C_{i+1}$ 无法取到任何值。因此,我们可以列出如下的计数式子:
$$
|C_1C_2C_3|=\sum_{i=1}^2\sum_{j=i+1}^2 1=2^3
$$
其中 $\sum_{i=1}^2$ 表示 $C_1$ 可以取到 $1,2$ 中的任意一个值,$\sum_{j=i+1}^2$ 表示 $C_2$ 可以在 $C_1$ 的后面取到 $1,2$ 中的任意一个值,以此类推。
同样地,上面的计数式子会把一些串计算多次。具体来说,如果 $C_1=C_2=1$,那么这个串会被上面的式子计算 $1$ 次,即当 $C_3=1$ 时计算一次。因此,我们需要减去这些被重复计算的串的个数。
综上,不包含 5 个连续的 0 的串的个数为:
$$
2^7-3^5+2^4-2^3+1=\boxed{43}
$$
阅读全文