[已注销]对《组合数学》的笔记(2)

组合数学
  • 书名: 组合数学
  • 作者: 布鲁迪
  • 页数: 425
  • 出版社: 机械工业出版社
  • 出版年: 2005-2
  • 第168页

    证明某个计数问题的答案是一个特殊序列的简单方法是证明它们的递推式相同。

    2012-12-14 11:37:04 回应
  • 第1页

    2.1 基本的计数原理 加法原理:若集合S分割成m个不相交的部分(part)S1……Sm,集合S元素的的个数等于各个“部分”元素个数的和 乘法原理:若S是有序对(a, b)的集合,如果a来自大小为p的集合,b来自大小为q的集合,那么S的大小为p*q 我们将S根据不同的a划分为p个部分,每个部分又可以根据不同的b划分为q个部分 例如 a<-{1, 2, 3} b<-{x, y} a=1 2个 a=2 2个 a=3 2个 2+2+2=6个 因此,乘法原理是加法原理的一个推论 通过这两个原理我们可以将数数的过程分为几个步骤。 2.2 集合的排列 n元集合的r排列:第一个位置有n种,第二个位置有n-1种……一个有r个位置。 由乘法原理导出 P(n,r)=n!/(n-r)! n元集合的循环r排列数是P(n,r)/r,因为每r个环就形成一个等价类 2.3 集合的组合 n元集合的r组合(对于r排列,不考虑这些数之间的差异) (n r) = p(n, r)/(r!) = n!/(r! * (n-r)!) 2.4多重集合的排列 多重集合是指某个对象多次出现例如 {3.a, 4.b, 5.c}的12排列就是 (3+4+5)/3! 4! 5!,且它的13排列不存在! 我们可以这么思考问题:12个位置中先选出a的位置,一共有(12 3)种,确定以后,不需要进行排列,因为这三个位置只能放a a a;接着在剩下9个位置中选出4个来放b,是(9 4);最后在5个位置没得选 (5 5) (12 3)=12!/(3! 9!) (9 4)=9!/ (4! 5!) (5 5)=5!/(1 5!) 即12!/(3! 4! 5!) 如果我们问{3.a, 4.b, 5.c}集合的3排列数是几相当于问下面这个集合的3排列。 因为{&.a, &.b, &.c}中选3个数出来,怎么取,都不会把任何一个元素取空。 也相当于{3.a, 3.b, 3.c}的三排列数,即{k.a, l.b, m.c} min{k,l,m}>=3即可 2.5 多重集合的组合 集合{2.a, 1.b, 3.c}的3组合 先来看无穷集合{&.a, &.b, &.c}的3组合 即求x1+x2+x3=r的非负整数解(解集)个数 其中x1代表有几个a(0个,1个,2个,3个) x2代表几个b,x3代表有几个c x1=3,x2=0,x3=0(3个a,0个b,0个c) x1=2,x2=1,x3=0(2个a,1个b,0个c) …… 它等价于{r.1, k-1.*}的排列个数:原因是我们可以把“求x1+x2+x3=r的非负整数解(解集)个数”的过程转变为如下问题: 在r个1之间,添加k-1个分割符号*: 如: 1*1*1 表示 1个a,1个b,1个c 相同的情况还有{3.a, &.b, 99.c}的3组合个数 只要abc的个数均>=3时均可以用非负整数解的方法来计数 {&.a1, &.a2... &.an} n元无限重复数的r组合为(r+n-1 r) == (r+n-1 n-1) 通过变量代换的方法,我们可以限制每种对象在r组合中出现的次数: 例如{10.a, 10.b, 10.c, 10.d}中每个对象至少出现1次的10组合的个数是多少? 相当于求: x1+x2+x3+x4=10的正整数解的个数,即xi>=1 我们令yi=xi-1 y1+y2+y3+y4=6 , yi>=0 只要我们求出了上述方程的非负整数解个数,把这些解加1,我们就得到了x1+x2+x3+x4=10的正整数解 y1+y2+y3+y4=6的非负整数解个数为(6+4-1 6)=(9 6)=84 3 鸽笼原理(断言) n+1只鸽子飞进n个笼子,至少一个笼子中有两只或两只以上鸽子。 加强版本: q1+q2+...qn-n+1只鸽子,n个笼子,那么要么第一个笼子里至少有q1只鸽子,要么第二个笼子里有q2只鸽子……要么qn只笼子里有qn只鸽子。 5.2 二项式定理 (x+y)^n=sum(k=0..n)x^(n-k) y^k 占看看第k项:(x+y)(x+y)(x+y)...=...(n k) x^n-k y^k... 展开后x^n-k y^k有多少个同类项呢?n个元素的k子集!在n个x+y中选出任意k个,从中取出x,然后在剩下的项中取出y,一共有(n k)个这样的项目! 5.4 多项式定理 (x+y+z)^n (x1+x2+x3+x4+x5)^7展开式中 x1^2.x3.x3^3.x5 的系数是 7!/2! 3! (2x1-3x2+5x3)^6 展开式中 x1^3.x2.x3^2 的系数是 6!3! 2! (2)^3 (-3) (5)^2 6 容斥原理 直接计数不方便的情况下,间接计数 最常见的问题是求解 {3.a, 4.b, 5.c} 的10组合数目 T={&.a, &.b, &.c} S=集合T的10组合数量 A1:T的10组合中a的数量大于等于4的组合数量 A2:T的10组合中b的数量大于等于5的组合数量 A3:T的10组合中c的数量大于等于6的组合数量 那么 {3.a, 4.b, 5.c} 的10组合数目就是 | !A1 and !A2 and !A3 |=|S|-(|A1| + |A2| + |A3|)+(|A1 and A2| + |A1 and A3| + |A2 and A3|)- (A1 and A2 and A3) |S|=(10+3-1 2)=(12 10)= 计数A1的方法是,我们先选出{&.a, &.b, &.c}的6组合,然后剩下4个数都取a(反正a有无限个) |A1|=(6+3-1 2)=(8 6) ... 计数A1 and A2的方法是选出{&.a, &.b, &.c}的1组合,然后剩下9个数,选4个a,选5个b |A1 and A2|=(1+3-1 1) ... 而A1 and A2 and A3个数是0,因为不存在这样的组合 6.3 错位排列 给定x元集合X,其中每个元素都指定一个特定位置,现在要求X的排列中任意元素都不允许出现在指定位置上 这个问题的一个经典描述就是绅士取帽子的时候没有人拿到了自己的帽子。 错位排列Dn的公式为 Dn= n!(1-1/1! +1/2!- 1/3! + 1/4! +...+ (-1)^n * 1/n!) 满足递推关系: Dn=nDn-1 + (-1)^(n) (n=2,3,4) Dn=(n-1)(Dn-2+Dn-1) D1=1 D2=1 D3=3*1-1=2 D4=4*2+1=9 D5=5*9-1=44 D6=6*44+1=265 D7=7*265-1=154 ... 7 递推关系与生成函数 寻找计数问题的通项公式。 2^n这样的一个通项公式表示一个1 2 4 8……数列,它的组合意义在于求n元集合子集数。 14 Polya计数 Burnside定理可以简单地描述为 着色方案数是在所有置换下保持不变的着色方案数的平均数 即我们求着色方案数时,我们可以求每种置换下的保持不变的着色数,然后求和,然后除以置换总数 ==== 最简单的例子 给一条线段两个端点上红白两色 两个置换 在置换下保持不变的着色数 [1]o[2] 2*2=4 [1 2] 2 n= 4+2/2=3 即【红白】【红红】【白白】 ==== 而在统计每个置换下的着色方案时,只要使用polyia计数法,即对置换f进行因式分解为k个循环,若每个循环有j中颜色选择,那么就有j*j*j*j(k个 j)=j^k种着色方法。 例如,我们用红、白、蓝三种颜色对正方形顶点进行上色,问有多少种着色方案? 有8个置换,四个是代表旋转(平面对称),四个代表翻转(空间对称) 循环因式分解 循环个数 着色数 [1]o[2]o[3]o[4] 4 3^4=81 [1 2 3 4] 1 3 [1 3] o [2 4] 2 3^2=9 [1 4 3 2] 1 3^1 [1]o[2 4]o[3] 3 [1 3]o[2]o[4] 3 [1 2]o[3 4] 2 [1 4]o[2 3] 2 81+3+9+.../8=21 使用这种方法并不不能解决“确定颜色使用特定次数时”非等价的着色数。 于是需要引入循环指数的概念,它的本质是在保留循环个数信息的同时保留循环各个阶数的信息。 还是正方形的例子: 循环因式分解 循环个数 类型 单项式 [1]o[2]o[3]o[4] 4 (4,0,0,0) z1^4 [1 2 3 4] 1 (0,0,0,1) z4 [1 3] o [2 4] 2 (0,2,0,0) z2^2 [1 4 3 2] 1 (0,0,0,1) z4 [1]o[2 4]o[3] 3 (2,1,0,0) z1^2*z2 [1 3]o[2]o[4] 3 (2,1,0,0) z1^2*z2 [1 2]o[3 4] 2 (0,2,0,0) z2^2 [1 4]o[2 3] 2 (0,2,0,0) z2^2 P=(z1^4 + 2*z4 + 3*z2^2 + 2*z1^2*z2 )/8 如果不限颜色次数,一共k种颜色,那么P=(k^4+2k+3k^2+2*k^3)/8 设有两种颜色,k=2,P=(16+4+12+16)/8=2+2+2=6 或设两种颜色分别为r和b z1=r+b z2=r^2+b^2 z3=r^3+b^3 z4=r^4+b^4 P(z1, z2, z3, z4)=r^4 + r^3 * b + 2r^2 * b^2 + r * b^3 +b^4 从这个式子就中就可以看出4四个颜色都上红色的方案是1种,3红1蓝1种……4蓝也是1种。

    2013-01-16 19:33:25 回应

