小结教学设计范文

组合计数

组合计数是各类髙中数学竞赛的必考内容，题材广泛，方法灵活，是培养学生组合思维能力的基础题材。

1.基础知识

(1)加法原理面向整体分类加法计数，数学表达式为NNi1nni. (2)乘法原理基于局部分步乘法计数，数学表达式为NNi1i. (3)容斥原理计算有限个有限集并集中元素个数的根本方法，数学表达式为A1ii1k1nnk1Ai1Ai2Aik,另有筛法公式Ai+1i1k1nnkAj1kij,其中，有限集Ai1in. (4)映射原理设A,B为两个有限集合，对于映射f:AB有以下结论：

ⅰ若f:AB为单射，则AB; ⅱ若f:AB为满射，则AB; ⅲ若f:AB为双射，则AB; ⅳ若f:AB为“k—倍”满射（集合A中每个元素在集合B中均有k个不同的像）,则kAB. (5)排列数与组合数

mAnmn!n!ⅰ异元情形 Ann1nm1;Cn. m!m!nm!nm!mnkⅱ重元情形 从1,2,,n中可重复的去处k个元素的组合数为Cnk1. ⅲ圆排列数 n个元素1,2,…,n在一个圆周上的不同排列数为(n-1)!. ⅳ控距组合 从集合1,2,,n中取出满足jiji1mi2,3,,k的k个不同元素k1j1j2jkn的取法数为Cnk1m1. (6)不定方程

x1x2xmnmN,nN的一个非负整数解是指满足此方程的一个m元有序数

组x1,x2,,xm,同样可理解为一个正整数解. m1ⅰ非负整数解个数为Cnm1; m1ⅱ正整数解个数为Cn1. (7)形式幂级数 应用形式幂级数求解组合计数是基于“算两次”或“换序求和”，通过幂级数的形式运算翻幂级数axnn0n,从而得出目标数an.最常用的两个幂级数为: xn0n1x1, 1x1xr01r1r!x'x1. 2.基本方法

2.1分类与分步

组合计数经常要施以分步与分类．分步计数面向局部，每一种方法均只能完成一件事的某个环节，各个环节的做法构成有序串联，因此，对分步计数相乘，得到完成一件事的不同方法数；分类计数面向整体，每一类的任何一种方法均能完成一件事，因此，分类所得方法数必须求和．为了保证计数结果正确，分步应要求完整（做一件事的每个环节）而不重叠（各步独立），分类应要求完整（涵盖做一件事的每一类办法）而不重复；分类的另一重要功能是从总控数据中剔除与提取．

例1: 将24个志愿者名额分配给3所学校．则每所学校至少有一个名额且各校名额互不相同的分配方法共有 种. 解: 设甲、乙、丙三校分配名额分别为x,y,z.先不考虑x,y,z两两互异.由x+y+z=24得到2一个总控数据C23.再分离出其中不是两两互异的正整数组(x,y,z)的个数.由2a+b=24,知b=2c.所以a+c=12,共有11个解. 其中，有一个解满足a=b=8对应一个三元数组(8,8,8);另1外,10个解(a,a,b)ab对应10C3个正整数组(x,y,z). 因此，两两互异的正整数组(x,y,z)的个数为C23110C3222. 例2: 设A,B,C,D为空间不共面四点，以1的概率在每对点之间连一条边，任意两点对之间212是否连边是相互独立的.求点A,B可用(一条边或若干条边组成的)空间折线连接的概率.

解: 每对点之间是否连边各有2种可能，共计264种可能．下面计算A,B两点之间有折线相连的种数．(1)有边AB，共计232种．(2)无边AB，但有边CD．此时，点A,B之间有折线相连的条件是点A与C,D之一有折线相连,并且点B与C,D之一有折线相连,把两个局部计数相乘,共计2212219种情形. (3)无边AB,也无边CD,此时CA,CB均连边的情形共有2种,DA,DB均连边的情形有2种,但CA,CB,DA,DB均连边的情形重复计数一次.由容斥原理，知点A,B之间有折线相连的情形共有4+4-1=7种.故点A,B之间有边相连的概率为2265483. 6442.2化归与转化

2.2.1标准化

