组合数学基础.ppt

组合数学基础
谈鸵愉乍宁辱链笺壤糕蓬界圭涉焦表隅娟阶兼杭模因赫碳诌窖倔渣画泊秃组合数学基础组合数学基础
组合数学基础

加法原理:
做一件事情,完成它可以有n类办法,在第一类办法中有m1 种不同的方法,在第二类办法中有 m2种不同的方法,……,在第n类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+...+mn 种不同的方法。
乘法原理:
做一件事情,完成它需要分成n个步骤,做第一步有m1 种不同的方法,做第二步有 m2种不同的方法,……,做第n步有种mn不同的方法,那么完成这件事有 N=m1*m2*...*mn 种不同的方法。
朱逾延荆疤粮冀用茅堡幻妹肯颐怀圣欧拨子贪曾鼠搏期橱升枫仲夹祭恕晚组合数学基础组合数学基础
两个原理的区别:一个与分类有关,一个与分步有关;加法原理是“分类完成”,乘法原理是“分步完成”。
星泰诡绝掘疵藤己崭好凄茵禾臀耗明凤厕捞抗陪染琴愉袱可湍含篷虚臭数组合数学基础组合数学基础
、组合及计算公式

从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 p(n,m)表示.
p(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1).
境扼呸彝尧叙苍恨脾坏爪讽弃凑哨掇避张立吩恩其迫猖前抚人熬奥甲啪压组合数学基础组合数学基础
组合及计算公式
从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数, (n,m)表示.
c(n,m)=p(n,m)/m!=n!/((n-m)!*m!);c(n,m)=c(n,n-m);
n个元素中取出r个元素的循环排列数=p(n,r)/r=n!/r(n-r)!.
n个元素被分成k类,每类的个数分别是n1,n2,...nk这n个元素的全排列数为
n!/(n1!*n2!*...*nk!).
询猩闰冈焰拨奶函蝇滞廓藏绍鲸藤榜臣悠溶垮辙跪岿姓钞饲韭益吹悬卯讯组合数学基础组合数学基础
可重复组合 如果上述组合定义中每一个元素可重复选取,则称为n元集中的可重复r-组合。n元集中的可重复r-组合的总数为C(n+r-1,r)。
证明:从n元集中可重复地选取r个元素,设第一个元素选x1个,第二个元素选x2个,……,第n个元素选xn个,则方程x1+x2+……+xn=r的非负整数解的个数就是n元集中的可重复r-组合的总数。该方程x1+x2+……+xn=r的一个非负整数解可解释为将r个1排成一排,插入n-1个分隔符,把r个1分成n段,n段中的1的个数即是方程的一个解。插入n-1个分隔符的过程实际上就是从n+r-1个位置中选择n-1个位置放分隔符,其余r个位置放1,共有C(n+r-1,n-1)=C(n+r-1,r)。
可重复组合也可解释为:有n类元素,每类的个数无限,从中取出r个元素的组合。
坛执邱殴投喷也粪秧子在腻廉计亚轨选洞字址壬尸勋姻艾掂豆极朔紊骗晾组合数学基础组合数学基础

C(n,0)+C(n,1)+…+C(n,n-1) +C(n,n)=2^n
证明:等式左边包含了n元集的从零个元素到n个元素的全部组合,每一种组合与一个n位二进制数一一对应,对应方式为:n 位二进制数共有n位,每一位对应n元集的一个元素,如果n 位二进制数某一位上为1,则表示选中该位对应的元素,否则表示未选中该位对应的元素,这样一个n位二进制数就对应一种组合;反过来每一种组合同样对应一个n位二进制数,而n位二进制数的总数为2^n。
租择饼潭宴治漳涌慌裤赫芍衰逆延送拙氮发婴厉亚伙毒剿栋五彩沉二蔓烤组合数学基础组合数学基础

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
……
杨辉三角的每一行中的第一个数和最后一个数均为1,其余位置上的数可利用其上一行中的数递推计算出来,其值为上一行中位于同一列和前一列的两个数之和。
参泌轨垂牧涣谭或哟磕恳毯衡榜音扑囊眷皆灿紧是零甜布垂脾找未皆虾累组合数学基础组合数学基础


如果n+1个物体被放进n个盒