离散数学－计数技术 南京大学计算机科学与技术系 排列组合 离散数学－计数技术 南京大学计算机科学与技术系

引言--算法分析中的计数 k:=0 for i:=1 to m k:=k+1 for j:=1 to n k:=0 for i1:=1 to n for i2:=1 to i1 for i3:=1 to i2 k:=k+1 10的4次方－1:正整数个数； 9的4次方－1:不含1的正整数； 相减得结果

基本原则 乘法原则 加法原则 做一件事有两个步骤，第一步有n种完成方式，第二步m种完成方式，则完成这件事情共有m×n种方法 例: A是有限集合， |A|=n. A的幂集有几个元素？ p(A) = 2n. 加法原则 一件事情有两种做法，第一种做法有n种方式，第二种做法有m种方式，则完成这件事情共有m＋n种方法 例： 在37位教师和83位学生中选一位校委会代表，多少种选择？ 10的4次方－1:正整数个数； 9的4次方－1:不含1的正整数； 相减得结果

n个元素的r排列 在n个元素的集合中，有序取出r个元素，元素不重复，有多少种可能？ n 1 r P(n,r)= n(n-1)…(n-r+1)=n!/(n-r)! //P(n,0)=1 n 1 r r个“对象”到n个对象的单射

例题 从52张扑克牌中发5张牌，如果考虑发牌次序，共有多少种牌型？ 密码是字母开头8位长字母和数字串，总共可以设计多少个密码？ 密码是字母开头8位长字母和数字串，如果不允许字母或者数字重复，总共可以设计多少个密码？ 将26个英文字母进行排列，有多少种排列以TXP开头？ 将26个英文字母进行排列，有多少种排列中含有TXP串？

r组合 考察有n个元素的集合，如果取r个元素出来，共有多少种取法？ 用乘法原则来证明！ r组合：c(n,r)=c(n,n-r) r组合：c(n,r)=P(n,r)/r! =n!/[r!(n-r)!] 用乘法原则来证明！ r组合：c(n,r)=c(n,n-r)

示例 从52张扑克牌中发47张牌，如果不考虑发牌次序，共有多少种牌型？ 从5个妇女和15个男性中选出一个包含2名妇女的5人委员会，有多少种可能？ 从5个妇女和15个男性中选出一个至少包含2名妇女的5人委员会，有多少种可能？

r组合 r c(n,r)=2n n个元素的集合到{Y, N}的函数，共有2n个 1 Y N 含有r个1的n位0-1位串 n | f -1(Y)|=r r c(n,r)=2n 含有r个1的n位0-1位串

园排列 从n个不同元素中，取r个不重复的元素排成一个圆圈，有P(n,r)/r种排列方法 每一种排列结果，在园的概念下都重复了r次

有重复（不可区分）物体的排列 把单词“mathematics”中的字母重新排列，可以得到多少个不同的字符串（单词）？ 2个m，2个a， 2个t，1个h，1个e，1个c, 1个i, 1个s. 11个位置(2+2+2+1+1+1+1+1) ，选2个放置m， 乘下的9个位置，选2个放置a， … C(11, 2) C(9, 2) C(7, 2) C(5, 1) C(4, 1) C(3, 1) C(2, 1) C(1, 1) 11!/(2! 2! 2! 1! 1! 1! 1! 1!)

有重复的排列 在n个有不可区分项的对象集中，若有k类对象，各类对象的数目分别为n1，…, nk, n排列的个数是： n!/(n1! …nk!), 其中 n=n1+…+nk nk n1 1 n n个不同位置赋予k个类别，各类别的数量为n1,…,nk

一种取法对应于一个有4个0和2个1构成的0-1串，C(6, 4) 有重复的组合 厨房有三种水果，每样都足够多（超过4个）。从厨房取4个水果，有多少种取法？ **** ** * * 一种取法对应于一个有4个0和2个1构成的0-1串，C(6, 4)

n种不同元素中，可重复的r组合 C(r+n-1, r) 例 含r个0和(n-1)个1的0-1串，这种0-1串的个数 甜点店4种面包，买6个面包的买法有几种？ k:=0 for i1:=1 to n for i2:=1 to i1 for i3:=1 to i2 k:=k+1 可重复地从{1, …,n}中选取3个数：ni1 i2  i3 1 C(n+2, 3)

n种不同元素中，可重复的r组合 x+y+z=11有多少组解？其中x,y,z是非负整数 如果x1,y 2, z3时，上述方程有多少组解？ 3种水果足够多，取11个水果的方案 如果x1,y 2, z3时，上述方程有多少组解？ (x’+1) + (y’+2) + (z’+3)=11，其中x’,y’, z’是非负整数 x’ + y’ + z’ =5 ，其中x’,y’, z’是非负整数

不同物体分配到不同盒子 n个不同物体分配到k个不同的盒子中，使得第i个盒子包含ni个物体（i=1,…,k），有多少种分配方案？ 1 n1 n!/(n1! …nk!)

不同物体分配到不同盒子（示例） 52张扑克牌发给4个人使得每人5张 1 5 52!/(5! 5! 5! 5! 32!) 32 52 意味着“第5人”拿到32张 5 1 52 32 52!/(5! 5! 5! 5! 32!)

含n个0和(k-1)个1的0-1串，C (n+k-1, n) 相同物体分配到不同盒子 n个相同物体分配到k个不同的盒子中，有多少种分配方案？ x1+…+xk=n 的非负整数解 x1 x2 xk xk个* x1个* … 含n个0和(k-1)个1的0-1串，C (n+k-1, n)

不同物体分配到不可辨别的盒子 S(n, k): Stirling number of the second kind k-划分 (nk) S(n+1, k) = k * S(n, k) + S(n, k-1), S(0, 0)=1

不同物体分配到不可辨别的盒子 n个不同物体分配到k个不可辨别的盒子，允许空盒 j=1..k S(n,j) n个元素上的等价关系（个数） Bn=j=1..n S(n,j) // Bell number B0=B1=1

相同物体分配到不可辨别的盒子 k个盒子，不允许空盒 k个盒子，允许空盒 x1+…+xk=n 的正整数解， x1…  xk 1 x1+…+xj=n 的正整数解， x1…  xj1, jk

Stirling number of the second kind S(n, k), 或 n个不同物体分配到k个不可辨别的盒子，不允许空盒 k-划分 (nk) k! S(n, k): [1..n]  [1..k] 满射的个数

Stirling number of the second kind [1..n]  [1..k] 满射的个数？（Section 7.6） U={ f | f :[1..n]  [1..k] }, Aj={f U | f(x)  j, x=1, …n}, j=1,..,k kn-C(k, 1) (k-1)n+C(k, 2) (k-2)n- …

作业 教材 5.3；5.5； 作业 P277：8；16；20；24；30 P292：10；14；17