计数'n'个对象

CS109 教会我 计数很重要。要真正理解概率及其用例，需要进行计数（样本空间和事件空间）。Chris Piech，这门课程的讲师，深入探讨了计数的直觉，并提出了一些基本构建块。这篇博客文章将是我分享我所理解的方式。如需更详细的分析，请参阅课程（可在 YouTube 上免费获取）。

计数二法则

计数步进法则

想象一个实验，有两种选择：抛硬币（正面或反面）和掷骰子（六种可能性）。如果这些选择互不影响（抛硬币不影响掷骰子），那么整个实验的总可能性数量就是抛硬币的方式（2）**乘以**掷骰子的方式（6）。

换句话说，如果可以发生n种不同的事情（$A_{1}A\_1$、$A_{2}A\_2$、$\dots \backslash dots$、$A_{n}A\_n$），并且它们互不影响，那么实验的总方式就是将每种事情的可能性数量相乘（n个选项相乘）。

$$\text{number of outcomes}=\mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{\mid }{A}_2\mathrm{\mid }\dots \mathrm{\mid }{A}_n\mathrm{\mid }\backslash text\{number\; of\; outcomes\}\; =\; |A\_\{1\}|\; |A\_\{2\}|\; \backslash dots\; |A\_\{n\}|$$

让我们通过一个例子进一步说明这个概念。

我们有一个2x2的网格（如下图所示）。通过填充这4个网格，可以形成多少个独特的图像？

我们假设每个网格可以包含以下颜色组合：红色, 绿色和，蓝色。我们还假设表示一个颜色需要1字节（8位）内存。

既然问题和假设都清楚了，让我们**一步步**解决这个问题。

8位可以表示的颜色总数

有8步——每一步有2个结果（0或1）。每个结果相互独立，因此我们可以在这里使用计数步进法则。颜色总数将是$2^{8}2^8$

一个像素中颜色组合的总数

现在我们有$2^{8}2^8$种方式来表示一种颜色，共有3种颜色可以组合起来形成一个像素中的不同颜色。

这可以用计数的步进法则再次计算。$2^8\times 2^8\times 2^8=2^{24}2^8\; \backslash times\; 2^8\; \backslash times\; 2^8\; =\; 2^\{24\}$

独特图像的总数

你大概能猜到我要做什么。

$$2^{24}\times 2^{24}\times 2^{24}\times 2^{24}2^\{24\}\; \backslash times\; 2^\{24\}\; \backslash times\; 2^\{24\}\; \backslash times\; 2^\{24\}$$

计数或法则

这个很简单。如果你有n组结果，并且想知道任一组中所有可能的结果，你就需要将所有组的结果数量相加。

想象一下你在自动售货机前，你可以：

选择冷饮：5种选择（可乐、雪碧、芬达、橙汁、水）

或者

选择热饮：3种选择（咖啡、茶、热巧克力）

你总共有多少种选择？

根据或法则，我们只需将可能性相加

总选择数 = 冷饮选项 + 热饮选项

总选择数 = 5 + 3 = 8

我们已经涵盖了计数的基础知识。在接下来的章节中，我们将在此基础上构建一些抽象概念。具体来说，我们将深入探讨在给定$nn$个对象时，不同的计数方式。

计数排列（Permutations）

给定$nn$个不同的对象，有多少种排列方式？

让我们考虑一个字母集合 {a, b, c, d} 和 4 个位置，每个位置可以放置一个字母。

我们可以用我们友好的步进计数法则来解决这个问题。第一个位置有4种选择，一旦选择，第二个位置有3种选择，依此类推。

应用计数步进法则，总排列数是$$4\times 3\times 2\times 1=4!4\; \backslash times\; 3\; \backslash times\; 2\; \backslash times\; 1\; =\; 4!$$

给定$nn$个不相异的的对象，有多少种排列方式？

修改之前的例子，我们现在有以下字母集合 [a, a, b, c]。请注意，我们仍然有 4 个位置要填充，但并非所有字母都不同。

Chris Piech 分享的一个🔑重要见解是先将所有元素视为不同的，然后再进行处理。

经过这种修改，我们现在知道有 4! 种排列字母的方式。实际上，我们**多算了**。现在，我们只需要减去多算的部分。

在去除多算数量之前，让我们更好地构建这个想法。要么存在一个静态的多算次数（需要减去），要么存在一个可以多算的乘法因子（需要除以）。在这种情况下，我们以倍数多算了。

