文档介绍：第一章组合数学基础
绪论
两个基本法则
排列与组合
组合等式及其组合意义
多项式系数
排列的生成算法
组合的生成算法
应用举例
斯特灵(Stirling)近...<br****题一
计数的两条基本法则
加法法则(加法原理,加法原则,和则)
若完成一件事有k种不同的方案,第1种方案有n1种方法,第2种方案有n2种方法,…,第k种方案有nk种方法,所有方法均不相同,其中任何一种方法均可完成此事,则完成这件事的方法总数是n1+n2+…+nk.
乘法法则(乘法原理,乘法原则,积则)
若完成一件事可分为k个步骤,第1步有n1种方法,第2步有n2种方法,…,第k步有nk种方法,各步骤需连续完成才能完成这件事,则完成这件事的方法总数是n1*n2*…*nk.
&
(,男女均可做,共多少种方案?)
排列计数公式
相异元素不允许重复的排列:从n个元素中取出r个的排列数
相异元素允许重复的排列:从n个元素中取出r个的排列数为
排列计数公式(从n个元素中取出r个)
相异元素不允许重复的圆排列数
相异元素不允许重复的项链排列数
第一章组合数学基础
绪论
两个基本法则
排列与组合
组合等式及其组合意义
多项式系数
排列的生成算法
组合的生成算法
应用举例
斯特灵(Stirling)近似公式<br****题一
组合等式及其组合意义
C(n, r)=C(n-1, r)+C(n-1, r-1)
C(n, k) C(k, r)=C(n, r) C(n-r, k-r)
C(n, r)=C(n, n-r)
组合等式例子:
组合等式及其组合意义
目的: 证明组合等式
主要方法:组合意义法
其他方法:母函数法;归纳法;……
组合意义法:是指借助于阐明等号两端的不同表达式实质上是同一个组合问题的方案数(即殊途同归法), 或者虽是两个不同组合问题的方案数, 但二者的组合方案之间存在着一一对应关系, 因此等式两端必须相等, 从而达到证明等式成立的目的。对于恒等式的实质揭露得更为深刻。
母函数法:利用无穷级数(包括有限时的多项式)证明有关组合等式。是产生和证明组合恒等式的普遍方法。
归纳法, 迭代法, 等等
等式1:对称关系式
C(n, r)=C(n, n-r)
组合意义: 从n个元素中取走r 个, 必然余下n-r个, 故从n取r的组合与从n取n-r的组合一一对应。
等式2:加法公式
C(n, r)=C(n-1, r)+C(n-1, r-1)
证明思路:将r 组合分成两类
(包含某元素;不包含某元素)。
例:从{1, 2, 3, 4, 5}中取3个的组合情况为:
第一类(包含元素“1”):
123, 124, 125, 134, 135, 145
第二类(不包含元素“1”):
234, 235, 245, 345
加法公式