math - 随机生成的密码中出现 3 个字符串的概率

Question

如果您有一个随机生成的密码，仅由字母数字字符组成，长度为 12，并且比较不区分大小写(即 'A' == 'a')，那么一个长度为 3 的特定字符串(例如 ' ABC') 会出现在那个密码中吗？

我知道可能的组合总数是 (26+10)^12，但除此之外，我有点迷茫。对数学的解释也是最有帮助的。

Answer 1

字符串 "abc"可以出现在第一个位置，使字符串看起来像这样:

abcXXXXXXXXX

...其中 X 可以是任何字母或数字。有 (26 + 10)^9 个这样的字符串。

它可以出现在第二个位置，使字符串看起来像:

XabcXXXXXXXX

还有 (26 + 10)^9 个这样的字符串。

由于“abc”可以出现在第一个到第 10 个位置的任何位置，因此有 10*36^9 个这样的字符串。

但这会高估，因为它计算(例如)这样的字符串两次:

abcXXXabcXXX

所以我们需要像这样计算所有的字符串，并从我们的总数中减去它们。

由于此模式中有 6 个 X，因此有 36^6 个字符串与此模式匹配。

我得到 7+6+5+4+3+2+1 = 28 个这样的模式。 (如果第一个“abc”在开头，第二个可以在7个位置中的任何一个。如果第一个“abc”在第二个位置，第二个可以在6个位置中的任何一个。以此类推。)

所以减去28*36^6。

...但这减去太多，因为它减去这样的字符串三次而不是一次:

abcXabcXabcX

所以我们必须像这样在字符串中添加两次。我得到 4+3+2+1 + 3+2+1 + 2+1 + 1 = 20 个这些模式，这意味着我们必须添加 2*20*(36^3)。

但是那个数学计算这个字符串四次:

abcabcabcabc

...所以我们必须减去 3。

最终答案:

10*36^9 - 28*36^6 + 2*20*(36^3) - 3

将其除以 36^12 以获得您的概率。

另见 Inclusion-Exclusion Principle .如果我在计数时出错，请告诉我。