重复计算

的原则双重计数是首先用一个方式计算一组对象，然后计算另一种方式。最好通过查看几个例子来最佳解释，因为有许多不同的方式来计算。

在11人的一方，每个人都声称他们以其他5人握手。表明有人在撒谎。

---

为每个人提供标签 $1$来 $11$．在握手时贴上标签 $1$来 $n$的适当值 $n$）.考虑到集 $H (i, j)$，人 $我$参加握手 $j$．我们将数一数 $H (i, j)$在两种方式。首先，因为每个人都参加了5次握手，所以有 $11乘以5等于55$这样的价值观。其次，由于每个握手只涉及2人，因此有 $n \ times 2 = 2n$这样的价值观。因此，我们必须有 $55 n = 2,$这是一个矛盾。因此，有人在撒谎。 $_ \广场$

如果我们把每个人在Facebook上的朋友总数加起来，结果是一个偶数。

---

给人们贴上标签 $1$来 $n$．标记友谊 $1$来 $米$．考虑到集 $F (i, j)$，人 $我$涉及到友谊 $j$．考虑一个特定的人 $我$．朋友的数量人 $我$有多少组 $F (I, j)$,对于一些 $j$．因此，每个人都有的朋友总数是总数 $F (i, j)$．

考虑特定的友谊 $J$．然后，由于Facebook上的友谊是相互的，所以正好有两个副本 $F (i, J)$，这两个词都与建立友谊的两个人有关。因此，总数量 $F (i, j)$是 $2米$，即甚至。

这通常被称为握手引理． $_ \广场$

在板球循环赛中 $n$团队，每个团队都互相游戏一次。在每场比赛中，有一个胜利者和一个失败者。让 $W_i$表示团队的胜利人数 $我$, $L_i$表示该队输掉的次数 $我$．表明,

$w_1 + w_2 + \ cdots + w_n = l_1 + l_2 + \ cdots + l_n。$

---

我们将以两种方式计算锦标赛中的游戏数量。让 $G (i, j)$表示球队之间播放的游戏 $我$和 $j$，在哪个队 $我$赢了。首先，我们计算的值的数量 $G (i, j)$根据获胜队伍的说法。因为团队 $我$赢了 $W_i$游戏，由此可见是存在的 $W_1 + W_2 + cdots + W_n$这样的价值观 $G (i, j)$．

现在，我们来计算 $G (i, j)$根据输掉比赛的球队的说法。因为团队 $我$失去了 $L_i$游戏，由此可见是存在的 $l_1 + l_2 + \ cdots + l_n$这样的价值观 $G (i, j)$．

因此，这两个和相等。而且，这个和等于游戏的总数，也就是 $\压裂{n (n - 1)} {2}$． $_ \广场$

考虑一个3到9个板，其中每个方块都是红色或蓝色的。表明存在2行（不一定是连续的）行和2（不一定是连续的）列，其交叉点给出了相同颜色的4个平方。

---

证明通过矛盾。

用表示列号 $j$，表示行号对 $I = {r_1, r_2\}$．我们将数一数 $X (I, j)$，其中给定行和列中的正方形具有相同的颜色。

首先，按列计数 $(j)$．由于每列中有三个方块，因此鸽子原则意味着至少有两个正方形的颜色是相同的。因为有九列， $|x（i，j）|\ geq 9.$．

现在，根据行对计算 $(我)$．根据假设，没有两行两列给出四个相同颜色的正方形。因此，每对行在同一列中最多有一对红-红方块，在同一列中最多有一对蓝-蓝方块。因为有三对行，所以最多有 $3乘以2等于6$这样对。因此, $(I, j, I, j, I, j$．自 $| x（i，j）|\ LEQ 6 <9 \ LEQ | X（I，J）|$，我们有一个矛盾。 $_ \广场$

注:我们也可以用鸽子洞原理来解决这个问题。有 $2 ^ 3 = 8$用不同的方法给一个由3个正方形组成的列涂上红色和蓝色。因此，必须有两列具有相同的颜色配置。根据鸽子洞原理，这一栏中至少有2个方块是相同颜色的。因此，这就得到了我们想要的两行。我们可以把它固定在一块3 × 7的木板上 $不，不$）使用双重计数参数，并且鸽舍参数将不再适用。这是最好的界限，因为我们可以创建一个3乘6个板，方块用2种颜色彩色，并且不存在行和列的这种配置。（在8种可能的组合中，拿6个只有2个方格的6，呈现出相同的颜色。） $_ \广场$

1. 表明, $2 ^ n = \ dbinom {n} {0} + \ dbinom {n} {1} + \ dbinom {n} {2} + \ cdots + \ dbinom {n} {n}$．

   解决方案

   我们将数一数有多少种投放方式 $n$截然不同的物体 $2$不同的盒子。
   首先，我们将盒子标记为 $1$和 $2$．
   计算的第一种方法是考虑对象的对象：每个对象都可以放入任一框中 $1$或盒子 $2$．
   既然有 $n$对象，方法的总数 $n = 2 ^$．第二种计算方法是考虑放入框中的对象的数量 $1$．
   有 $\ dbinom n0$戴路的方法 $0$对象到盒子 $1$， $\ dbinom n1$戴路的方法 $1$对象,……, $\ dbinom nr.$戴路的方法 $r$对象。
   方法总数 $= \ dbinom n0 + \ dbinom n1 + \ dbinom n2 + \ cdots + \ dbinom nn$．

2. 表明在Facebook上拥有奇数好友的人数一定是偶数。

3. [法国]在…的国际会议上 $n \ geq 3$参加者讲14种语言。我们知道任何3个参与者都说一种共同的语言，并且没有超过一半的参与者会说一种语言。的最小值是多少 $n$？