string - 区分大小写字符串的组合计数

Question

我记得，组合数等于 n！

但是，例如，我有字符串“abc”。我想获得具有不同注册表的所有组合：aBc 或 ABc 等

所以，abc 是 3 个字符。3！= 1 * 2 * 3 = 6。但是，如果我尝试手动完成这项工作 - 我会得到 8 种变化：

1 abc 2 abc 3 abc 4 abc 5 abc 6 abc 7 abc 8 abc

所以，看起来，答案是 2^3 = 8，但 2 是什么？3 - 是字符串中的注册表数。什么是 2？注册表变体的数量？

Answer 1

如果我理解正确，您想知道对于固定字符串，以混合大写形式编写固定字符串有多少种可能的组合。您对源字符串的实际排列不感兴趣，即您不想考虑到 abc 也有 acb、cab、cba 等。是吗？

如果是这样，对于 1 个字母，我们有

a A

两个字母

ab Ab aB AB

和三个字母

abc Abc aBc abC ABc aBC AbC ABC

等等。如果是这种情况，那么如果您选择正确的底层模型，那么解决方案将非常简单。您可能已经注意到，结果与我们选择的字符序列无关 - 那么为什么不选择 all a：

a A
aa aA Aa AA
aaa aaA aAa aAA Aaa AaA AAa AAA

模式是，对于每个字符，我们有两个可用的选择，大写或小写，设置或未设置... 1 或 0 - 只需将 a 替换为 0 并将 A 替换为 1 即可获得：

0 1
00 01 10 11
000 001 010 011 100 101 110 111

这实际上是二进制计数！因此对于 n 个字母，可能的组合数将等于 2^n。

Answer 2

啊，我想我明白你在说什么了。如果我对您的理解正确，您正在寻找所有可能的方法来将字符串中的字母大写，以使所有字母的大小写不同 - 也就是说，给定 abc，您会产生

abC aBc aBC Abc AbC ABc

但不是

abc ABC

因为这些版本中的所有字母都有相同的大小写。

如果这是您想要的，那么您可以在长度为 n 的非空字符串中执行此操作的方法数由 2 ⁿ - 2 给出。直观地说，这背后的基本原理如下。给定一个由 n 个字母组成的字符串，有 2 ⁿ种不同的方式将该字符串中的所有字母大写，因为对于每个独立于其余字符的字符，该字母可以处于两种状态之一（大写或小写）。如果您考虑所有这些组合，则恰好有两个您想要禁止 - 所有字母都是大写的版本，以及所有字母都是小写的版本。

在您的问题中，您提到 n 元素序列的组合数是 n！。这不太对。有n！n 元素序列的排列（假设每个元素都是不同的）。例如，有 3 个！= 序列 abc 的 6 个排列：

abc  acb  bac  bca  cab  cba

有六种方法可以将三个字母的序列大写，但所有字母的大小写都不相同，而且 abc 有六种排列，这完全是巧合。如果您查看该系列的更多术语，您会发现它们仅在两个位置（2 和 3）匹配：

                                    n = 1   2   3   4   5   6
Permutations (n!)                       1   2   6   24  120 720
Mixed-case capitalizations (2^n - 2)    0   2   6   14  30  62

如果您允许更多的情况，而不仅仅是上和下（例如，k 个不同的版本），那么您可以将其推广以得到 k ⁿ - k 的值，因为有 k ^{n 个}不同的组合，其中 k 个都将具有大小写相同。

希望这可以帮助！