第 6 讲 计数和组合专题 一、 计数问题1、枚举法枚举法就是把所有也许得状况一一列举出来，然后数一下总共有多种状况．2、加乘原理（1）加法原理——分类假如完毕一件事有几类措施，在每一类措施中又有不一样样措施，那么把每类措施数相加就得到所有措施数．（2）乘法原理——分步假如完毕一件事有多种环节，在每一种环节中又有不一样样措施，那么把每步措施数相乘就得到所有措施数．3、排列组合（1）排列从 m 个不一样样元素中取出 n 个（），并根据一定次序排成一列，其措施数叫做从 m 个不一样样元素中取出 n 个排列数，记作.其计算措施为：即从 m 开始递减地连乘 n 个数(2)组合从 m 个不一样样元素中取出 n 个（）构成一组（不计次序），其措施数叫做从 m 个不一样样元素中取出 n 个不一样样组合数，记作.其计算措施为：4、分类法和排除法（1）分类法：分来法处理问题基础思想是通过度类拆解把一种复杂问题转化成多种相对简朴小问题来处理．（2）排除法：当题目中满足规定状况较多，分类法不好处理时，可以尝试用排除法，把不符合规定状况去掉，剩余就是符合．5、容斥原理（1）理解简朴容斥原理（两个之间重叠）和复杂容斥原理（三个之间重叠）（2）用文氏图协助解题6、递推措施（1）上楼梯模型（2）传球法——列表写出每一步中详细措施数（3）几何图形分平面——增量分析7、插板法用于求解“把 m 个相似球放到 n 个不一样样盒子中”此类问题（1）注意：球必需是相似，盒子必需是不一样样．（2）假如规定每个盒子至少一种球，那么措施数为（把 n-1 个板插到 m-1 个空隙中）（3）假如规定每个盒子可以为空，那么措施数为（先借 n 个球，然后根据每个盒子至少 1 个去放，最终从每个盒子中拿出 1 个还回去）（4）方程正整数解共组（把 n 个球放到 3 个盒子中，每个盒子至少 1 个）（5）方程自然数解共组（把 n 个球放到 3 个盒子中，每个盒子可以为空）8、和旋转、翻转有关计数此类问题要想清晰与否有反复，反复了多少．一般求解时，要先固定部分对象，使其不能旋转或翻转．二、 统筹计划1、安排工序问题2、最短路线或最短时间问题3、排队等待问题4、集合问题5、货品调度问题三、 游戏对策（1）必胜方略往往是考虑“怎样让对方输”，即必胜方行动时怎样进行一次合适操作，把必输状态留给对方．（2）游戏对策中往往会运用对称性来处理问题，如桌子上放硬币问题（轮番在圆桌上放硬币，到谁放时...
