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

1、学习必备欢迎下载简单的组合计数问题浙江省镇海中学沈虎跃【教学目标】【知识与技能】1、灵活应用分类相加原理与分步相乘原理进行计数.2、掌握基本的组合数恒等变形 .【过程与方法】通过解决几个简单的组合计数问题的学习，使学生进一步熟练掌握解决简单的组合计数问题的常用思考方法.【情感、态度价值观】1、渗透解决问题从自然的想法出发，从简单问题入手的基本原则.2、使学生表达清晰、思考有条理.3、通过引导学生主动参与分析解决问题，培养学生的探索精神，及锲而不舍的精 神.【重点难点】重点：灵活应用分类相加原理与分步相乘原理进行计数.难点：如何将问题进行适当的分类或分步.【突破方式】通过典型例题的师生互动分析、

2、共同解决，加深学生对两个基本计数原理的理解； 通过引申变式训练，进一步深化其应用.【教学策略】【教学顺序】课题引入，方法展示，互动探究，方法构建，练习巩固，归纳小结.【教学方法与手段】.采用师生互动的方式，在教师的引导下，学生通过思考、交流、讨论、辨析，加深 学生对两个基本计数原理的理解，体验自主探索、合作交流的学习方式， 充分发挥学生的积极性与主动性.利用计算机辅助教学.【教学过程】一、课题引入本课我们主要通过共同解决几个简单的组合计数问题来进一步理解基本计数原理、掌握组合计数中一些常用方法与技巧。同学们最喜欢听技巧，最好来“四两拨千斤”，要知道如果用杠杆原理来做的话，你的运动位移是抬起高度

3、的2500倍，你以更长的位移换取更小学习必备欢迎下载的力。数学上大概也如此，想到用更简洁的方法与技巧， 大概要付出更长的思考时间， 当然 数学上更长的思考时间可以在平时进行， 还是那句老话，“一份辛苦，一份收获”。对于组合 数学我很欣赏 。不妨从一个简单的例子来展示一下。学习必备欢迎下载二、方法展示【弓I例】n元集S=1,2,3，,n的子集个数为 。方法1:按照子集中含有元素的个数分类计数：n含有k个元素的子集有Ck （k=0,1,2,3,n）个，则共有子集Z C； = 2n。k 0其中揭示了组合计数中一个基本原理：分类相加原理，即完成一件事情可分成n类，n第i类有Mi种方式，则完成这一件事情

4、共有N =Z Mi种方式。i 1方法2:按照每一个元素的归属分步计数：设ACS,我们考虑，1三A或1乏A有2种方式，2WA或2正A有2种方式，一般地，k三A 或kA有2种方式，当1, 2, 3,，n这n个元素的归属确定，则子集 A中的元素也就确 定下来了，这样共有 2m2m.m 2 = 2个不同的子集。其中揭示了组合计数中一个基本原理：分步相乘原理，即完成一件事情可分成n步，n第i步有M i种方式，则完成这一件事情共有N 二口 M i种方式。i 1以上两种方式及其揭示的原理是组合计数中的两个基本原理，在今后的计数中经常用 到。当然对于一个关于 n的问题我们也可以从简单做起、从小做起的角度考虑当

5、n=1时，子集个数为2个即0, 1当n=2时，子集个数为 4个即0, 1 , 2 , 1,2当 n=3 时,子集个数为 8个即 0, 1 , 2 , 1,2 , 3 , 1,3 , 2,3 , 1,2,3也就是说，我们只需将前一种方式排出，则下一种即可作出。方法3:递推法计数：设n元集S=1,2,3,n的子集个数为an ,则a1 = 2 ,则n+1元集1,2,3,n+1的 子集个数为an书，同时这些子集可以分成两类：第一类，不含n+1,有an个；第二类，含n+1,只需在每不含n+1的子集中添加n+1即可，这样也有有an个。故an书=2an a1 = 2即 an = 2n n N三、互动探究【例

6、1】已知AU B=1,2,3, , n,则有序集合对（A, B）的个数为 方法1:（按A中的元素个数分类）：设|A|=k,则此时B的构成如下： A中的每个元素可取也可不取，其余元素全取，故有序集合对（A, B）n的个数为 、Cnk 2k =（1 2）n = 3n k =0方法2:（分步而言）：（如图）将 AUB分成AB、APB、B A互不相交的三个部分即分为三类，则 i可 以放在这三类中的任意一类（i=1,2,3,一, n）,故共有3n个有序集合对。对于元素i有iA,国A两种选择，又iWB, i更B两种选择，再除去i不在A,也不在B中的情形，即有（22 1）种方式（i= 1,2,3, , n）

7、,故共有（22 1）n = 3n 个有序集合对。【引申1】 已知 AU BU C=1,2,3, n,则三元有序集合组（A, B,C）的个数为。方法1:（按AUB中的元素个数分类）：设|AUB|=k,则C的选择 方式有2k种，满足|AUB|=k的集合对（A, B）有3k中，这样故三元有序集学习必备欢迎下载n合组（A, B,C 的个数为 C Ck 3k 2k =（1+6）n =7n k 0方法2:（分步而言）：（如图）恰好分成互不相交的7部分，故共有7n个有序集合对。 对于兀素i有iwA, iA两种选择，iwB, iWB两种选择，又iwC, iWC两种选择, 再除去i不在A,不在B中，也不在C中的

