组合数学/计数

看起来很奇怪，但有时计数是数学中最困难的事情之一。事实上，将组合数学称为排列对象的艺术并计数它们并不为过。在组合数学中，当通过枚举所有可能性来计数对象时，蛮力技术通常注定会失败，我们被迫依赖各种技术和数学思想。有时，即使这些想法也无法帮助我们，我们也必须满足于建立给定估计或要计数对象的界限。

双重计数

在组合数学中，双重计数，也称为双向计数，是一种证明技术，它涉及以两种方式计算集合的大小，以证明集合大小的两个结果表达式是相等的。我们从两个角度描述一个有限集合 X，从而得到两个不同的表达式。通过这两个角度，我们证明了每一个都等于 |X|。

让我们看两个例子。第一个被称为握手引理，可以简洁地表述为

在一次大会上，握手次数为奇数的代表人数是偶数。

为了看到这一点，让 $D_{1},\cdots D_{n}$ 是代表。让 $x_{i}\,$ 是 $D_{i}\,$ 握手次数，$y\,$ 是发生的握手总数。很明显，手的伸出次数总共是

$\sum _{i=1}^{n}x_{i}$.

但从另一个角度计数，它仅仅是 $2y\,$ - 每次握手 $y\,$ 伸出的两只手。所以，

$\sum _{i=1}^{n}x_{i}=2y$.

现在总共有多少奇数 $x_{i}\,$ 可以出现在总和中。如果奇数 $x_{i}\,$ 的数量是奇数，那么它们的总和也一定是奇数（例如 2a+1）。当它加到偶数 $x_{i}\,$ 的总和（例如 2b）时，会得到一个奇数（2a+2b+1）。但我们刚刚看到 $\sum _{i=1}^{n}x_{i}$ 是偶数。因此，奇数 $x_{i}\,$ 的数量是偶数。但这仅仅是另一种说法，即握手次数为奇数的代表人数是偶数。

让我们看另一个例子。我们想要推导出前 n 个自然数之和的公式。假设我们有一个 (n + 1)×(n + 1) 的点阵。对角线上点的数量正好是 n + 1，并且显然严格位于对角线上的点的数量 S 等于严格位于对角线下的点的数量，因此方阵中点的总数是 n + 1 + 2S。另一方面，方阵中点的总数是 (n + 1)²，所以

$(n+1)^{2}=n+1+2S\,$,

因此

$n(n+1)=2S\,$,

所以

$S=\sum _{k=1}^{n}{k}={\frac {n(n+1)}{2}}.$