第1章排列与组合
1.1组合学简史
计数原理、排列组合缘于人们对生活中存在的数与形及其关系的发现和认识，最早可以追溯到五千年以前。《易经》中用十个天干和十二个地支以六十为周期来记载月和年，河图、洛书中关于幻方的记载，这些可能是最早研究的组合问题。有学者考证，易经诞生于五千年前，也有人考证说它诞生于七千年前，而成书的年代则是在商末周初，这对于教学并不重要。传统上一般认为《易经》起源自“河图、洛书”。相传伏羲时期黄河出现了背上画有图形的龙马，洛水出现了背上有文字的灵龟，于是圣人伏羲画出了“先天八卦”。殷商末年，周文王又根据伏羲的“先天八卦”演绎出了“后天八卦”，也就是“文王八卦”，并进一步推演出了六十四卦，并作卦辞和爻辞，春秋时期，孔子作《易传》。所以《易经》又有“人更三圣，世历三古”的说法。也就是说，《易经》经历了上古、中古、下古三个时代，由伏羲、文王、孔子三个圣人完成。古人对组合学的研究不仅由来已久，而且颇为深奥。
古希腊的阿基米德可能是对组合问题研究得最早的西方人，考古学家发现了1000多年前写在羊皮纸上的阿基米德手稿的副本，2003年，这篇论文被成功破译了出来，发现研究的是“十四巧板”问题。阿基米德试图计算将14条不规则的纸带拼成正方形所有可能的拼法，现在大家把这个问题称为贴瓷砖(tiling)问题。斯坦福大学的教授也研究了这个问题，并设立了一个100美金的奖项来征集答案。伊利诺伊大学计算机系的比尔·卡特勒借助计算机得出的答案是17152种拼法。不过数学家们希望找到一种数学证明，他们用纸和笔对排列进行分类，共24个基本族，基本解法是536种，考虑旋转32种，答案也是17152种。
历史上最著名的组合问题是宋朝时期所谓的“贾宪三角”，在公元11世纪至12世纪间，贾宪首先发现了二项式系数，后来杨辉将它整理记载在他的《续古抉奇法》一书中。这就是后人通常所说的杨辉三角。差不多同时期发现这个组合数的不仅是贾宪，印度的婆什迦罗也发现了这种组合数，这位数学家对微积分也是有贡献的，事实上他比牛顿与莱布尼茨更早地研究了微积分(大约早500年)。帕斯卡研究这个问题则是在17世纪中叶。组合论的系统研究应该缘于德国数学家莱布尼茨，他与牛顿被公认为共同发明了微积分，莱布尼茨所著《论组合的艺术》是组合数学的第一部专著，他在书中首次使用了组合论(combinatorics)一词。
虽然一般的数学史对组合数学的介绍并不多见，但随着组合数学的发展，它已经逐步形成了数学的一个重要分支并且其方法与思想已经渗透到众多数学领域乃至自然科学。例如生命科学中DNA的结构本质上就是组合数学中的序列结构。计算机科学的核心则是利用算法处理离散数据，而广义的组合数学就是离散数学。组合数学是图论、代数结构、数理逻辑等的总称，它是一门研究离散对象的科学。图论、拓扑、分析学等数学分支与组合数学都有着千丝万缕的联系。组合数学大致可以分为经典组合学、组合设计、组合序、图与超图和组合多面形与最优化。中学阶段介绍的计数原理及排列组合属于组合数学的最基础部分，虽然内容是十分基础与传统的，但教法上却有一定的难度。
1.2排列组合教学策略
1.2.1计数原理
1.2排列组合教学策略
与教材的很多内容相比，这部分内容的编写逻辑是比较顺畅的，如果本着精益求精的原则，依然有可以改善之处。某版本教材通过交通问题引入加法原理与乘法原理无可厚非，不过如果考虑到教材的前后呼应以及适当的难度梯度，可能换一种方式更合适一些。这一章是概率的基础，如果能做到问题相对统一或许更好。例如不妨通过如下几个问题层层展开。
问题1工商部门为了检查某个厂家的某类商品是否合格，决定从该商品的各大销售点抽取产品检验，已知该产品共有n个经销点，每个经销点分别有该产品m1,m2,…,mn件，如果从市场上所有的该商品中任意抽取一件，共有多少种抽取方法？
这个问题实际上反映了一般的加法原理，学生也很容易理解，而且为后面的排列组合问题打下了基础，因为只要针对同样的情境把问题设计得稍微一般一点，就可以引出一般的排列组合问题。
问题2工商部门为了检查某个厂家的某类商品是否合格，决定从该商品的各经销点抽取产品检验，已知该商品共有n个经销点，每个经销点分别有该商品m1,m2,…,mn件，如果从市场上该商品的每个经销点各抽取一件，共有多少种抽取方法？
“从市场上所有该商品中抽取一件”运用的是加法原理，而“每个经销点各抽取一件”运用的则是乘法原理。这两个问题的好处在于难度不大，但又不像教材中的例子那样稍显肤浅，学生可以轻而易举地回答。
通过上面两个问题的分析，学生自己就可以总结出一般的加法原理(分类计数原理)与乘法原理(分步计数原理)。此外，我们认为，用加法原理与乘法原理命名这两个原理可能更合适一点，既符合习惯，也更能反映这两个原理的本质。例如，问题2中也许是工商部门分派人手同时到各个经销点抽取样品，抽取是同时进行的，哪里来的分步进行？教材中的例子容易让学生陷入思维陷阱。就产品抽检而言，既有可能是同时从各个经销点抽样，也有可能是同一个(或一批)人分别从各个经销点依次抽样(即分步进行)，甚至有可能是每个人分别从若干个经销点抽样，无论是什么样的抽检顺序，本质都只有一个： 从每个经销点抽取一个样品。不应该让非本质的程序化过程掩盖数学的本质。
1.2.2排列
与组合相比，排列概念的教学难度不是很大，不过教材引入的问题显得松散了一点，某版教材首先从选班长开始：
考察下面两个问题：
(1) 高二(1)班准备从甲、乙、丙这3名学生中选出2人分别担任班长和副班长，有多少种不同的选法？
(2) 从1,2,3这3个数字中取出2个数字组成两位数，这样的两位数共有多少个？
上面的两个问题有什么共同特征？可以用怎样的数学模型来刻画？
第一个问题尚有一定的生活意义，虽然现实中选班长是有条件的选择，通常是学生投票表决或老师指定，但作为一种可能性分析也是可以的。在这两个例子的基础上引出了排列的概念，接下来又举出了有4个元素的例子：
例1(1) 写出从a,b,c,d这4个字母中，取出2个字母的所有排列；
(2) 写出从a,b,c,d这4个字母中，取出3个字母的所有排列。
有了教材开头的两个例子，其实不需要再针对特殊情形单独举例，可以稍微一般化，在对一般化问题的分析过程中可以根据需要选择某些特殊情形，这样更符合科学研究的习惯。既然我们的课程标准强调生活化，这类问题恰恰具有比较重要的现实价值，例如可以创设如下的问题情境。
问题3物流公司要运送一批货物到n个不同的目的地，为了计算运输成本，在优化运输路径之前，需要搞清楚有多少种不同的方法将货物运送到各个目的地，进而核算成本，选择最佳路径。你能帮物流公司计算一下有多少种不同的运输路线吗？
这是个具有经济意义的简单物流问题，学生并不难理解，不妨先从n=3,4，5等开始，逐步过渡到一般的n。在此基础上，考虑稍微复杂一点的问题：
问题4物流公司要运送一批货物到n个不同的目的地，由于运输条件的限制，一次只能送达其中的m(m解决了上述两个问题，排列问题也就清楚了，在此基础上可以抽象出一般的排列概念，并归纳出排列数公式。
如果觉得需要，还可以通过下面的例子稍微拓展一下：
问题5如果你用0~9十个数字为你的计算机设置首位不为0且无重复数字的6位数密码，请问可以设置多少种密码？
这个问题的难度在于首位数不能为0，学生需要细加分析后才能搞明白。实际的密码可能会出现重复数字，所以可能的情况下可以进一步延伸一下上面的问题：
问题6如果你用0~9十个数字为你的计算机设置首位不为0的6位数密码，请问可以设置多少种密码？
问题7如果你用0~9十个数字及26个小写英文字母为你的计算机设置首位不为0且无重复字符的8位数密码，请问可以设置多少种密码？
计算排列数并不是一件困难的事情，教师完全没有必要像教材那样将4个字母的各种可能情形罗列出来，显得比较烦琐。最简单的办法是画一个有n个格子的框，然后考察用m(m≥n)个标有不同数字的虚拟物体分别往第1个格子、第2个格子、……、第n个格子里“放”，看共有多少种可能的放置方法？教材最后的总结还是比较到位的。
1.2.3组合
组合是教学的一个难点，应用也最为广泛，无论是后续的二项式定理还是概率论中的古典概型以及二项分布等都与之有关，而且其中可能出现很困难的问题。教材通过两个与排列类似的问题引入：
考察下面两个问题：
(1) 高二(1)班从甲、乙、丙这3名同学中选2名代表，有多少种不同的选法？
(2) 从1,2,3这3个数字中取出2个数字，能够组成多少个不同的集合？
这两个问题与上一节中相应的排列问题有何区别？有何联系？
如果说问题(1)尚且算是一个有点意义的问题，问题(2)就有点牵强了，不过教材通过这两个例子解释排列与组合的不同还是比较清楚的。遗憾的是，教材引入组合的概念显得匆忙了一点，至少应该在此之前举一个稍微一般一点的例子。在给出了组合的概念后，接着又引出了下面的例子：
例1
写出从a,b,c这3个元素中，每次取出2个元素的所有组合。
例1与问题(2)有什么不同吗？为什么不直接针对问题(2)进行计算呢？同样的问题是，在介绍了这个例子之后，马上给出了一般性的组合数概念，这个跳跃度显得大了一点。此后直接给出了组合数的计算公式：
一般地，求从n个不同元素中取出m个元素的排列数Amn,可以分为两步：
第一步： 先求出从这n个不同元素中取出m个元素的组合数Cmn;
第二步： 求每一个组合中m个元素的全排列数Amm。
根据分步计数原理，得到Amn=Cmn·Amm，因此，我们得到组合数公式
Cmn=AmnAmm=n(n-1)(n-2)…(n-m+1)m!,
这里n,m∈N*，并且m≤n。因为
Amn=n!(n-m)!,
所以，上面的组合数公式还可以写成
Cmn=n!m!(n-m)!。
从问题(1)、(2)到组合数公式之间似乎缺少了一个过渡过程，如果中间辅以一个稍微一般性的例子并对组合数做出分析，或许学生更容易理解。组合数公式后以从a,b,c,d 4个元素中取出3个元素为例列出一个表格，我们觉得这个表格对于学生理解一般组合数公式并不能带来实质性的帮助，因为一般的组合数公式并不能通过列表来计算，应该通过特殊情况的组合数计算寻找一般的规律。如果在组合数公式前对一般情形做更细致的分析，也就是在“感知”与“抽象”之间增加“归纳”“概括”过程或许更能帮助学生理解这个公式。
问题8工商部门经常会对市场上的产品进行合格检查，在产品数量比较庞大的情况下，一般都是抽取部分商品检测。假设某商场有某种商品n件，现从这n件商品中任意抽取m(m
可以通过这个例子引导学生分析排列数与组合数之间的关系，不妨先从5件商品中抽取若干件开始进行分析，例如，如果从5件商品中任意抽取3件商品，有多少种抽取方法？显然抽取出来的商品不需要进行排序，为了算出组合数，姑且先假设5件商品标着不同的序号(例如每件商品实际上都有二维码)，考察任意抽取3件的排列数A35，排列数的计算过程既可以用前面画格子的办法计算，也可以分步计算，即先计算从5件商品中任意抽取3件的组合数，然后再将每次抽取出来的商品排序，这两步过程合在一起与前面的画格子排列方法的计算结果是一样的。每次取出来的3件商品有多少种排列方法？显然是3！，因此从5件商品中任意抽取3件的排列数等于任意抽取3件商品的组合数与3件商品全排列的乘积： A35=C35·A33。检测商品实际是不需要考虑顺序的，也就是商品被抽取出来后不需要再排序了，所以组合数应为5件商品任意抽取3件商品的排列数除以3件商品的排列数，即
C35=A35A33。
在此基础上过渡到一般情形，那么一般的组合数公式就好解释了。
计数应用题的选择有值得斟酌之处，教材拟了两个例子：
例1高二(1)班有30名男生，20名女生。从50名学生中选3名男生、2名女生分别担任班长、副班长、学习委员、文娱委员、体育委员，共有多少种不同的选法？
例22名女生、4名男生排成一排，问：
(1) 2名女生相邻的不同排法共有多少种？
(2) 女生甲必须排在女生乙的左边(不一定相邻)的不同排法共有多少种？
从排列数公式与组合数公式一下子跳到类似例2的问题，难度梯度是不是太大了一点？此外，现实中恐怕没有哪个班级如例1那样选择班干部，总会附加一些条件，所以，这是一个不真实的生活情境。如何创设一些承载类似问题的真实情境，值得教师们认真思考。我们不妨将原问题稍作修改，或许更真实一些。
问题9某中学高二(1)班有30名男生，20名女生，学校为了考察各班同学平时锻炼身体的情况，决定从50名学生中任选3名男生、2名女生与其他班级同学一起分别参加5项不同的体育竞赛，每个同学只能任选一个项目，共有多少种不同的选法？
如果想拓展一下，还可以进一步这样设计：
问题10某中学高二(1)班有30名男生，20名女生，学校为了考察各班同学平时锻炼身体的情况，决定从50名学生中任选3名男生、2名女生与其他班级同学一起分别参加10个体育项目中的5项竞赛，每个同学只能任选一个项目，共有多少种不同的选法？
现实中这两类事情都是有可能发生的，如果需要继续拓展，可以在问题10的基础上再次改进：
问题11某中学高二(1)班有30名男生，20名女生，学校为了考察各班同学平时锻炼身体的情况，决定从50名学生中任选3名男生、2名女生与其他班级同学一起分别参加10个体育项目中的5项竞赛，每个同学只能任选一个项目，但其中100m跨栏只能女生参加，110m跨栏只能男生参加，共有多少种不同的选法？
如果不是为了竞赛，作为中学生，到这个难度应该可以了。
1.2.4二项式定理
如果不去牵强附会地创设一些所谓的生活化情境，教材的处理还是相对比较得体的，例如二项式定理的处理就可圈可点，先从2次、3次因式的展开过渡到任意n次二项式展开，从中分析出系数的规律，从定理的证明到几个例子的选择都是适当的。美中不足的是，教材一如既往地没有以通常定理的陈述方式呈现二项式定理，我们觉得这是教材的一大败笔，无论是一个新概念还是新命题、新定理的出现，最好以一种惯用的标准方式陈述，它对于加深学生的印象还是有一定帮助的。
二项式系数的性质最好能做一番直观解释，这对于以后的概率论学习会有帮助，否则学生只会机械套用。教材中给出了二项式系数的4个重要性质：
(1) Cmn=Cn-mn。
(2) Cmn+Cm-1n=Cmn+1。
(3) 当m<(n-1)/2时，Cmn(n-1)/2时，Cm+1n(4) C0n+C1n+…+Cnn=2n。
Cmn为什么等于Cn-mn？ 可以这样解释性质(1)： 从n个元素中抽取m个元素后还剩下多少元素？显然是n-m，这就是说，每抽取m个元素，就剩下n-m个元素，反之，如果抽取n-m个元素，则剩下m个元素，因此从n个元素中抽取m个元素与从n个元素中抽取n-m个元素有一样多的方法。
性质(2)可以这样解释： 在n+1个元素中先取定一个元素，再从n+1个元素中取出m个元素有两种可能，一种是取出来的m个元素中含事先取定的元素，另一种可能是不含事先取定的元素。如果含事先取定的元素，那么只需要从剩下的n个元素中任取m-1个元素即可，如果不含事先取定的元素，则从剩下的n个元素中任取m个元素，因此有
Cmn+1=Cmn+Cm-1n。
性质(3)的后半部分根据性质(1)很容易得到，关键是前半部分的解释。这个问题的分析相对复杂一些，假设从n个元素中任意选取m+1个元素，共有Cm+1n种方法。我们还有一种选取方法，先从n个元素中选取m个元素，共有Cmn种方法，再从剩下的n-m个元素中选取一个，共有C1n-m种方法，但这种选取方法显然有了先后顺序，也就是第二次选取出来的元素与第一次选取出来的m个元素之间有了先后顺序，第m+1个元素与前面的m个元素间有多少种可能的顺序呢？打个比方，m个人随便站成一排，不考虑顺序，第m+1个人可以插队，有多少种插队方法？显然有m+1种，把这个顺序除去之后得到的就是m+1个的组合数了。因此有
Cm+1n=CmnC1n-mm+1=Cmn(n-m)m+1。
性质(4)是比较重要的，它说明了一个具有n个元素的集合共有多少子集。例如，一个随机试验的样本空间有n个元素，那么这个随机试验共有多少个随机事件？这个问题相当于问样本空间的子集全体构成的集合含多少元素。以班级为例，如果一个班有50人，那么从班级任意选取若干人参加某个活动的方法有多少种？其中包括放弃参加与全体出动，显而易见，共有C050+C150+…+C5050=(1+1)50=250种选取方法。做出这些解释后，学生就能理解这些性质的内在含义，不需要死记硬背也能懂得如何运用。
如果搞清楚计数原理、排列组合的本质，教案的设计就不是一件困难的事情了，本章略去教案设计。
