组合数学基础.ppt

组合数学基础组合数学基础 加法原理: 做一件事情,完成它可以有 n类办法,在第一类办法中有m1 种不同的方法,在第二类办法中有 m2种不同的方法, ……,在第 n类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+...+ mn 种不同的方法。 乘法原理: 做一件事情,完成它需要分成 n个步骤,做第一步有 m 1 种不同的方法,做第二步有 m 2种不同的方法, ……,做第 n步有种m n不同的方法,那么完成这件事有 N=m 1*m 2*... *m 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) 表示. 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个盒子,那么至少有一个盒子包含两个或更多的物体。例2:在 13个人中必存在两个人,他们的生日在同一月份里。例3:设有 n对已婚夫妇。为保证有一对夫妇被选出,至少要从这 2n个人中选出多少人?( n+1 ) 加强形式令q1,q2,... qn为正整数。如果将 q1+q