组合数学_第05讲(0314).pptVIP

组合数学 王新红 上讲 回顾 上讲 回顾 本讲内容 多重集的组合 不相邻的组合 给出F(n,r)的至少3种组合意义解释。 用球放入盒子模型解释学过的排列数与组合数 本讲内容 多重集的组合 不相邻的组合 这两次课我们介绍了多重集的排列和多重集的组合以及不相邻的组合。并学习了模型转换的思想。 多重集的r-排列和r-组合是在无重集合的排列和组合知识上的推广，也可以称为广义的排列组合。 下次上课内容： 1）二项式定理 2）组合恒等式及其组合意义的解释 1、6个没有区别的车放在6×6棋盘上，使没有两个车能够互相攻击的放置方法有多少？如果是2个红车4个蓝车，那么放置方法又是多少？ 2、 确定多重集S={3·a, 4·b, 5·c}的11-排列的个数 3、在三个孩子之间分发12个完全相同的苹果和1个橘子，使每个孩子至少得到一个水果，有多少种分发方法？ 4、在下面的伪代码执行后k的值是什么？ 5、8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？ 6、（a）在2n个球中，有 n个相同，求从这2n个球中选取n个的方案数。 （b）在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。 本次授课到此结束 谢谢大家 作业 §1.4 二项式定理 定理 1.9 四个推论 推论1.9.1： 推论1.9.2： 推论1.9.3： 推论1.9.4： 证明：因为(x+y)n=(x+y)(x+y)…(x+y)，等式右端有n个因子，项xkyn-k是从这n个因子中选取k个，k=0,1,…,n。在这k个(x+y)里都取x，而从剩下的n-k个因子(x+y)中选取y作乘积得到，因此xkyn-k的系数为上述选法的个数C(n,k)。故有 证毕。 注：可用数学归纳法证明，证明略； C(n, k)又称二项式系数。 证明：在推论1.9.2中令x=1，即可得证。 利用组合分析，等式左端相当于从A={an}中任意选择k(0≤k≤n)个元素的所有可能数目，即对n个元素，每一个都有被选择和不被选择的可能，总的可能数为2n。 另外，该等式还表明A的所有子集个数为2n。 证明：在推论1.9.2中令x=-1，即可得证。 另外，该等式还表明A={an}的偶数子集个数和奇数子集个数相等。 §1.4 二项式定理 定理 1.10 定义 1.8 广义二项式系数 为： 牛顿二项式定理： * 济南大学教学课件件 ise_wangxh ujn.edu.cn 1、与组合数相关的的典型例题 例2、从1~300之间任取3个不同的数，使得这3个数的和正好被3除尽，问共有几种方案？ 例4、求5位数中至少出现一个6，而被3整除的数的个数。 例5、求1000!的末尾有几个零。 2、重排列 （1）重集B={∞*b1, ∞*b2, … , ∞*bn} 的r?排列的个数为nr。 （2）重集B={n1*b1,n2*b2,…,nk*bk}的全排列个数为 例1、由数字1,2,3,4,5,6这六个数字能组成多少个五位数？又可组成多少大于34500的五位数？ 例7、用字母A、B、C组成五个字母的符号，要求在每个符号里，A至多出现2次，B至多出现1次，C至多出现3次，求此类符号的个数。 例 题 例6、有四面红旗，三面蓝旗，二面黄旗，五面绿旗可以组成多少种由14面旗子组成的一排彩旗？ 解：这是一个重排列问题，是求重集{4*红旗,3*蓝旗,2*黄旗,5*绿旗}的全排列个数， 根据定理，一排彩旗的种数为 例 题 例7、用字母A、B、C组成五个字母的符号，要求在每个符号里，A至多出现2次，B至多出现1次，C至多出现3次，求此类符号的个数。 解：这也是一个重排列问题。根据分析，符合题意的符号个数相当于求重集M={2*A,1*B,3*C}的5?排列个数， 可分为三种情况： 需要分别求M-{A}、M-{B}和M-{C}的全排列个数。 根据加法法则，此类符号个数为 无法直接应用定理1.4 §1.2 排列 定义 1.4 1.2.4 项链排列 对圆排列，通过转动、翻转可重合的，即可看作项链排列。 如n个不同元素的r?项链 排列个数为P(n,r)/(2×r)， 具体参照Pólya定理。 重集B={n1*b1,n2*b2,…,nk*bk}的全排列个数为 证 为确定排列数， 首先注意到可以用C(n，n1)种方式在n个位置中放n1个b1，剩下n-n1个空位。 然后用C(n-n1， n2)种方式放b2，剩下n-n1 -n2个空位。 继续放b3， … ，bk-1，直到最后可用C(n-n1-n2- …-nk-1,nk)种方式bk。 因此，由乘积法则，不同的排列总数是 C(n，n1)