组合数学第一章-3.pptVIP

模型转换--------允许重复的组合 定理1：从n个不同的元素中取r个，允许重复的组合数为 使得bi=ai+i-1,i=1,2,…,r. 则b1b2…br满足1≤b1＜b2＜…＜br≤n+r-1 b1b2…br∈C(n+r-1,r) f： a1a2…ar→b1b2…br 显然f是单射， 定理2：r个无区别的球放入n个有标志的盒子里，每个盒子中可多于一个。共有 相当于将n个球放入r个有标志的盒子（即不同的变量）里，每个盒子中可多于一个。 3。不相邻的组合 定理：从n个不同的元素中取r个不相邻的组合数为 例：1000！有多少个连续的0？ 这个问题相当于求5的次幂是多少，2的次幂是多少 第五节 组合恒等式 组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。 若干等式及其组合意义 1. C(n,r)=C(n,n-r)　　 　(1.5.1)　　 从[1,n]去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。 故C(n,r)=C(n,n-r) 2. C(n,r)=C(n-1,r)+C(n-1,r-1) (1.5.2) 从[1,n]取a1,a2,…,ar.设1≤a1＜a2＜…＜ar≤n,对取法分类：a1=1,有C(n-1,r-1)种方案 a11,有C(n-1,r-1)种方案 共有C(n-1,r)+C(n-1,r-1)中方案，故 C(n,r)=C(n-1,r)+C(n-1,r-1) 从[1,n+r+1]取a1a2…anan+1，设a1＜a2＜…＜an ＜ an+1，（不重复的组合） [2]从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上) r (n+1,r) . . . (0,0) n n+1 4. ( )( )=( )( ) (1.5.4) ①选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委 ②选常委,再选非常委政治局委员 两种选法都无遗漏,无重复地给出可能的方案，应该相等。 n l n n-r l r r l-r 也可直接计算。 证1 从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类.