考虑 a, a, b, c 这种排列。如果 'a's 是不同的，那么放置它们的两种方式是。

如果我们考虑两个不同的'a'，这两种排列是不同的，但这里情况并非如此。继续这个想法，我们了解到对于所有包含a、b和c的不同排列，都有2个重复项（'a's交换位置）。

这意味着我们需要将4！（所有不同的）除以2（两个'a'），然后得到我们想要的结果$\frac{4!}{2!}\backslash frac\{4!\}\{2!\}$。

如果我们有以下字母 [a, a, a, c] 和相同的 4 个位置，会怎样呢？我们多算的次数实际上是如果 'a's 是不同的，它们排列的次数（即 3!）。因此，我们排列字母的总方式是$4!3!\backslash frac\{4!\}\{3!\}$

我们可以将其归纳为：如果给定$nn$个对象，其中$n_1,n_2,\dots n_{r}n\_\{1\},\; n\_\{2\},\; \backslash dots\; n\_\{r\}$是不可区分的，那么总排列数将是：$$\frac{n!}{n_1!n_2!\dots n_r!}\backslash frac\{n!\}\{n\_\{1\}!\; n\_\{2\}!\; \backslash dots\; n\_\{r\}!\}$$

计数选择k个对象的方式（组合）

给定$nn$个不同给定n个不同的对象，有多少种方式可以选择其中的k个对象？

你为$nn$个人举办了生日派对，但你计算错误，只能选择k个人（k < n）吃蛋糕。你有多少种方式可以做到这一点？

如果你在**一步步**思考，那你就走对了。

1. 问题的第一部分是排列n个不同的人。我们可以用n!种方式来完成。
2. 下一步是在前k个人之间画一条分隔线。我们只能用1种方式来做。
3. 我们不关心前k个人的排列方式。总共有k!种排列方式。
4. 我们不关心其余 (n-k) 个人的排列方式。总共有 (n-k)! 种排列方式。

$$\text{number of ways to choose k from n objects}=n!\times 1\times \frac{1}{k!}\times \frac{1}{(n-k)!}=\frac{n!}{k!(n-k)!}\backslash text\{number\; of\; ways\; to\; choose\; k\; from\; n\; objects\}\; =\; n!\; \backslash times\; 1\; \backslash times\; \backslash frac\{1\}\{k!\}\; \backslash times\; \backslash frac\{1\}\{(n-k)!\}\; =\; \backslash frac\{n!\}\{k!(n-k)!\}$$

❤️ 我非常喜欢这个问题，因为这是我第一次通过计数推导出组合的公式。

注：从n个不同对象中选择k个对象也可以表示为$C_r^{n}C\_\{r\}^\{n\}$

给定$nn$个不相异的给定n个不同的对象，有多少种方式可以选择其中的k个对象？

这很简单，从n个不相异对象中选择k个对象只有1种方式。

计数将对象放入r个桶中的方式

给定$nn$个不同给定n个不同的对象，有多少种方法可以将它们放入$rr$个桶中？

我们有 3 个不同的形状，需要放入 3 个桶中。这个问题与将 3 个不同形状排列在 3 个位置（允许重复）是相同的。

这意味着第一个桶有3种方式，第二个桶有3种方式，第三个桶有3种方式。根据计数步进法则，总共有$3^{3}3^3$种方式。

概括这个概念，如果存在n个不同的对象和r个桶，那么将它们放入桶中有$n^{r}n^r$种方式。

给定$nn$个不相异的给定n个不同的对象，有多少种方法可以将它们放入$rr$个桶中？

现在我们有n个不可区分的对象，需要放入r个桶中。这里的想法是在混合物中添加(r-1)个分隔符。让我们考虑3个对象和2个桶，下图显示了对象和分隔符。

简单地计数排列数量就能得到我们想要的结果。

这现在变成了一个排列非区分对象的问题。我们可以将其表述为$$\frac{(n+r-1)!}{n!(r+1)!}\backslash frac\{(n+r-1)!\}\{n!(r+1)!\}$$

总结

感谢您的时间。我希望我能对计数这一主题有所帮助。我一直被这些直觉的隐藏方式所折服。祝您学习愉快。

致谢

我要感谢 Udbhas Mitra 和 Sayak Paul 对本博客文章的审阅。