第二章第二讲 枚举法与容斥原理

第二讲

枚举法与容原理级标分类枚举树形图法枚举法列举法枚举法与容原理

一般标数法容斥原理

*标数法

阶梯标数法础关法枚举法通俗讲就是一一个去数方法，有人说枚举法是计数中的万的方法，真正能够做到不不漏却是难因此举法通常需要我们找到一个好的分标准也是要学会类枚举，下我们来介一些常用枚举计数的方法和技巧。举关键是找到个好的分标准，但类标准并不为一，要具体情况具体析。例如论计数，我们一可以按整特征或余分类，几何计数按图形大小、形状颜色、位、方向等类。）枚举树就是助树状结的分层特来罗列所有可能的方法，适用于层结构鲜明题型。利用枚举树行枚举的般步骤和巧：（1）（2）（3）（4）法

明确条件：析枚举对满足的限条件。确定范围：据限制条所想枚举范围。确定次序：般按照由到多的原，采用合适的分类保证枚举的完整以求不重漏。逐一枚举：助枚举树分层特征按次序逐次画图枚举，最终求出问的解。一般适用于举情况不很多、同情况间的联系较复杂的题目，通过表比较形直观的看到各部之间的关往往可以通归纳找到一类题目的解法因此列法常和归与递推有联系。一、般标数

标数法一般用于求从A点的最短线的条数标数法的核思想是：起点带任一点的最短路线数，都等于从起点发到与这点相邻的点的最路线数之。这种思本质上就是利用加法原理进行分类数。二、梯型标法（一）J阶梯型标数指的是求中从点A走点B的最短路线的条数图中的虚不能走）（二）阶梯型标数征1．走到图中任一点的所路线中单位竖段个数不多于单横线段的数，2．走到虚线边任意一点路线条数好是卡兰数。斥理某些需要统的数量之有包含排关系的，可以采用容斥原理进行分。（1）

容斥原理1两量重叠题1先包含——

重叠部分A∩B计算了两次，多加了一2再排除——

AB用符号可表为：

ABAA读作：A并，表A情况的总。AB作：A，表的公共部。（2）

容斥原理2三量重叠问题图示如下：AB

BC图中小圆表A的元素的数，中圆表示B的元素的个数大圆表示C的素的个数。CA1.先包含—

BABC

重叠部分B、C、重叠了两次，C叠3次。2.3.

再除——ABACC，再含——A

用号示：ACBCABBACAA作：交B，表C者的公共部分题讲分类枚举例1.用台天平和重克、3克9克的砝码一个（不用其他物当砝码），当砝码只能放在同一个内时，可称出的重有多少种？解析：共有个重量不的砝码，以取出其中的一个，两个，三个来量。一一来举这三种况。取一个砝码称：1克3克、9克有3种。取两个砝码称1+3=4克）1+9=10（克3+9=12（克3种。取三个砝码称：1+3+9=13克），1种。注意到1、、9、4、101213各不相同所以可以出：3+3+1=7（种）例2.用1、2、3这三数一共可以成多少个同的三位？分别为几个？解析：根据位上的数不同，我可以将它们分成三类第一类：百上数字为1有123、132第二类；百上数字为2有213、231第三类：百上数字为3有312、321可以组成123、132、213231312、321共6个不同数列表法例3.课小组组织30人做游，按1～30号排队报。第一报数后，单号全部站出来，然后每次余下人中第一开始站出隔一人站出一个人到第次这些人全站出来？后站出的人应是第几号解析：根据目的特点先用排列把题中的条件问题列出来，再用枚法完成题要求。排好队的人次是，2，3，5，．．．．．28，29，30次第一次第二次第三次第四次第五次

出号1，3，5，7，9，11，13，15，17，21，，2527，292，6，10，14，18，22，，304，12，，288，2416

从上面的列中我们毫遗漏的排，得出到第五次这些人全部站出来最后在个是16号。树形图例4.如所示，数字1处一颗棋，现移动这颗棋子到数字5处。规每次只能移动到邻近一格，且总向右移动例如1→2→4→5就是一路线。问多少种不的移动路线？解析：从1移到，从结想，要移到5只有从4、向右移动一格到邻一格，即5←45←3；要到，只有3、2向右移动一到邻近的4，即：←34←2；．．．．．．用树形图

