可重组合与组合恒等式

1

《图论与组合优化》第三讲

可重组合与组合恒等式2允许重复的排列---多重集的排列多重集—元素可以多次出现的集合，即元素可以重复。我们把某个元素ai出现的次数ni(ni=0,1,2,…)叫做该元素的重复数，通常把含有k种不同元素的多重集S记作3

可重排列定义从一个多重集中有序选取的r个元素叫做S的一个r-(可重)排列。当时也叫做S的一个排列.4定理设多重集则的r-(可重)排列数是rk5例求4位数的二进制数的个数解：所求的标志数是多重集{2红旗，3黄旗}的排列数，故N=5!/(2!*3!)=10例用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？

6允许重复的组合----可重组合允许重复(可重)的组合是指从中取r个元素,

允许重复，即允许.允许重复的组合个数记作C(n,r)定理1.2从中取r个作可重的组合，其个数为C(n+r-1,r)7定理1.2证明C(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每个盒子中球数不加限制的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。易知所求计数为=C(n+r-1,r)(n-1+r)!————r!(n-1)!

r个相同的球

/\———————

————————／\0…010…01…10…0

\/————————

\/

n-1个相同的盒壁8设a1a2…ar∈C(n,r)

1≤a1≤a2≤…≤

ai

≤…≤ar≤n,与下面的数列对应相加0<1<2<…<i-1<…<r-1即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是双射所以C(n,r)=C(n+r-1,r)－-1定理1.2证明－91.8.2不相邻的组合

不相邻的组合是指从序列{1,2,…,n}中取r个，不允许重复且不存在i,i+1两个相邻的数同时出现于一个组合中的组合定理1.4

从A={1,2,…,n}中取r个作不相邻的组合，其个数为C(n-r+1,r)10任给a1a2…ar∈C’(n,r),

a1＜

a2＜

…＜

ar≤n且

ai+1-ai≥2,i=1,2,…,r-1与下面的数列对应相减0<1<2<…<i-1<…<r-1得1≤b1＜

b2＜

…＜

br

≤

n-r+1，其中

bi=ai-i+1,i=1,2,…,rbi+1-bi≥1.b1b2…br∈C(n-r+1,r)令f：a1a2…ar→b1b2…br

C’(n,r)=C(n-r+1,r)定理1.4的证明11组合恒等式

如图，求从(0,0)点到(m,n)点、沿格子线走的最短路径数N。

一条到达点(m,n)的路径对应一个由m个x，n个y组成的排列xxxyyxyxxyyxxyyxxxy12若干组合等式(1)C(n,r)=C(n,n-r)

(2)C(n,k)=C(n-1,k)+C(n-1,k-1)

证明1：从{1,2,…,n}中取k个组合的全体可以分为两组：

A1组：含有元素n，|A1|=C(n-1,k-1)A2组：不含元素n，|A2|=C(n-1,k)13(2)C(n,k)=C(n-1,k)+C(n-1,k-1)

证明2：考虑如图棋盘从(0,0)到(k,n-k)的最短路条数为C(n,k)，其中经过P1点的有C(n-1,k),经过P2点的有C(n-1,k-1)。14四.若干组合等式(2)C(n,r)=C(n-1,r)+C(n-1,r-1)

(3)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+…+C(n+1,1)+C(n,0).证明1：由（2）可得。15(3)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+…+C(n+1,1)+C(n,0).证明2：从{1,2,…,n+r+1}中取r个组合的全体可以分为r+1组：A1：不含1，|A1|=C(n+r,r)A2：含1但不含2，|A2|=C(n+r-1,r-1)A3：含1,2，但不含3，|A3|=C(n+r-2,r-2)………Ar：含1,2,…,r-1，但不含r，|Ar|=C(n+1,1)Ar+1：由12…r组成的组合，|Ar+1|=C(n,0)16(4)C(n,k)C(k,r)=C(n,r)C(n-r,k-r),(k>r).证明：考虑如下问题，把Nn={1,2,…,n}分为甲、乙、丙三组，使得甲组恰有r个，乙组恰有k-r个，丙组恰有n-k个，其分法种数可以用两种方法计算。方法1：从Nn中取k个，余下的n-k个放在丙组；再从取出的k个中拨出r个分在甲组，余下的k-r个分在乙组，分法种数有C(n,k)C(k,r)。方法2：从Nn中取r个分在甲组，再从余下的n-r个中取出k-r个分在乙组，最后剩下的n-k个分在丙组，分法种数有C(n,r)C(n-r,k-r)。17(5)C(m,0)+C(m,1)+…+C(m,m)=2m.

(x+y)m=xm+C(m,1)xm-1y+C(m,2)xm-2y2+…+ym(6)C(n,0)-C(n,1)+C(n,2)-…+(-1)^nC(n,n)=0.(7)C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0),r<min(m,n).(8)C(m+n,m)=C(m,0)C(n,0)+C(m,1)C(n,1)+…+C(m,m)C(n,m),mn.18扑克问题每张扑克牌都有两种标志，一种是花色{♣♥♦♠}，另一种标志是数值

{2,3,4,5,6,7,8,9,10,J,Q,K,A}共52张。(1)从52张扑克牌中取出5张，使其中两张的值相同，另外3张的值也相同，有多少种方案？(2)取出5张扑克牌，出现两对同值的方案数是多少？(3)两个牌友A和B，各取五张，分别有两对相同的数值，问这样的状态有多少种？19有限制的路径问题从(0,0)点到达(m,n)点，其中m<n。要求中间所经过的路径上的点(x,y)恒满足x<y。问有多少不同的路径？售票问题一场音乐会票价50元，排队的顾客中有n位持50元的钞票，m位持100元的钞票。售票处没有准备零钱。试问有多少