《排列组合专题》PPT课件.ppt

加法原理和乘法原理 加法原理和乘法原理是排列组合的基础和核心 既可用来推导排列数 组合数公式 也可用来直接解题 它们的共同点都是把一个事件分成若干个分事件来进行计算 利用加法原理 重在分 类 类与类之间具有独立性和并列性 利用乘法原理 重在分步 步与步之间具有相依性和连续性 比较复杂的问题 常先分类再分步 1 加法原理 如果完成一项工作有两类相互独立的方式A和B 在方式A中有m种完成任务的途径 在方式B中有n种完成任务的途径 则完成这项工作的总的途径有m n种 2 乘法原理 如果完成一项工作有两个连续的步骤A和B 在步骤A中有m种不同的方式 在步骤B中有n种不同的方式 则完成这项工作的总的方法有m n种 例1 从1到4这4个数码中不重复地任取3个构成一个三位数 求这样的三位数一共有多少个 分析 构成三位数的过程可以看成是由连续的三步完成 第一步 取百位上的数字 共有4种方法第二步 取十位上的数字 共有3种方法 即不能取百位上已经取走的数码 第三步 取个位上的数字 共有2种方法 即不能取百位和十位上已经取走的数码 因此由乘法原理 这样的三位数一共有 4 3 2 24种 例2 一个三位数 如果它的每一位数字都不小于另一个三位数对应数位上的数字 就称它 吃掉 后一个三位数 例如543吃掉432 543吃掉543 但是543不能吃掉534 那么能吃掉587的三位数共有多少个 百位上有5 6 7 8 9五种选择 十位上有8 9两种选择 个位上有7 8 9三种选择 所以共有5 2 3 30 个 三位数 例3 如图 一方形花坛分成编号为 四块 现有红 黄 蓝 紫四种颜色的花供选种 要求每块只种一种颜色的花 且相邻的两块种不同颜色的花 如果编号为 的已经种上红色花 那么其余三块不同的种法有种 21 编号为 的有三种选择 对于编号为 的 可以分成以下二类 1 若编号为 的与编号为 的同色 则编号为 的有三种选择 这种情况下共有3 3种方案 2 若编号为 的与编号为 的不同色 则编号为 的有二种选择 编号为 的有二种选择 这种情况下共有3 2 2种方案 例4 用红 黄 绿 蓝 黑五种颜色涂在如下图所示的ABCDE五区域 颜色可重复使用 但同色不相邻 涂法有几种 AC同色 5 4 4 1 4AC不同色 5 4 4 3 3 1040 例5 在一块并排的10垄田地中 选择二垄分别种植A B两种作物 每种种植一垄 为有利于作物生长 要求A B两种作物的间隔不少于6垄 不同的选法共有 种 分析 采取分类的方法 第一类 A在第一垄 B有3种选择 第二类 A在第二垄 B有2种选择 第三类 A在第三垄 B有一种选择 同理A B位置互换 共12种 例6 某小组有10人 每人至少会英语和日语的一门 其中8人会英语 5人会日语 从中选出会英语与会日语的各1人 有多少种不同的选法 由于8 5 13 10 所以10人中必有3人既会英语又会日语 5 2 3 所以可分三类 5 2 5 3 2 3 31 例7 在所有的三位数中 有且只有两个数字相同的三位数共有多少个 1 2 3 1 2 3 类中每类都是9 9种 共有9 9 9 9 9 9 3 9 9 243个只有两个数字相同的三位数 例8 求正整数1400的正因数的个数 因为任何一个正整数的任何一个正因数 除1外 都是这个数的一些质因数的积 因此 我们先把1400分解成质因数的连乘积1400 23527 所以这个数的任何一个正因数都是由2 5 7中的若干个相乘而得到 有的可重复 于是取1400的一个正因数 这件事情是分如下三个步骤完成的 1 取23的正因数是20 21 22 23 共3 1种 2 取52的正因数是50 51 52 共2 1种 3 取7的正因数是70 71 共1 1种 所以1400的正因数个数为 3 1 2 1 1 1 24 例9 从1到300的自然数中 完全不含有数字3的有多少个 将0到299的整数都看成三位数 其中数字3不出现的 百位数字可以是0 1或2三种情况 十位数字与个位数字均有九种 因此除去0共有3 9 9 1 242 个 例10 在小于10000的自然数中 含有数字1的数有多少个 不妨将0至9999的自然数均看作四位数 凡位数不到四位的自然数在前面补0 使之成为四位数 先求不含数字1的这样的四位数共有几个 即有0 2 3 4 5 6 7 8 9这九个数字所组成的四位数的个数 由于每一位都可有9种写法 所以 根据乘法原理 由这九个数字组成的四位数个数为9 9 9 9 6561 于是 小于10000且含有数字1的自然数共有9999 6561 3438个 排列的定义 数学上 把若干元素 按照任何一种顺序排成一列 叫做排列 如果两个排列满足下列条件之一 它们就被认为是不同的排列 1 所含元素不全相同2 所含元素相同 但顺序不同 相异元素不重复的排列 从n个不同的元素中 取出r个不重复的元素 按次序排成一列 当r n时 称为从n个中取r个的一种选排列 如 从a b c这三个字母中 每次取出2个 有多少种排列方法 第一步 确定左边的字母 在三个字母中任取一个 有 种方法 第二步 确定右边的字母 从剩下的 个字母中选取一个 有 种方法 根据乘法原理 共有 种不同的排法 abacbabccacb 一般地 从n个不同的元素中取出r个元素的选排列数用表示 则 n n r 例 全国足球甲级 组 联赛共有 队参加 每队都要与其它各队在主 客场分别比赛一次 共进行多少场比赛 任何二个队进行一次主场比赛和一场客场比赛 相当于从14个元素中任取2个元素的一个排列 共需进行的比赛场次是 14 12 14 13 182 当n r时 叫做n个不同元素的全排列 n个不同元素的全排列数Pnn n 例 个人站成一排照相 共有多少种不同的排列方法 例3 求有多少个没有重复数字且能被5整除的四位奇数 要能被5整除又是奇数 所以个位上数字只能是5 有1种选法 由于5已用过 又不可能是0 所以千位上数有P18种选法 已用过2个数 所以百位 十位上的数有P28种选法 所以符合题意的个数为 1 P18 P28 448 例4 用0 1 2 3 4 5六个数字 可以组成多少个没有重复数字的三位偶数 1 个位为0 十位为1 2 3 4 5中的一个 百位为剩下的四个数字中的一个 所以这样的偶数共有1 P15 P14 2 个位为2 百位为1 3 4 5中的一个 十位为剩下的四个数字中的一个 所以这样的偶数共有1 P14 P14 3 个位为4 百位为1 2 3 5中的一个 十位为剩下的四个数字中的一个 所以这样的偶数共有1 P14 P14 所以符合题意的个数为20 16 16 52 例5 8位同学排成相等的两行 要求某两位同学必须排在前排 有多少种排法 这两个同学排在前排4个位置的排列数是P24 其它同学在余下的6个位置排的排列数是6 所以符合题意的个数为P24 6 12 720 8640 例6 某车站有编号为1到6的6个入口处 每个入口处每次只能进一人 问一个小组4人进站的方案有几种 第一个人有6种方案 第二个人有7种方案 因为他选择和第一个人相同入口处时 还有前后之分 9 8 7 6 3024 相异元素的可重复排列 从n个不同元素中取出r个元素的可重复的排列种数为nr 93 729 例7 由数字1 2 3 9共能组成多少个三位数 相异元素的循环排列 n个不同元素不分首尾排成一个圆圈 称为循环排列 其排列数为n n n 1 如1 2 3三个数的循环排列只有 二种 例8 在圆形花坛外侧摆放 盆菊花和 盆兰花 要求兰花不能相邻摆放 一共有多少种摆法 盆菊花摆成一周的排列方法有n1 盆兰花插入 个空中的排列总数有n2 P 8 4 摆放总数为n n1 n2 8467200 例9 有男女各五个人 其中有 对是夫妻 沿圆桌就座 若每对夫妻都坐在相邻的位置 问有多少种坐法 设 对夫妻分别为 和a 和b 和c 先让 三人和另外 个人沿圆桌就座的方法为 种 又对上述每种坐法 a坐在 的邻座的方式有左右两种 b c也如此 所以共有 种 不全相异元素的排列 如果在n个元素中 有n1个元素彼此相同 有n2个元素彼此相同 又有nm个元素彼此相同 若n1 n2 nm n 则这n个元素的全排列叫做不全相异元素的全排列 其排列数为 n n1 n2 nm 若n1 n2 nm r n 则这n个元素的全排列叫做不全相异元素的选排列 其排列数为 prn n1 n2 nm 例10 将N个红球和M个黄球排成一行 如 N 2 M 3可得到10种排法 问题 当N 4 M 3时有种不同排法 7 4 3 35 NOIP2002 例11 把两个红球 一个蓝球和一个白球放到十个编号不同的盒子中去 有多少种方法 排列数为p410 2 1 1 2520 生成排列的算法 下面程序的功能是利用递归方法生成从1到n n 10 的n个数的全部可能的排列 不一定按升序输出 例如 输入3 则应该输出 每行输出5个排列 123132213231321312 求全排列 06年初赛题 vari n k integer a array 1 10 ofinteger count longint procedureperm k integer varj p t integer beginif thenbegin forp 1tokdowrite a p 1 write if thenwriteln exit end forj ktondobegint a k a k a j a j t perm k 1 t a k endend beginwriteln Entryn read n count 0 fori 1tondoa i i end perm 1 K n inc count countmod5 0 a k a j a j t 123132213231321312 算法过程 用数组 a array 1 r ofinteger 表示排列 初始化时 a i i i 1 2 r 设中间的某一个排列为a 1 a 2 a r 则求出下一个排列的算法为 从后面向前找 直到找到一个顺序为止 设下标为j 1 则a j 1 a j 从a j a r 中 找出一个比a j 1 大的最小元素a k 将a j 1 与a k 交换 将a j a j 1 a r 由小到大排序 问题描述 用生成法求出1 2 r的全排列 r 8 1999年提高组 constr 7 varn i s k j i1 t intger a array 1 r ofinteger procedureprint1 varik integer beginforik 1tordowrite a ik 8 writeln endbeginfori 1tordo print1 输出第一个排列 s 1 fori 2tordos s i 总排列数为r s s 1 还需生成s 1个排列 fori dobeginj r while doj j 1 k j fori1 j 1tordoif thenk i1 t a j 1 a j 1 a k a k t fori1 jtor 1dofork i1 1tordoif thenbegint a i1 a i1 a k a k t end print1 end end a i i 1tos a j 1 a j a i1 a j 1 and a i1 a k a i1 a k 132541345213425 问题描述 人类终于登上了火星的土地并且见到了神秘的火星人 人类和火星人都无法理解对方的语言 但是我们的科学家发明了一种用数字交流的方法 这种交流方法是这样的 首先 火星人把一个非常大的数字告诉人类科学家 科学家破解这个数字的含义后 再把一个很小的数字加到这个大数上面 把结果告诉火星人 作为人类的回答 火星人用一种非常简单的方式来表示数字 掰手指 火星人只有一只手 但这只手上有成千上万的手指 这些手指排成一列 分别编号为1 2 3 火星人的任意两根手指都能随意交换位置 他们就是通过这方法计数的 一个火星人用一个人类的手演示了如何用手指计数 如果把五根手指 拇指 食指 中指 无名指和小指分别编号为1 2 3 4和5 当它们按正常顺序排列时 形成了5位数12345 当你交换无名指和小指的位置时 会形成5位数12354 当你把五个手指的顺序完全颠倒时 会形成54321 在所有能够形成的120个5位数中 12345最小 它表示1 12354第二小 它表示2 54321最大 它表示120 下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字 火星人 04年普及组 现在你有幸成为了第一个和火星人交流的地球人 一个火星人会让你看他的手指 科学家会告诉你要加上去的很小的数 你的任务是 把火星人用手指表示的数与科学家告诉你的数相加 并根据相加的结果改变火星人手指的排列顺序 输入数据保证这个结果不会超出火星人手指能表示的范围 输入文件 输入文件martian in包括三行 第一行有一个正整数N 表示火星人手指的数目 1 N 10000 第二行是一个正整数M 表示要加上去的小整数 1 M 100 下一行是1到N这N个整数的一个排列 用空格隔开 表示火星人手指的排列顺序 输出文件 输出文件martian out只有一行 这一行含有N个整数 表示改变后的火星人手指的排列顺序 每两个相邻的数中间用一个空格分开 不能有多余的空格 样例输入 5312345 样例输出 12453 数据规模 对于30 的数据 N 15 对于60 的数据 N 50 对于全部的数据 N 10000 varn m i ss j k temp integer min longint a array 1 10000 ofinteger beginreadln n readln m fori 1tondoread a i whilem 0do 一次循环产生下一个排列 beginj n while j 1 and a j a j 1 min a j k j fori jtondoif a i a j 1 and a i min thenbegink i min a i end 从a j 到a n 找出一个比a j 1 大的最小值 temp a j 1 a j 1 a k a k temp 交换 fori jton 1dobeginss i fork i 1tondoifa ss a k thenss k ifssithenbegintemp a i a i a ss a ss temp end end 在j到n中 从小到大排列 m m 1 end fori 1tondowrite a i end 531234512354124531243512453 组合的定义 数学上 把若干元素 不论次序并成一组 叫做组合 如果两个组合中 至少有一个元素不同 它们就被认为是不同的组合 abc abd 相异元素不重复的组合 设从n个不同的元素中 取出m个不同元素 不考虑顺序并成一组 叫作从n个不同的元素中 取出m个不同元素的一个组合 如 写出从a b c d四个元素中 任取三个元素的所有组合 abc abd acd bcd 从n个不同的元素中 取出m个不同元素的组合数记为Cmn 则有Cmn Pmn m n m n m 规定C0n 1 abc bac cab acb bca cba 例1 八年级6个班进行排球比赛 每班的排球队要与其他5个班分别比赛一场 求共要进行多少场比赛 C26 P26 2 6 5 2 1 15 例2 平面上有n个点且无三点或三点以上共线 任意两点可以连成一条直线 一共能连成多少条直线 C2n n n 1 2 例3 某班第一组有10名同学 第二组有8名同学 现要求每组选出2名学生代表参加座谈会 有多少种选法 C210 C28 1260 例4 一元 二元 五元 十元人民币各一张 一共可以组成多少种不同的币值 C14 C24 C34 C44 4 6 4 1 15 例5 5年级有8个班 六年级有6个班 先分别举行各年级的篮球赛 采用单循环制 然后由两个年级的第一名争夺冠军 共需要比赛多少场 C28 C26 1 8 7 2 6 5 2 1 28 15 1 44 例6 某班第一组有10名同学 其中有4名女同学 现要求选出3名学生代表 其中至少有一名女同学去参加座谈会 有多少种选法 代表中有1名女同学的选法为C14 C26种 代表中有2名女同学的选法为C24 C16种 代表中有3名女同学的选法为C34种 C14 C26 C24 C16 C34 100 例7 欲登上第10级楼梯 如果规定每步只能跨上一级或两级 则不同的走法共有 例8 A的一边AB上有4个点 另一边AC上有5个点 连同 A的顶点共10个点 以这些点为顶点 可以构成 个三角形 90 例9 平面上有三条平行直线 每条直线上分别有7 5 6个点 且不同直线上三个点都不在同一条直线上 问用这些点为顶点 能组成多少个不同三角形 2001年p C 7 2 5 6 C 5 2 7 6 C 6 2 7 5 7 6 5 21 11 10 13 15 12 210 231 130 180 210 751 例10 平面上有三条平行直线 每条直线上分别有7 5 6个点 且不同直线上三个点都不在同一条直线上 问用这些点为顶点 能组成多少个不同四边形 2001年t C 7 2 C 5 2 C 7 2 C 6 2 C 5 2 C 6 2 C 7 2 5 6 C 5 2 7 6 C 6 2 5 7 21 10 21 15 10 15 21 5 6 10 7 6 15 5 7 2250 例11 10名划船运动员中 3人只会划左舷 2人只会划右舷 5人左右舷都会划 从中选6人 平均分在左 右舷 共有多少种不同的选法 675 例12 小陈现有2个任务A B要完成 每个任务分别有若干步骤如下 A a1 a2 a3 B b1 b2 b3 b4 b5 在任何时候 小陈只能专心做某个任务的一个步骤 但是如果愿意 他可以在做完手中任务的当前步骤后 切换至另一个任务 从上次此任务第一个未做的步骤继续 每个任务的步骤顺序不能打乱 例如 a2 b2 a3 b3 是合法的 而 a2 b3 a3 b2 是不合法的 小陈从B任务的b1步骤开始做 当恰做完某个任务的某个步骤后 就停工回家吃饭了 当他回来时 只记得自己已经完成了整个任务A 其他的都忘了 试计算小陈饭前已做的可能的任务步骤序列共有种 2009年p 70 排列组合 加法原理 B任务中的b1一定做 而且肯定是第一个做的 除了b1外 第一类 完成A任务只有1种 第二类 完成A任务和b2有C 4 1 4种 第三类 完成A任务和b2 b3有C 5 2 10种 第四类 完成A任务和b2 b3 b4有C 6 3 20种 第五类 完成A任务和b2 b3 b4 b5有C 7 4 35种 加起来1 4 10 20 35 70 例13 袋中有已编号的20个球 其中1 10号是红球 11 20号是白球 每取得一个红球得2分 取得一个白球得3分 若取得若干个球 共得20分 有多少种不同取法 2x 3y 20 y必是偶数 所以y 0 2 4 6 相应地x 10 7 4 1 C010 C1010 C210 C710 C410 C410 C610 C110 51601 例14 从1 300之间任取3个不同的数 使得这3个数的和恰好被3除尽 有多少种方法 被3除所得的余数不外乎 0 1 2 所以可把1 300之间的数分成三组 A 1 4 7 298 B 2 5 8 299 C 3 6 9 300 三个数同属于集合A 有C3100种 三个数同属于集合B 有C3100种 三个数同属于集合C 有C3100种 三个数分属于集合A B C 有1003种 加起来等于1485100种 例15 若将一个正整数化为二进制数 在此二进制数中 我们将数字0的个数多于数字1的个数的这类二进制数称为A类数 例如 24 10 11000 2其中1的个数为2 0的个数为3 则称此数为A类数 请你求出1 112之中 包括1与112 全部A类数的个数 112 10 1110000 2可根据二进制数的前缀来分类 111 这类数中A类数只有一个 即1110000 0 位数不确定 需对位数进行讨论 1位数 即1 不是A类数 2位数 即1 10和11都不是A类数 3位数 即1 只有100一个 4位数 即1 只有1000一个 5位数 即1 A类数个数有C44 C34 5 6位数 即1 A类数个数有C55 C45 6 1 5 16 1 1 5 6 35 例16 某城市有4条东西街道和6条南北的街道 街道之间的间距相同 若规定只能向东或向北两个方向沿图中路线前进 则从M到N有多少种不同的走法 2007年p M N 一 从M到N必须向上走三步 向右走五步 共走八步 二 每一步是向上还是向右 决定了不同的走法 三 事实上 当把向上的步骤决定后 剩下的步骤只能向右 从而 任务可叙述为 从八个步骤中选出哪三步是向上走 就可以确定走法数 本题答案为56 相异元素的可重复组合 设从n个不同的元素中 取出m个不同元素 若允许这个元素可以重复使用 也允许m n 则把这样的组合称为重复组合 其组合数记为Hmn Hmn Cmn m 1如1 2 3 4 四个数字中取三个 允许重复的组合有以下20种 111 122 134 224 333112 123 144 233 334113 124 222 234 344114 133 223 244 444 组合的生成算法 从1 2 3 n共n个数中任取m个数 请输出所有组合并计算组合数 varn m i k s integer a b array 0 100 ofinteger beginreadln n m fori 1tomdobegina i i b i end k m s 0 repeatifthenbegins s 1 fori 1tomdowrite a i write end ifa k b k thenbegin ifk mthenfork k 1tomdo endelse untilk 0 writeln writeln s s end n m i k m a k a k 1 a k a k 1 1 k k 1 Jam的计数法 问题描述 Jam是个喜欢标新立异的科学怪人 他不使用阿拉伯数字计数 而是使用小写英文字母计数 他觉得这样做 会使世界更加丰富多彩 在他的计数法中 每个数字的位数都是相同的 使用相同个数的字母 英文字母按原先的顺序 排在前面的字母小于排在它后面的字母 我们把这样的 数字 称为Jam数字 在Jam数字中 每个字母互不相同 而且从左到右是严格递增的 每次 Jam还指定使用字母的范围 例如 从2到10 表示只能使用 b c d e f g h i j 这些字母 如果再规定位数为5 那么 紧接在Jam数字 bdfij 之后的数字应该是 bdghi 如果我们用U V依次表示Jam数字 bdfij 与 bdghi 则U V 且不存在Jam数字P 使U P V 你的任务是 对于从文件读入的一个Jam数字 按顺序输出紧接在后面的5个Jam数字 如果后面没有那么多Jam数字 那么有几个就输出几个 输入文件 输入文件counting in有2行 第1行为3个正整数 用一个空格隔开 stw 其中s为所使用的最小的字母的序号 t为所使用的最大的字母的序号 w为数字的位数 这3个数满足 1 s t 26 2 w t s 第2行为具有w个小写字母的字符串 为一个符合要求的Jam数字 输出文件 输出文件counting out最多为5行 为紧接在输入的Jam数字后面的5个Jam数字 如果后面没有那么多Jam数字 那么有几个就输出几个 每行只输出一个Jam数字 是由w个小写字母组成的字符串 不要有多余的空格 输入样例 2105bdfij 输出样例 bdghibdghjbdgijbdhijbefgh vari j s t w n longint st string a array 0 30 ofinteger beginreadln s t w readln st 输入起始字符串 fori 1towdoa i ord st i ord a s 2 将字符串转变为数字串 a 0 0 n 0 控制开关变0和生成个数清0 while a 0 0 and n0 doi i 1 inc a i forj i 1towdoa j a j 1 1 产生下一个组合 ifa 0 0thenbeginhalt endelsebeginfori 1towdowrite chr ord a a i s 2 writeln n n 1 个数加1 end end end 2105bdfij先转换 98 97 2 2 113589 初始组合 i 5时 t s w i 1 10 2 5 5 1 9a 5 最大可取9产生下一个组合 13678输出 i 1时 chr 97 1 2 2 bbdghi 排列组合题型总结 排列组合问题千变万化 解法灵活 条件隐晦 思维抽象 难以找到解题的突破口 因而在求解排列组合应用题时 除做到 排列组合分清 加乘原理辩明 避免重复遗漏外 还应注意积累排列组合问题得以快速准确求解 直接法 1 特殊元素法 用1 2 3 4 5 6这6个数字组成无重复的四位数 试求满足下列条件的四位数各有多少个 1 数字1不排在个位和千位 2 数字1不在个位 数字6不在千位 分析 1 个位和千位有5个数字可供选择 其余2位有四个可供选择 由乘法原理 240 特殊元素 优先处理 特殊位置 优先考虑 2 特殊位置法 2 当1在千位时余下三位有 60 1不在千位时 千位有种选法 个位有种 余下的有 共有 192 所以总共有192 60 252 间接法 当直接法求解类别比较大时 应采用间接法 如上例中 2 可用间接法 有五张卡片 它的正反面分别写0与1 2与3 4与5 6与7 8与9 将它们任意三张并排放在一起组成三位数 共可组成多少个不同的三位数 8位同学排成一行 要求某两位同学互不相邻 有多少种排法 8位同学排成一行的总数是8 把排在一起的的两个同学看成一个人的排列总数是7 因为排在一起的两个同学的位置可以互换 所以两位同学排在一起的排列数是2 7 所以符合题意的个数为8 2 7 30240 正方体8个顶点中取出4个 可组成多少个四面体 所求问题的方法数 任意选四点的组合数 共面四点的方法数 12 70 12 58个 插空法 在一个含有8个节目的节目单中 临时插入两个歌唱节目 且保持原节目顺序 有多少种插入方法 原有的8个节目中含有9个空档 插入一个节目后 空档变为10个 故有 90中插入方法 8位同学排成一行 其中有4位女同学 要求女同学不相邻 有多少种排法 四位男同学排成一行的总数是4 在他们首尾两个位置和他们两两之间的位置 共5个 分别插入一个女同学的排列数是A45 120 所以符合题意的个数是4 120 2880 马路上有编号为l 2 3 10十个路灯 为节约用电又看清路面 可以把其中的三只灯关掉 但不能同时关掉相邻的两只或三只 在两端的灯也不能关掉的情况下 求满足条件的关灯方法共有多少种 关掉的灯不能相邻 也不能在两端 又因为灯与灯之间没有区别 因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯 共 20种方法 捆绑法 当需排元素中有必须相邻的元素时 宜用捆绑法 4名男生和3名女生共坐一排 男生必须排在一起的坐法有多少种 分析 先将男生捆绑在一起看成一个大元素与女生全排列有种排法 而男生之间又有种排法 由乘法原理满足条件的排法有 576 四个不同的小球全部放入三个不同的盒子中 若使每个盒子不空 则不同的放法有种 一定有两个球放在同一个盒子中 某市植物园要在30天内接待20所学校的学生参观 但每天只能安排一所学校 其中有一所学校人数较多 要安排连续参观2天 其余只参观一天 则植物园30天内不同的安排方法有 注意连续参观2天 即需把30天中的连续两天捆绑看成一天作为一个整体来选有 其余的就是19所学校选28天进行排列 书架上有四本不同的书A B C D 其中A和B是红皮的 C和D是黑皮的 把这四本书摆在书架上 满足所有黑皮的书都排在一起的摆法有 种 满足A必须比C靠左 所有红皮的书要摆放在一起 所有黑皮的书要摆放在一起 共有 种摆法 2008年p 闸板法 名额分配或相同物品的分配问题 适宜采用闸板法 某校准备组建一个由12人组成的篮球队 这12个人由8个班的学生组成 每班至少一人 名额分配方案共种 分析 此例的实质是12个名额分配给8个班 每班至少一个名额 可在12个名额中的11个空当中插入7块闸板 一种插法对应一种名额的分配方式 故有种 若m n N m n 把n写成m个自然数之和 如 m 3 n 5时 5 1 1 3 1 3 1 3 1 1 2 2 1 2 1 2 1 2 2 问共有多少种表示法 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 对n 1 1 1 1有几种加括号的方法 也就是在n 1个加号中 保留m 1个加号 将其余的各部分元素分别加起来 Cm 1n 1 平均分堆 6本不同的书平均分成三堆 有多少种不同的方法 分析 分出三堆书 a1 a2 a3 a4 a5 a6 由顺序不同可以有 6种 而这6种分法只算一种分堆方式 故6本