2

4填写如下

1

3

5123145

2

13

2

11数一数，图1的数就是移动的路线数。共有5条不同路线。两量重叠问例1.一班有45个小学生统计借外书的情况是:全班学都借有语文数学课外.借语课外书的有39人,借数课外书的有人.语、数学两课外书都的有多少人？解析：解决斥原理的题，在小阶段我们主要采用图示法示出各部分之间关系再进行求解。画图时通将所有对看作全体，然后根据题意分解，如题则将全45名学生看作全体从图中可以出，两种的人数相时重叠部分被多加了一次，此两种都的人数=32+39-45=26人）

数学课外书32人

语文课外书39人两种都借的

例2.有长8厘米,宽6厘米的方形与边长为5厘米的方形,如图,放在桌面阴影图形的重叠部分),么这两图形盖住桌的面积是少平方厘？解析：重叠分相加时计算了两，因此能覆盖的面积为

86×8＋5×5－3×4÷2=67（平厘米）

6345三量重叠问例3.某共有30名男生其中20人参加足球,人加篮球队10人参加球队.已，没一个人同时加3个队,且每人至少加一个队有6人既加足球队参加篮球队有2人既参加篮队又参加球队,那么既加足球队参加排球的有多少人解析：根据意画出示图，从图可知，只参加篮球队的人数为12-6-2=4，既参足球队又加排球队的人数为20+10+4-30=4（人。（只有？”部分被加了两次）

篮球队人

排球队人人？人人

足球队人故既参加排队又参加球队的人为4人.例4.某有学生960人其中510人订阅“文报,有330人订阅“数学报,有120人订科学爱者,校学生有270人订阅两种刊有58人三种报都订么这学校没有订阅任报刊的有少人？解析：从图中可以看订了报刊人数为

一共

科学好者

都没的？人330+510+120-270-58=632(人)（相加过程订两种的加了2次，订三种被加了，减270的时候种的减一次，还要再减一次。

数学

作文所以没有订任何报纸人数为960－632=328（人）例5.在然数1~100中，能23或5除的数有少个？解析：能被2整除有50个；能被3整除的有33个能被5除的有。但，有的数既能被2除也能3或5整除就是我们计算过程会有重复算的数字要剔除其实题和例4似。能同时被23整除数有16个；

倍数

都不、5倍数数能同时被25整除数有10个；

能同时被35整除数有6；能同时被23、5整除数有3。

倍数

倍数然后画出图，不难得结论。解：50＋3320－10＋＋6）－3=68（个

故在自然数1~100中，能2、或整除数有68个。真题解读【10年白塔中】用2克，克6克的码在天平上可以称出_____种不同的重量。解析：共有个重量不的砝码，以取出其中的一个，两个，三个来量。一一列举这三情况。取一个砝码称：2克3克、6克有3种。取两个砝码称：2+3=5（克）2+6=8克）3+6=9克），。取三个砝码称：2+3+6=11克），1种。注意到23、6、5、8、9、11各不相同，以可以称：3+3+1=7（种）刀试1.商店售饼干，存10箱5公斤重，箱2公斤的，箱一斤重的。顾客要买九公斤重的饼干，了便于携又不开箱售货员有多少种发货办法？2.小云了1张5、张2元的币和8枚1的硬币，在他要买本8元的说，问他有多少种付方式？3.用0、1、2这三个，分别能成多少个不同的三位数？其中最小三位数和大的三位分别是多少4.一个子中装有枚硬币，枚1分，两枚分两枚1，一枚5角，每次出两枚，下它们的和然后放回中，如此复取出和放回，那么记下的和最多多少种不的钱数？5.在1~100的然数中,是5的数或是7的数的数有.6.某区100个语教懂英语或俄,其中英语的75人既懂英语懂俄语的20人那么懂语的教师为.7.六一有学生46人其中会自行车的17人,会游泳的14人既会骑又会游泳的4人,两样都不会的人8.在1至10000中不能被57整的数共有个.

9.如图示,AB分代表面积8、11的张不同状的纸片,它们重叠放在