高中数学组合计数问题教学设计

简单的组合计数问题浙江省镇海中学沈虎跃【教学目标】【知识与技能】1、灵活应用分类相加原理与分步相乘原理进行计数．2、掌握基本的组合数恒等变形.【过程与方法】通过解决几个简单的组合计数问题的学习，使学生进一步熟练掌握解决简单的组合计数问题的常用思考方法．【情感、态度价值观】1、渗透解决问题从自然的想法出发，从简单问题入手的基本原则．2、使学生表达清晰、思考有条理．3、通过引导学生主动参与分析解决问题，培养学生的探索精神，及锲而不舍的精神．【重点难点】重点：灵活应用分类相加原理与分步相乘原理进行计数．难点：如何将问题进行适当的分类或分步．【突破方式】通过典型例题的师生互动分析、共同解决，加深学生对两个基本计数原理的理解；通过引申变式训练，进一步深化其应用．【教学策略】【教学顺序】课题引入，方法展示，互动探究，方法构建，练习巩固，归纳小结．【教学方法与手段】1．采用师生互动的方式，在教师的引导下，学生通过思考、交流、讨论、辨析，加深学生对两个基本计数原理的理解，体验自主探索、合作交流的学习方式，充分发挥学生的积极性与主动性．2．利用计算机辅助教学．【教学过程】一、课题引入本课我们主要通过共同解决几个简单的组合计数问题来进一步理解基本计数原理、掌握组合计数中一些常用方法与技巧。同学们最喜欢听技巧，最好来“四两拨千斤”，要知道如果用杠杆原理来做的话，你的运动位移是抬起高度的2500倍，你以更长的位移换取更小的力。数学上大概也如此，想到用更简洁的方法与技巧，大概要付出更长的思考时间，当然数学上更长的思考时间可以在平时进行，还是那句老话，“一份辛苦，一份收获”。对于组合数学我很欣赏………。不妨从一个简单的例子来展示一下。二、方法展示【引例】n元集S={1,2,3,…,n}的子集个数为。方法1：按照子集中含有元素的个数分类计数：含有k个元素的子集有knC（k=0,1,2,3,…,n）个,则共有子集02nknnkC。其中揭示了组合计数中一个基本原理：分类相加原理，即完成一件事情可分成n类，第i类有iM种方式，则完成这一件事情共有1niiNM种方式。方法2：按照每一个元素的归属分步计数：设AS，我们考虑，1A或1A有2种方式，2A或2A有2种方式，一般地，kA或kA有2种方式，当1，2，3，…，n这n个元素的归属确定，则子集A中的元素也就确定下来了，这样共有2222n个不同的子集。其中揭示了组合计数中一个基本原理：分步相乘原理，即完成一件事情可分成n步，第i步有iM种方式，则完成这一件事情共有1niiNM种方式。以上两种方式及其揭示的原理是组合计数中的两个基本原理，在今后的计数中经常用到。当然对于一个关于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}的子集个数为na，则12a，则n＋1元集{1,2,3,…,n＋1}的子集个数为1na，同时这些子集可以分成两类：第一类，不含n＋1，有na个；第二类，含n＋1，只需在每不含n＋1的子集中添加n＋1即可，这样也有有na个。故1122nnaaa即2nnanN三、互动探究【例1】已知A∪B={1,2,3,┄,n}，则有序集合对(A,B)的个数为。方法1：（按A中的元素个数分类）：设|A|=k,则此时B的构成如下:A中的每个元素可取也可不取,其余元素全取,故有序集合对(A,B)的个数为02(12)3nkknnnkC方法2：（分步而言）：①（如图）将A∪B分成A－B、A∩B、B－A互不相交的三个部分即分为三类，则i可以放在这三类中的任意一类（i＝1,2,3,┄,n），故共有3n个有序集合对。②对于元素i有iA，iA两种选择，又iB，iB两种选择,再除去i不在A，也不在B中的情形，即有2(21)种方式（i＝1,2,3,┄,n），故共有2(21)3nn个有序集合对。【引申1】已知A∪B∪C={1,2,3,┄,n}，则三元有序集合组(A,B,C)的个数为。方法1：（按A∪B中的元素个数分类）：设|A∪B|=k,则C的选择方式有2k种,满足|A∪B|=k的集合对(A,B)有3k中,这样故三元有序集ABABC合组(A,B,C的个数为032(16)7nkkknnnkC方法2：（分步而言）：①（如图）恰好分成互不相交的7部分，故共有7n个有序集合对。②对于元素i有iA，iA两种选择，iB，iB两种选择,又iC，iC两种选择,再除去i不在A，不在B中,也不在C中的情形，即有3(21)种方式（i＝1,2,3,┄,n），故共有3(21)7nn个有序集合对。【引申2】已知A∪B∪C∪D={1,2,3,┄,n}，则四元有序集合组(A,B,C,D)的个数为。方法1：（分类而言）：072(114)15nkkknnnkC方法2：（分步而言）：①（如图）画四个圆能行吗？不行！（为什么肯定不行？）当然画图还可以，比如②同【引申1】、【引申2】可知，故共有4(21)15nn个有序集合对。【引申3】已知A1∪A2∪…∪Ak={1,2,3,┄,n}，则n元有序集合组(A1,A2,…,Ak)的个数为。对于k较大时画图比较麻烦，采用方法2比较恰当，这样可得共有(21)kn个有序集合对。数学归纳法四、方法构建1、将问题恰当地分类或分步2、从简单入手（包括简单的想法、问题的特殊化等）五、练习巩固【练习】用1，2，3，4，5，6组成一个n位整数，其中数字1出现偶数次有多少个？解:设1在n位整数中出现2i次(0,1,2,,)2ni,2220(51)(51)64522nnnnnniiniC.附（递推法）:设A={用1，2，3，4，5，6组成一个n位整数，其中数字1出现偶数次的个数}设||,nAA则11115(6),5nnnnAAAA,11116()4444nnnnnAA,即1133[1()]11322[1()]34422412nnnnAA*1(46)2nnnAnN.【引申1】用1，2，3，4，5，6组成一个n位整数，其中数字1，2均出现偶数次有多少个？解:设1,2在n位整数中共出现2i次(1,2,,)2ni,其中1出现2j次(1,2,,)ji,则1，2均出现偶数次有22222004niniijniijCC=2222222221011444422nninniijnniiininijiCCC2222111(42)(42)4424[4]222nnnnniiinnniC*62424nnnnN附（递推法）:设na：表示在n位整数中1出现偶数次,2出现偶数次的个数；nb：表示在n位整数中1出现奇数次,2出现偶数次的个数；nc：表示在n位整数中1出现偶数次,2出现奇数次的个数；nd：表示在n位整数中1出现奇数次,2出现奇数次的个数；则1114nnnnabca①1114nnnnbdab②1114nnnncdac③1114nnnndbcd④由①-④得1111114()4()4(40)4nnnnnnnadadad由②-③得1111114()4()4(11)0nnnnnnbcbcbc又令nnnAad即1,2均出现次数同奇偶的个数;nnnBbc即1,2均出现次数异奇偶的个数;所以1124nnnABA(可由①+④得)⑤1124nnnBAB(可由②+③得)⑥由⑤+⑥得6nnnAB由⑤-⑥得1111422nnnnABABAB所以,622nnnA所以,*624162422[()()]224nnnnnnnnnnnaadadnN【引申2】用1，2，3，4，5，6组成一个n位整数，其中数字1，2至少一个出现偶数次有多少个？解:设A={n位整数中1出现偶数次的个数}；B={n位整数中2出现偶数次的个数}则AB={n位整数中1，2均出现偶数次的个数}，由上面的讨论可知,*1||(46),2nnAnN*1(46)2nnnBnN，|AB|=*62424nnnnN故*624236242||||||||4644nnnnnnnnABABABnN【例3】设自然数k满足121001100，1,2,,100,,kaaa对的任一个排列，取最小的mk，使12,,,mkaaaa至少小于中1k个数，已知满足1ma的数列的个数为100!4.求k。解答：将12,,kaaa重新排列成12kbbb，由m的最小性，设2bt，则(1,2,1)miatatikkm，当t固定时.由1.bt且b1不能为1，故b1有t2种取法，而3,,kbbt故有2100ktC种取法，而将b1,b2,……bk排列有k!种，于是确定12,,,kaaa有(t2)2100ktCk!种,而前面分析(1,2,,1)iatikkm,而在大于t的100t个数中除去34,,,kbbb还有100(2)102tktk个数。故有1102mktkA种取法,而1ma是固定的,其余数1na100a排列有(100)!m种。综上满足1ma的排列个数1021032110010231(2)!(100)!ktkmkttktmkTtCkAm10210331(100)!(102)!(2)!(100)!(2)!(102)!(103)!kttmktkttkmkkttm10210331(100)!(3)!(2)(1)(100)!(103)!(3)!kttmkmttkkttmt102103310031(2)!(1)(100)!kttmtmktkktC10221100113(2)!(1)(100)!()ktmmmknnnttkktCCCC因1023(100)!(1)(100)!(102)!ktkkktkt1023(100)!(2)!(1)(100)!(102)!(2)!kttkkkkktk10221003!(100)!kkttkkC19898!!(100)!!(100)!(1)!(99)!kkkCkkkk(100)98!kk由已知100!4T，故有100!(100)98!4mk2100992504555kkk或六、归纳小结这节课和同学们一起解决了几个简单的组合计数问题，主要运用分类相加原理与分步相乘原理，及从简单做起的想法，希望同学们仔细体会其应用，做到举一反三。当然组合计数的方法还有很多，如：利用容斥原理、生成函数、一一对应等方法。