资源描述
简单的组合计数问题 浙江省镇海中学 沈虎跃 【教学目标】【知识与技能】1、灵活应用分类相加原理与分步相乘原理进行计数2、掌握基本的组合数恒等变形.【过程与方法】通过解决几个简单的组合计数问题的学习，使学生进一步熟练掌握解决简单的组合计数问题的常用思考方法【情感、态度价值观】1、渗透解决问题从自然的想法出发，从简单问题入手的基本原则2、使学生表达清晰、思考有条理3、通过引导学生主动参与分析解决问题，培养学生的探索精神，及锲而不舍的精神【重点难点】重点：灵活应用分类相加原理与分步相乘原理进行计数难点：如何将问题进行适当的分类或分步【突破方式】通过典型例题的师生互动分析、共同解决，加深学生对两个基本计数原理的理解；通过引申变式训练，进一步深化其应用【教学策略】【教学顺序】课题引入，方法展示，互动探究，方法构建，练习巩固，归纳小结【教学方法与手段】1采用师生互动的方式，在教师的引导下，学生通过思考、交流、讨论、辨析，加深学生对两个基本计数原理的理解，体验自主探索、合作交流的学习方式，充分发挥学生的积极性与主动性2利用计算机辅助教学【教学过程】一、课题引入本课我们主要通过共同解决几个简单的组合计数问题来进一步理解基本计数原理、掌握组合计数中一些常用方法与技巧。同学们最喜欢听技巧，最好来“四两拨千斤”，要知道如果用杠杆原理来做的话，你的运动位移是抬起高度的2500倍，你以更长的位移换取更小的力。数学上大概也如此，想到用更简洁的方法与技巧，大概要付出更长的思考时间，当然数学上更长的思考时间可以在平时进行，还是那句老话，“一份辛苦，一份收获”。对于组合数学我很欣赏。不妨从一个简单的例子来展示一下。二、方法展示【引例】n 元集S=1,2,3,n的子集个数为 。方法1：按照子集中含有元素的个数分类计数：含有k个元素的子集有（k=0,1,2,3,n）个,则共有子集。其中揭示了组合计数中一个基本原理：分类相加原理，即完成一件事情可分成n类，第i类有种方式，则完成这一件事情共有种方式。方法2：按照每一个元素的归属分步计数：设AS，我们考虑，1A或1A有2种方式，2A或2A有2种方式，一般地，kA或kA有2种方式，当1，2，3，n这n个元素的归属确定，则子集A中的元素也就确定下来了，这样共有个不同的子集。其中揭示了组合计数中一个基本原理：分步相乘原理，即完成一件事情可分成n步，第i步有种方式，则完成这一件事情共有种方式。以上两种方式及其揭示的原理是组合计数中的两个基本原理，在今后的计数中经常用到。当然对于一个关于n的问题我们也可以从简单做起、从小做起的角度考虑.当n=1时，子集个数为2个即，1当n=2时，子集个数为4个即，1，2，1,2当n=3时，子集个数为8个即，1，2，1,2，3，1,3，2,3，1,2,3也就是说，我们只需将前一种方式排出，则下一种即可作出。方法3：递推法计数：设n 元集S=1,2,3,n的子集个数为，则，则n1 元集1,2,3,n1的子集个数为，同时这些子集可以分成两类：第一类，不含n1，有个；第二类，含n1，只需在每不含n1的子集中添加n1即可，这样也有有个。故即三、互动探究【例1】已知AB=1,2,3,n，则有序集合对(A,B)的个数为 。AB方法1：（按A中的元素个数分类）：设|A|=k,则此时B的构成如下:A中的每个元素可取也可不取,其余元素全取,故有序集合对(A,B)的个数为方法2：（分步而言）：（如图）将AB分成AB、AB、BA互不相交的三个部分即分为三类，则i可以放在这三类中的任意一类（i1,2,3,n），故共有个有序集合对。 对于元素i有iA，iA两种选择，又iB，iB两种选择,再除去i不在A，也不在B中的情形，即有种方式（i1,2,3,n），故共有个有序集合对。ABC【引申1】 已知ABC=1,2,3,n，则三元有序集合组(A,B,C)的个数为 。方法1：（按AB中的元素个数分类）：设|AB|=k,则C的选择方式有种, 满足|AB|=k的集合对(A,B)有中,这样故三元有序集合组(A,B,C的个数为方法2：（分步而言）：（如图）恰好分成互不相交的7部分，故共有个有序集合对。 对于元素i有iA，iA两种选择， iB，iB两种选择, 又iC，iC两种选择,再除去i不在A，不在B中, 也不在C中的情形，即有种方式（i1,2,3,n），故共有个有序集合对。【引申2】已知ABCD=1,2,3,n，则四元有序集合组(A,B,C,D)的个数为 。方法1：（分类而言）：方法2：（分步而言）：（如图）画四个圆能行吗？不行！（为什么肯定不行？）当然画图还可以，比如同【引申1】、【引申2】可知，故共有个有序集合对。【引申3】已知A1A2Ak=1,2,3,n，则n元有序集合组(A1,A2,Ak)的个数为 。对于k较大时画图比较麻烦，采用方法2比较恰当，这样可得共有个有序集合对。数学归纳法四、方法构建1、将问题恰当地分类或分步2、从简单入手（包括简单的想法、问题的特殊化等）五、练习巩固【练习】用1，2，3，4，5，6组成一个n位整数，其中数字1出现偶数次有多少个？解:设1在n位整数中出现次,.附（递推法）:设A=用1，2，3，4，5，6组成一个n位整数，其中数字1出现偶数次的个数设则, 即.【引申1】用1，2，3，4，5，6组成一个n位整数，其中数字1，2均出现偶数次有多少个？解: 设1,2在n位整数中共出现次,其中1出现次,则1，2均出现偶数次有=附（递推法）: 设：表示在n位整数中1出现偶数次,2出现偶数次的个数；：表示在n位整数中1出现奇数次,2出现偶数次的个数；：表示在n位整数中1出现偶数次,2出现奇数次的个数；：表示在n位整数中1出现奇数次,2出现奇数次的个数；则 由-得由-得又令即1,2均出现次数同奇偶的个数;即1,2均出现次数异奇偶的个数;所以(可由+得) (可由+得) 由+得 由-得 所以,所以,【引申2】用1，2，3，4，5，6组成一个n位整数，其中数字1，2至少一个出现偶数次有多少个？解:设A=n位整数中1出现偶数次的个数；B=n位整数中2出现偶数次的个数则AB=n位整数中1，2均出现偶数次的个数，由上面的讨论可知,，| AB|=故【例3】设自然数 k满足，取最小的，使中个数，已知满足的数列的个数为. 求k。解答：将重新排列成，由m的最小性，设，则 当t固定时.由且b1不能为1，故b1有t2种取法，而故有种取法，而将b1,b2,bk排列有k!种，于是确定有 (t2)k!种,而前面分析,而在大于t的100t个数中除去还有个数。故有种取法,而是固定的,其余数排列有种。综上满足 的排列个数由已知，故有六、归纳小结 这节课和同学们一起解决了几个简单的组合计数问题，主要运用分类相加原理与分步相乘原理，及从简单做起的想法，希望同学们仔细体会其应用，做到举一反三。当然组合计数的方法还有很多，如：利用容斥原理、生成函数、一一对应等方法。
展开阅读全文