继续厕所读书，Richard A. Brualdi的《组合数学》，第三章，排列与组合。

四个最基本的计数原理：

• 加法原理：设集合S划分为。则S的元素个数等于每个部分的元素个数的总和，即：

     

• 乘法原理：令S是元素的序偶(a, b)的集合，其中第一个元素a来自大小为p的集合，而对于a的每个选择，元素b都存在q中选择。于是，S的大小为:

     

• 减法原理：令A是一个集合，而U是包含A的更大的集合。设：

     

  是A在U中的补。那么A中的元素个数|A|等于：

     

• 出发原理：令S是一个有限集，它由以下方式被划分出k部分，每一部分包含相同数目的n元素。此时，划分中的部分的元素个数等于：

     

都不记得当年学习排列组合时这些概念是怎么描述的了。接下来是普通的排列组合。

本章最后介绍的是之前没有了解过的多重集的排列组合。多重集，即含有重复元素的集合。这种集合实际上违反了笛卡尔法则，不过在解决一些实际的排列组合问题时很有用。

最近的厕所读物是很早之前从China-pub淘来的二手书，Richard A. Brualdi的《组合数学》（Introductory Combinatorics 4th ed）。这两天读到的是第二章，鸽巢原理，做点笔记。

鸽巢原理

1834年，德国人Johann Dirichlet将鸽巢原理（pigeonhole principle）形式化，并用于后来被称为Dirichlet近似理论的证明。所以鸽巢原理又被称为Dirchlet原理。Dirichlet是一朵奇葩，这里按下不表，有兴趣的可以去维基百科——Johann Dirichlet。

Dirichlet近似理论是这样的：

对于任意实数和正整数N，存在整数p、q，1 ≤ q ≤ N，使得：

   

简单来说，任何实数都可以通过线性变换逼近某个整数。

Dirichlet是在证明这个理论的过程中将鸽巢原理形式化了，或者可以说这是第一次正儿八经地表述和使用了鸽巢原理。来看看Dirichlet近似理论的证明(参考Dirichlet近似理论证明)。

不妨假设，对于(1, N]区间中的整数a，都有：

其中表示小于的最大整数。这个是显然，任何一个实数减去其整数部分后剩下的小数部分显然是大于等于0，小于1的。因为存在N个整数a，加上0和1，所以在[0,1]这个区间内总共有N+2个数。N+2个数将[0,1]这个区间分割成了N+1个更小的区间。这些小区间中至少会有一个小区间的长度小于或等于。这些小区间实际上就是两个数的差值，换言之就是在这N+2个数中至少有两个数之间的差值小于或等于。

在长度小于等于的这一对数中，如果其中一个数是0或1，那就是说存在：

即：

因为a和b是整数，所以a-b也是整数；同样，也是整数。不妨假设q=a-b, ，则有：

证明完了。这里面什么地方用到了鸽巢原理？就是这句话：

N+2个数将[0,1]这个区间分割成了N+1个更小的区间。这些小区间中至少会有一个小区间的长度小于或等于

鸽巢原理的一般形式是这样的：

令为正整数。如果将个物体放入n个盒子中，那么，或者第一个盒子至少有个物体，或者第二个盒子至少有，，或者第n个盒子至少有个物体。

用到Dirichlet近似理论证明中就是将N+2个数字放入N+1个区间中，其中至少有一个区间至少有两个物体。区间的长度是，所以位于同一个区间中的两个数的差值就小于或等于。

鸽巢原理是最基本的组合学原理。曾经在小学、中学上奥数班时了解过皮毛，现在再来回味一下还是很有意思的。