基本的组合计数公式

《基本的组合计数公式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学第12章基本的组合计数公式12八月2021前言组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方…...前言幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言贾宪北宋数学家（约11世纪）著有《黄帝九章细草》、《算法斅古集》斅音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者

2、比霍纳（WilliamGeogeHorner，1786—1837）的方法（1819年）早770年。前言1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。计

3、数问题计数问题是组合数学研究的主要问题之一。西班牙数学家AbrahambenMeiribnEzra(1092～1167)和法国数学家、哲学家、天文学家LevibenGerson(1288～1344)是排列与组合领域的两位早期研究者。另外，法国数学家BlaisePascal还发明了一种机械计算器，这种计算器非常类似于20世纪40年代在数字电子计算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是很重要的，特别是在《数据结构》、《算法分析与设计》等后续课程中有非常重要的应用。内容提要二项式定理与组合恒等式3多项式定理4加法法则与乘法法则1排

4、列与组合2本章学习要求重点掌握一般掌握了解11加法法则和原理法则2排列组合的计算31离散概率2离散概念的计算公式及性质2二项式定理与组合恒等式计算组合问题的处理技巧一一对应数学归纳法上下界逼近一一对应与上下界逼近例1在允许移动被切割的物体的情况下，最少用多少次切割可以将333的立方体切成27个单位边长的立方体？中间的小立方体的6个面都是切割产生的面，每次切割至多产生一个面，至少需要6次切割。存在一种切割方法恰好用6次切割。例2100个选手淘汰赛，为产生冠军至少需要多少轮比赛？方法1：50+25+12+6+3+2+1=99方法2：比赛次数与淘汰人数之间

5、存在一一对应，总计淘汰99人，因此至少需要99场比赛.12.1加法法则与乘法法则开胃食品主食饮料种类价格(元)种类价格种类价格玉米片(Co)2.15汉堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85鱼排(F)3.15可乐(C)0.75啤酒(B)0.75表1乘法法则如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：例1Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过

6、以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？解根据Melissa病毒的扩散原理，经过四次转发，共有50×50×50×50+50×50×50+50×50+50+1=6377551个接收者。例2在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析用

7、8位进行编码可分为8个步骤：选择第一位，选择第二位，…，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有2×2×2×2×2×2×2×2=28=256种取值。解每个点有256(=28)种不同的取值。加法法则假定X1,X2,…,Xt均为集合，第i个集合Xi有ni个元素。如{X1,X2,…,Xt}为两两不相交的集合，则可以从X1,X2,…,Xt中选出的元素总数为：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选

8、出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Ali