n第三章 问题求解第 1 节 组合数学初步1、排列与组合历史1772 年,旺德蒙德以[n]p 表示由 n 个不同的元素中每次取 p 个的排列数。而欧拉则于1771 年以及于 1778 年以表示由 n 个不同元素中每次取出 p 个元素的组合数。至 1872 年,埃汀肖森引入了以表相同之意,这组合符号(SignsofCombinations)一直沿用至今。1830 年,皮科克引入符号 nCr 以表示由 n 个元素中每次取出 r 个元素的组合数;1869年或稍早些,剑桥的古德文以符号 nPr 表示由 n 个元素中每次取 r 个元素的排列数,这用法亦延用至今。按此法,nPn 便相当於现在的 n!。1880 年,鲍茨以 nCr 及 nPr 分别表示由 n 个元素取出 r 个的组合数与排列数;至 1899 年,克里斯托尔以 nPr 及 nCr 分别表示由 n 个不同元素中每次取出 r 个不重复元素的排列数与组合数,并以 nHr 表示相同意义下之可重复的排列数,这三种符号也通用至今。两个基本原理是排列和组合的基础(1) 加法原理:做一件事,完成它可以有 n 类办法,在第一类办法中有 m1 种不同的方法,在第二类办法中有 m2 种不同的方法,……,在第 n 类办法中有 mn 种不同的方法,那么完成这件事共有 N=m1+m2+m3+…+mn 种不同方法。(2)乘法原理:做一件事,完成它需要分成 n 个步骤,做第一步有 m1 种不同的方法,做第二步有 m2 种不同的方法,……,做第 n 步有 mn 种不同的方法,那么完成这件事共有 N= m1×m2×m3×…×mn 种不同的方法。这里要注意区分两个原理,要做一件事,完成它若是有 n 类办法,是分类问题,第一类中的方法都是独立的,因此用加法原理;做一件事,需要分 n 个步骤,步与步之间是连续的,只有将分成的若干个互相联系的步骤,依次相继完成,这件事才算完成,因此用乘法原理。这样完成一件事的分“类”和“步”是有本质区别的,因此也将两个原理区分开来。排列和排列数(1) 排列:从 n 个不同元素中,任取 m(m≤n)个元素,按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列。从排列的意义可知,如果两个排列相同,不仅这两个排列的元素必须完全相同,而且排列的顺序必须完全相同,这就告诉了我们如何判断两个排列是否相同的方法。(2)排列数公式:从 n 个不同元素中取出 m(m≤n)个元素的所有排列排列的记号和公式为 Pm n!(n m)!当 m=n 时,为全排列 nPn=n*(n-1)*(n-2)…3*2...