[已注销]的其他笔记  · · · · · ·  ( 全部295条 )

The Design of Everyday Things
1
About Face 3
6
Engineering a Compiler
1
人有人的用处
8
Understanding the Linux Kernel
4
计算机程序设计艺术
1
公正
1
The Art of Doing Science and Engineering: Learning to Learn
1
科学革命的结构
7
罗素论教育
3
三十六大
1
娱乐至死
3
Real World Haskell
2
Writing Analytically
1
Is Parallel Programming Hard, And, If So, What Can You Do About It?
1
计算机与人脑
1
菊与刀
1
Rework
5
翻译新究
4
计算机程序的构造和解释(原书第2版)
5
The Laws of Simplicity
4
计算机组成与设计硬件/软件接口
6
写给无神论者
2
放任自流的时光
3
哥德尔、艾舍尔、巴赫
2
树上的男爵
2
C++语言的设计与演化
1
Land of LISP
7
C陷阱与缺陷
2
CUDA by Example
3
C++沉思录
1
世界尽头与冷酷仙境
4
Head First C
2
刀锋
1
并行编程模式
2
The Ph.D. Grind
2
计算机系统结构
2
禅与摩托车维修艺术
14
流浪的面包树
2
翻译研究
18
An Introduction to Programming in Emacs Lisp
1
GNU Emacs Lisp 编程入门
1
计算机系统概论
1
编码
3
拖延心理学
1
古今数学思想(一)
1
挪威的森林
9
奇特的一生
7
GPU高性能运算之CUDA
5
那些年,我们一起追的女孩
8
十八岁给我一个姑娘
2
C++编程思想(第1卷)
9
多核计算与程序设计
8
少有人走的路
5
忧伤的情欲
3
Hackers & Painters
7
哲学的慰藉
9
男人来自火星 女人来自金星
8
旅行的艺术
14
活着活着就老了
1
如何阅读一本书
7
Data-intensive Text Processing With Mapreduce
1
学习GNU Emacs
1
给研究生的学术建议
3
C专家编程
2
Spring揭秘
2
Head First Java(第二版·中文版)
1
自私的基因
1
C程序设计语言
2
计算机网络
3
自由在高处
2
大话设计模式
16
计算机网络
12