Skip to content

Tag Archives: 组合数学

《组合数学》缩写(一)

第一章 组合数学关心的问题是将一个集合的物体排列成满足一些制定规则的格式,一般的问题有:排列的存在性(是否存在两个正交的6阶拉丁方)、排列的计数和分类(m×n的棋盘上1×2骨牌的完美覆盖的个数是多少)、研究一个已知的排列(第一类Stirling数与第二类Stirling数的关系)、构造一个最优的排列(给出有向图中从S到T的最短路径)。 第二章 鸽巢原理,又叫抽屉原理。最基本的形式是:把n+1个物体放进n个盒子,至少有一个盒子包含不止一个物体。这个看似平凡的原理就可以用来证明很多有趣的结论了,比如说任意m个整数的序列肯定存在一个连续的子序列的和能被m整除。用它来证明结论最重要的是要巧妙地构造出“盒子”和“物品”,并且通过存在两个物品在同一盒子的事实得出某种结论。 个原理比较加强的形式是:令q_1,q_2,…,q_n为正整数,若将 q_1 + q_2 + … + q_n – n + 1 个物体放入n个盒子中,那么或者第1个盒子含有至少q_1个物体,或者第2个合资含有至少q_2个物体,……,或者第n个盒子含有至少q_n个物体。可以采用明显的反证法证明。这个加强形式可以用来证明长度为n^2-1的实数序列一顶包含长度为n的非增或非减子序列等一些更有趣的问题。 鸽巢定理的推广是Ramsey定理。Ramsey数r(m,n)是指:将完全图K_p的所有边任意涂成红色和蓝色,则或者存在红色的子图K_m,或者存在蓝色的子图K_n,r(m,n)就是p的最小取值。Ramsey定理就是在说对于任意m、n,r(m,n)都是存在的。虽然Ramsey定理说明了Ramsey数的存在性,但是对于Ramsey数的求法,目前还没有非平凡的结论,比如说r(3,10)、r(5,5)这些东西现在还没人知道它们的准确取值。 第三章 组合数学中出现最频繁的问题可以说就是对于某种有趣排列的计数了。目前为止一切的计数都依赖于两个原理:加法原理和乘法原理。前者指构成一排列共有两类不同的方法,第一类有a种,第二类有b种,那么构成这排列就有a+b种不同的方法;后者指构成一排列可以用两步来完成,第一步有a种方法,不论第一步选择何种方法第二步都有b种方法,那么构成这排列就有a×b种不同的方法。另外还有可以由它们推导出来的减法原理和除法原理,它们的使用可以使某些求解变得方便。 排列和组合是由基本技术原理导出的更高级的组合数学工具。 n个元素的集合中取出r个元素排成一排,共有P(n,r)种方法。P(n,r) = n × (n-1) × … × (n-r+1) = n! / (n-r)!。它的证明就是说这一排里的第一个元素可以从n个里面选,第二个可以从n-1个里面选,……,第n个可以从n-r+1个里面选,根据乘法原理可得。如果不是排成一排,而是排成一个圈,那么沿用刚才构造性的方法,每一个合法的方案出现了r次,根据除法原理,n个元素的循环r-排列的个数就是P(n,r)/r。 从n个元素的集合中取出一个大小为r的子集,共有C(n,r)个方法,C(n,r)就是组合数。C(n,r) = P(n,r) / r! = n! / ( r! (n-r)! )。可以通过利用乘法原理证明 C(n,r) × n! = P(n,r) 来得出这个公式。组合数这个东西可以构成很多恒等式,例如C(n,0)+C(n,1)+…+C(n,n)=2^n。这个恒等式可以通过“算两次”的方法证明,这种方法是利用组合方法(而非代数方法)证明恒等式最常用的途径。 在排列问题中,如果每个元素都可以被取无数次,或者说待取元素的集合中是一个多重集,其中每一个都出现无数次。那么方法数就是r^n。如果多重集的k个元素中第i个元素出现n_i次(Σn_i = n),那么排列总数就是n! […]