通过换元消除控距与重复，转化为常态组合数与排列数可以表现的计数模式. 例3: 若从数1,2,…,14中，按由小到大的顺序取出a1,a2,a3,使得a2a13且a3a23,求不同取法的种数. 解: 由已知得a1a23a361a1a22a3410. 换元a1,a22,a34x,y,z,则所求数组a1,a2,a3的个数等于从1,2,,10中取出三3个不同元素的组合数C10120. 2.2.2映射与置换

求解－个置换f:AA(A为有限集)的个数要分析其中“映射圈”个数与长度,建构映射可以实现计数转移求解. 设A1,2,,10,映射f:AA满足f(x)xxA,但f21xxxA.求这种置换的数目. 解: 任取iA,则ififff2fffifji从而对任意的jN均有fjjA,其中f0ii,fjiffj1ijN.由于A10,故只要j10必j1,2,3,,10使得f存在kifki.于是存在最小的ti2,3,,10使得ftii,由i此形成一个含ti个元素的“映射圈”ififti1iftii由题设条件，知i

映射f:AA由一个含有三个元素的映射圈与一个含有七个元素的映射圈构成，每个映射3圈为一个圆排列．故满足题设条件的映射个数为2!6!C10172800. 2.2.3折线方法

例5: 在一天的不同时刻，经理把文件交给秘书打印，每次均将文件放在秘书要打印文件堆的上面，秘书有时间就从最上方取一份文件打印？若有份文件，且经理是按1,2,,n的顺序依次交来的，问：秘书打印完这n份文件的可能顺序有多少种？

【分析】诸如经历“放入”与“拿出”两种相等次数的操作，使得从0状态回归到0状态的计数问题可以尝试化归转化为“折线方法”. 从坐标原点O开始，经理送来一份文件，就画一条斜率为１、长为2的斜线段，秘书打印完一份文件，则接着画一条斜率为－１、长为2的斜线段，这样秘书打印完这n份文件的每一种顺序就对应于用这两种斜线段连接点O和M(2n,0)的折线,如图1.

y

A(1,1)

B(2n-1,1)

o x M

图1

很明显，有向线段OA和BM是固定的，也就是点A(1,1)和B(2n-1,1)均为必经点．于是，这种折线的条数由两种斜线段连接A,B两点的方式决定，共有C2n-2条．这是一个总控数据，其中，穿越x轴的折线(与直线y=-1有公共点,如图2)是不符合题意的,这样折线条数应减去.

y

A(1,1)

B(2n-1,1)

o x M

Ｋ

y=-1

Ａ＇

图2 n-1

对于这样的折线总存在与直线ｙ＝-1最左边的一个公共点K,把此折线上位于点A与K之间的部分关于直线y=-1做对称, 得到一条连接点A’(1,-3)与B(2n-1,1) 之间的线段，其中1斜向上方的线段为n+1条，共计Cn2n-2条折线．因此，符合条件的折线条数为

-1n1Cn2n-2C2n22n2!2n2!2Cn.不同顺序数有2Cn种. n1!n1!n1!n3!n12n1n12n12.3换序求和

例6: 对集合M＝的任一非空子集Ｘ，令x表示X中的最大数与最小数之和.1,2,,100求所有这种x的算术平均数．

【分析】按题意，所求平均数为f2XM1000x-1.则求解的关键是算出分子上的和式NXMx.计算这种“无序和式”，首先要选定一种

“顺序”.为此，可以先考虑每个元素对总和的贡献，再作出累加，常称“贡献法”; 或者考虑把两个子集进行配对，使得它们的

“和数”容易计算. 解法1（贡献法）: 任取iM,则i以两种方式对和式N集iPP1,2,,i1的个数2i1XMx做贡献:i作为最大数贡献的次数为子,i作为最小数贡献的次数为子集21000i.故i对分子的总贡献为i2i121000i,累的个数iPPi1,i2,,1000计对式NXM1000x的

“定序”求和Ni2i1i1（或21000i.应用“等差乘等比型数列”阿贝尔分步求和公式）求和方法得N10012解法2（配对法）: 10001f1001. 任取XM,定义X'1001xxX. 若XX'则minXminX'1001maxXxmaxXminX1001. 若XX'则minX'1001maxX及

maxX'1001minXx'10012xxx'10012. 记210001个非空子集中满足X'X的共有k个.则

xNXM

100021k2002

=1001k2=1001210001

故f21000N11001

2.4递推方法