8、情形，即有（231）种方式（i = 1,2,3, ,n）,故 共有（23 -1）n =7n个有序集合对。【引申 2】已知 AU BU CU D=1,2,3, , n,则四元有序集合组（A, B,C,D）的个数为。n方法 1：（分类而言）：z Cnk -7k 2k =（1+14）n =15nk =0方法2:（分步而言）：（如图）画四个圆能行吗？不行！（为什么肯定不行？）当然画图还可以，比如同【引申1】、【引申2】可知，故共有（24-1）n=15n个有序集合对。【引申3】已知A1UA2UU Ak=l,2,3, , n,则n元有序集合组（Ai, A2,，A.的个 数为。对于k较大时画图比较麻烦， 采

9、用方法2比较恰当，这样可得共有（2k1）n个有序集合 对。数学归纳法四、方法构建1、将问题恰当地分类或分步2、从简单入手（包括简单的想法、问题的特殊化等）五、练习巩固【练习】用1, 2, 3, 4, 5, 6组成一个n位整数，其中数字 1出现偶数次有多少个?解:设1在n位整数中出现2i次（i =0,1,2,.n ）,2 nc2nn 5n.;I:s12 一(5 1)n (5-1)n6n 4n2 一 21出现偶数次附（递推法）：设A=用1, 2, 3, 4, 5, 6组成一个n位整数，其中数字 的个数设 |A| = A，则 An =5An+（6n工AnQ,A1 =5,4 4311母力 221-32

10、1A =(4n 6n) nN.2学习必备欢迎下载【引申1】用1, 2, 3, 4, 5, 少个？6组成一个n位整数，其中数字 1, 2均出现偶数次有多解：设1,2在n位整数中共出现2均出现偶数次有2I次(I =12Jn )淇中1出现2j次(j =1,2,I),则1,I 4 r.21一=42n:4n -2 二-C：1C” : 4n .: 4n 二(：1 221 j 大 i2j 222(4 2)n (4 -2)n-4n附(递推法)：设an：表示在n位整数中1出现偶数次，2出现偶数次的个数；bn：表示在n位整数中1出现奇数次，2出现偶数次的个数；G：表示在n位整数中1出现偶数次，2出现奇数次的个数；

11、&：表示在n位整数中1出现奇数次，2出现奇数次的个数； TOC o 1-5 h z 则an =bn,+Cn+4an,bn =5 Jan J4。g =dn+an-+4G-dn =bn+G+4dn-由-得an -dn =4(an 1 一dn。=4 (a1 d1 ) =4 (4 0) = 4由-得bn -Cn =4(bn a - Cn _l) =4n (bl -C1) =4n1(1 -1) = 0又令A =an +dn即1,2均出现次数同奇偶的个数Bn =bn +G即1,2均出现次数异奇偶的个数；所以A =2Bn工+4A /可由+得)Bn =2A+4Bn /可由+得)由+得A - Bn =6n由-得

12、 A B =A 工Bn=A B =42=26n 2n所以，A =2n n TOC o 1-5 h z 62 n19 46n 2 4n2n*所以，an J(an dn) (an -dn)= n N224【引申2】用1, 2, 3, 4, 5, 6组成一个n位整数，其中数字 1, 2至少一个出现偶数 次有多少个？解:设A=n位整数中1出现偶数次的个数; B=n位整数中2出现偶数次的个数则Aq=n位整数中1, 2均出现偶数次的个数,由上面的讨论可知，|A|=L(4n 6n) n N*, Bn =L(4n 6n)n N* , | A B|=-224nn nnn n故 |aUb|=|A| |B|-1 A

13、lB尸 4n 6n： =：4_n N44学习必备欢迎下载【例3】设自然数k满足1 k k,使am至少小于a1, a2/H ,ak中k 一1个数，已知满足am =1的数列的个数为1吧.4求k。解答：将a1,a2,|ak重新排列成b Mb?bk ,由m的最小性，设b2=t,则am t, a At(i =k+1, k+2, |m1) 当 t 固定时.由b t,故有C1021种取法，而将k 2b1,b2, bk排列有k!种，于是确定a1,a24M,ak有(t-2)，丁仙!种，而前面分析ai At (i =k+1,k +2|,m1),而在大于t的100t个数中除去dhJILbk还有 100-t-( k-

14、2) V02 -t- k个数。故有A1m出种取法，而am =1是固定的淇余数 an 4111a100排列有(100 -m)!种。102 次综上满足am =1的排列个数T = x (t-2)C1o021102上= (t -2)t =3102上(100-t)!(k -2)!(102 -k -t)!103 _tt &103 _tk! vmk -1103 .tk! ”Am言一(100-m)!m* 1(102 -k -t)! , (100 - m)!(103-t-m)!二工(t -2)k(k -1)(100-t)! 、t 3102上m =ki(103-t -m)!(t -3)!103 _t=、(t -2)!k(k -1)(100-t)! 、, C10t0；t =3102 km i!r1八(t -2)!k(k-1)(100t =3102 ”(100 -k)!= k(k -1)(100-t)!t3(102 -k -t)!102 _k= k(k-1)(100-k)! 、t =3102 k= k!(100 -k)!、 濡上二 k!(100 k)!C =k!(100-k)! t 3-k