[SinGuLaRiTy] 组合数学

2018-06-17 23:03:23来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

【SinGuLaRiTy-1005】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved .

加法原理

设事件A有m种产生方式,事件B有n种产生方式,则事件A或B之一有m+n种产生方式。
集合论语言:若 |A| = m , |B| = n , A∩B =  Φ, 则 |AUB| = m + n 。

<例>

(1)某班选修企业管理的有 18 人,不选的有 10 人,则该班共有 18 + 10 = 28 人。

(2)北京每天直达上海的客车有 5 次,客机有 3 次, 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。

乘法原理

设事件A有m种产生式,事件B有n种产生方式,则事件A与B有 m · n种产生方式。
集合论语言:若 |A| = m , |B| = n , A*B = {(a,b) | a∈A,b ∈ B}, 则 |A * B| = m * n 。

<例>

(1) 某种字符串由两个字符组成,第一个字符可选自{a,b,c,d,e},第二个字符可选自{1,2,3},则这种字符串共有5 * 3 = 15 个。

(2) 从A到B有三条道路,从B到C有两条道路,则从A经B到C有3 * 2=6 条道路。

(3*)a.求小于10000的含1的正整数的个数

分析:

小于10000的不含1的正整数可看做4位数,但0000除外.
故有9×9×9×9-1=6560个.
含1的有:9999-6560=3439个

         b.求小于10000的含0的正整数的个数

分析:

不含0的1位数有9个,2位数有9*9  个,3位数有9^3  个,4位数有9^4 个 
不含0小于10000的正整数有9+9^2+9^3+9^4 =7380个
含0小于10000的正整数有9999-7380=2619个

排列与组合

定义:从n个不同的元素中,取r个不重复的元素,按次序排列,称为从n个中取r个的无重排列。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为  P(n,r) 。

排列:从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择,第2个有n-1种选择,······,第r个有n-r+1种选择。故有P(n,r)=n(n-1)······(n-r+1)。

组合:从n个中取r个的组合的典型例子是从n个不同的球中,取出r个,放入r个相同的盒子里。每个盒子要放一个球。每一种组合方案都可以衍生出r!种排列方案来。C(n,r)=p(n,r)/r! 。

<组合公式的性质>

性质1:C(n,0)=C(n,n)
性质2:C(n,k)=C(n,n-k)
性质3:C(n,k)+C(n,k+1)=C(n+1,k+1)

二项式定理:

<例>

1.有重复元素的全排列

有k种元素,其中第i种元素有ni个,所有元素一共是n个。求全排列的个数.
解:设元素的总数为n。它同一类元素被重复计算了ni!次.所以答案为:n!/(n1!*n2!*…nk!)

2.可重复选择的组合

有n个不同的元素,每个元素可以选多次,一共选择k个元素,有多少种方法?

如n=3,k=2,有6种选择:(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)

分析:设第一个元素选择x1个,第二个元素选择x2个,……,第n个元素选择xn个。则有方程:x1+x2+……xn=k。问题转换为求方程的非负整数解的个数。令yi=xi+1,则答案为y1+y2+…+yn=k+n的正整数解的个数。想想k+n个相同的小球拍成1列,现在要把它分成n个部分,则只需在其中放置n-1块隔板即可。一共有k+n-1个位置用来放隔板,所以答案为C(n+k-1,n-1)

集合拆分

<整数的无序拆分>

将一个整数n拆成无序的k个数的和,问有多少种方法?

将n个相同的球全部放入k个相同的盒子,问有多少种方法?
        p(n,k)=p(n-1,k-1)+p(n-k,k)

<集合的无序分拆(第二类stirling)>

将一个包含n个元素的集合拆成k个子集,每个子集非空,且子集之间无交集,问有多少种方法?

        设S(n,k)表示解,则S(n,k)=S(n-1,k-1)+S(n-1,k)*k,其中S(n,n)=1,S(n,1)=1,若i<j,则S(i,j)=0.

将n个不同的小球全部放入k个相同的盒子,要求每个盒子都不为空。

<集合的有序分拆>

将一个包含n个元素的集合拆成有序的k个子集,每个子集非空,且子集之间无交集,问有多少种方法?

将n个不同的小球全部放入k个不同的盒子,要求每个盒子都不为空。
设S(n,k)表示集合n的无序分拆,则本题的答案为:
              k!*S(n,k)
其中S(n,n)=1,S(n,1)=1,若i<j,则S(i,j)=0

<整数的有序拆分>

将一个整数n拆成有序的k个数的和,问有多少种方法?

将n个相同的球全部放入k个不同的盒子,问有多少种方法?

C(n-1,k-1)

<*经典分配问题12态>

 第一类Stirling数

将n个不同的数分成k个非空循环排列一共有多少种方法。

S1(n,k)=S1(n-1,k-1)+(n-1)*S1(n-1,k)
递推关系的说明:
考虑第n个数,n可以单独构成一个非空循环排列,这样前n-1种数构成k-1个非空循环排列,方法数为s1(n-1,k-1);
也可以前n-1种数构成k个非空循环排列,而第n个数插入第i个数的左边,这有(n-1)*s1(n-1,k)种方法。

鸽笼原理

又名抽屉原理。有n个鸽笼,现在放入m只鸽子(m>n)则必有两只鸽子在一个笼子。

容斥原理

如果被计数的事物有A、B、C三类,那么,A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。

(A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C)

<公式>

 

Time : 2017-02-08

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:03:成绩排序 个人博客:doubleq.win

下一篇:02:奇数单增序列 个人博客doubleq.win