例7: 将周长为24的圆周等分成24段,从24个分点中选取八个点,使得其中任意两点间所夹的弧长均不等于3和8.求满足这些要求的八点组的不同取法种数. 【分析】先分析数据本质结构:将24个分点按顺时针方向依次标注为1,2,,24.再排成如下38数表: 14710131619229121518212436. 1721232581114在数表中同一列相邻两数所代表的点之间所夹弧长为8，同一行相邻两数所代表的点之间所夹弧长为3(第一列与第八列也是相邻的,第一行与第三行也是相邻的),故在数表中任意相邻两数所代表的两点均不能同时取,即每一列恰取出一个数,并且相邻两列所取的两数不能同行.再作一般化,构建递推关系.从3nn3的数表中每列取出一个数,且相邻两列所取的数不同行(第一列与第n列视为相邻两列),记这种取数的方法数为an.则a36. 当n4时,有anan132n1an2n21. n递推计算得a82821258. 83.深度探究

发掘本质

很多组合计数问题的计数方法极不明显，因此，需要基于问题的条件作深人分析, 才能发现计数本质. 2例8: 给定素数p．设Aaij是一个pp的矩阵,满足aij1i,jp1,2,,p.允许对一个矩阵作如下操作：先选取一行或一列，将该行或该列的每个数同时加上１或同时减去１，若可以通过有限多次上述操作将矩阵A中元素全变为0，则称A为一个“好矩阵”．求好矩阵A的个数. 【分析】若A为好矩阵，则经过有限多次操作，可将矩阵A化为“零阵”不妨设矩阵A化为“零阵”过程中的所有操作为使得第ｉ行各数均减去xi第j列各数均减去yj1i,jp.

则aijxiyj.由矩阵A中各数互异，知x1,x2,,xp互异,y1,y2,,yp也互异(否则,假设x1x2,则导致a11x1y1x2y1a21,矛盾). 再由题意，知任意交换两行或两列，不改变一个矩阵是否为好矩阵，从而，不妨设x1x2xp,且y1y2yp.故假设矩阵A每一行从左到右是递增的，每一列从上到下也是递增的.从而,a111,a122或a212.不妨设a122(否则，将整个数表关于主对角线作对称也不改变A是好矩阵).下面证明:1,2,,p全排在第一行中.假设1,2,,k2kp排在第一行,但k1不排在第一行.于是,a21k1. 将连续的k个整数称为一个“块”，只要证明表中第一行恰有若干个块组成，即前k个数为一个块，后续的k个数又是一个块，等.否则,设前n组k个数均为块,但之后的k个数不为块.由此,yj-1k1,yj1k2,,yjkj1,2,,n均组成块. 从而，数表的前nk列共可分成pn个1k的子数表ai,j-1k1,ai,j1k2,,ai,jki1,2,,p;j1,2,,n,每个子数表中的k个数成块.现假设a1,nk1a,记b为最小的正整数,使得a+b不在第一行中,则bk1.由a2,nk1a1,nk1x2x1a21a11k,则a2,nk1ak.从而,a+b必在前nk列中,这样a+b含在前面所述的某个1k的块中,但a,a+k均不在该块中,矛盾. 故第一行由若干个块组成.从而kp.但1kp,这与p为素数矛盾. 于是，数表中第一行恰为1,2,,p,而第k行必定为k1p1,k1p2,,kp.综上，好矩阵A有本质特征“在交换行, 交换列以及关于主对角线作对称下总可以化成唯一形式”. 所以，好矩阵的个数为22p!. 4.练习题

(1)将两个ａ和两个b共四个字母填在如图3所示的16个格内，每个格内至多填１个字母．若使相同字母既不同行也不同列，求不同的填法种数？

(2) 从1,2,…20中任取五个不同的数, 使得其中至少有两个是相邻的？求这种取法的概率. (3)数列an中共有9项,其中,a1a91,且对每个i1,2,,8,均有ai12,1,1,求ai2

这样数列的个数. (4) 某足球邀请赛有16个城市参加，每市派出甲、乙两支队参加．根据比赛规则，比赛若干天后进行统计，发现除A市甲队外，其他各队已比赛过的场数各不相同．求A市乙队已赛过的场数. (5) —种密码锁的密码设置是在正ｎ边形A1A2An的每个顶点处赋值0和１两个数中的一个,同时在每个顶点染红,蓝两种颜色之一, 使得任意相邻的两个顶点的数字或颜色中至少有一个相同．问:该密码锁共有多少种不同的密码设置?