伤城文章网 > 数学 > acm 组合数学的艺术2

acm 组合数学的艺术2


ACM-Association for Computing Machinery ICPC-International Collegiate Programming Contest

Lecture 2 Generating Functions

By Yuhong Zhang (张玉宏) yhily@126.com, 186-2371-8860 (O), 159-3629-0516(H)

问题的导入
一道ACM试题 (offered by Weilong Zhang) ? 求装有苹果、香蕉、橘子和梨的果篮 的数量h[n],其中在每个果篮中苹果数 是偶数,香蕉是5的倍数,橘子最多是 4个,而梨的个数是0或1。 ? 比如h[1]=2,h[2]=3.
?

数学方法解决问题
?

利用generate function的方法,

公式从何而来?
因此得到h[n]=n+1.

问题2: 若有1克、2克、3克、4克的砝码各一

枚,能称出哪几种重量?各有几种可能方案?
4

如何解决这个问题呢?考虑构造母函数。 如果用x的指数表示称出的重量,则: 1个1克的砝码可以用函数1+x表示, 1个2克的砝码可以用函数1+x2表示, 1个3克的砝码可以用函数1+x3表示, 1个4克的砝码可以用函数1+x4表示,

2014-4-24

几种砝码的组合可以称重的情况,可 以用以上几个函数的乘积表示:
5

(1+x)(1+x2)(1+x3)(1+x4) =(1+x+x2+x3)(1+x3+x4+x7) =1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10
从上面的函数知道:可称出从1克到10克,系数便是方 案数。 例如右端有2x5 项,即称出5克的方案有2:5=3+2=4+1; 同样,6=1+2+3=4+2;10=1+2+3+4。 故称出6克的方案有2,称出10克的方案有1
2014-4-24

问题还在继续?
?

x+2y=10的非负整数解的个数
将这个思想表示为如下的公式: (1 + x + x^2 + x^3+...)(1 + x^2 + x^4 + x^6 +...) 求x^10的系数。

? ? ?

这是最简单的方 式吗?

Problem Description:HDU1028
?

"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this: N=a[1]+a[2]+a[3]+...+a[m]; a[i]>0,1<=m<=N; My question is how many different equations you can find for a given N.

Problem Description:HDU1028
?

For example, assume N is 4, we can find: 4 = 4; 4 = 3 + 1; 4 = 2 + 2; 4 = 2 + 1 + 1; 4 = 1 + 1 + 1 + 1; so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"

? x ? a?

n

A binomial is a polynomial with two terms such as x + a. Often we need to raise a binomial to a power. In this section we'll explore a way to do just that without lengthy multiplication.

? x ? a? ? 1 1 ? x ? a? ? x ? a 2 2 2 ? x ? a ? ? x ? 2ax ? a
0

Can you see a pattern? Can you make a guess what the next one would be?

3 2 2 3 x ? a ? x ? 3 ax ? 3 a x ? a ? ? 3

? x ? a ? ? x ? 4ax ? 6a x ? 4a x ? a 5 5 4 2 3 3 2 4 5 x ? a ? x ? __ ax ? __ a x ? __ a x ? __ a x ? a ? ?
4 4 3 2 2 3 4
We can easily see the pattern on the x's and the a's. But what about the coefficients? Make a guess and then as we go we'll see how you did.

Let's list all of the coefficients on the x's and the a's and look for a pattern.

? x ? a?
0

5

1

? 1x5 ? 5ax4 ? 10a 2 x3 ? 10a3 x 2 ? 5a 4 x ? 1a5
1 +1 1 +2 + 1

? x ? a? ? 1 1 ? x ? a ? ? 1x ? 1a 2 2 2 x ? a ? 1 x ? 2 ax ? 1 a ? ?
3

1 +3 3 1 + +
1 +4 +6 + 4 + 1

3 2 2 3 x ? a ? 1 x ? 3 ax ? 3 a x ? 1 a ? ?

1

5
3

10 10
4

5

1

Can you guess the next row?

? x ? a?

4

? 1x ? 4ax ? 6a x ? 4a x ? 1a
4 3 2 2

This is good for lower powers but could get very large. We will introduce some notation to help us and generalise the coefficients with a formula based on what was observed here.

1

1
1 1 3 2

1
1 3 1

1
1 5

4

6
10 10

4
5

1
1

This is called Pascal's Triangle and would give us the coefficients for a binomial expansion of any power if we extended it far enough.

The Binomial Theorem

? x ? a?

n

? n ? n ? n ? n?1 ? n? n ? ? ? x ? ? ? ax ? ? ? ? ? a ? 0? ?1? ? n?

The x's start out to the nth power and decrease by 1 in power each term. The a's start out to the 0 power and increase by 1 in power each term. The binomial coefficients are found by computing the combination symbol. Also the sum of the
powers on a and x is n.

Find the 5th term of (x + a)12
5th term will have a4

(power on a is 1 less than term number)

1 less than term number

?12 ? 4 8 4 8 a x ? 495 a x ? ? ?4?
So we'll have x8

(sum of two powers is 12)

Here is the expansion of (x + a)12

…and the 5th term matches the term we obtained! In this expansion, observe the following: ?Powers on a and x add up to power on binomial

?a's increase in power as x's decrease in power from term to term.
?Powers on a are one less than the term number
?Symmetry of coefficients (i.e. 2nd term and 2nd to last term have same coefficients, 3rd & 3rd to last etc.) so once you've reached the middle, you can copy by symmetry rather than compute coefficients.

Instead of x we have 2x Let's use what we've learned to expand (2x - 3y)6

Instead of a we have -3y

First let's write out the expansion of the general (x + a)6 and then we'll substitute.

? x ? a?

6

6 ax 5 ? 15 20 a 3 x 3 ? 15 6 a5 x ? a6 ? x 6 ? __ __ a 2 x 4 ? __ __ a 4 x 2 ? __
6 6 5 2 4

3 y ??will 2 xbe 15 ? 2x ? 3 y ? ? ? 2x ? ? 6 ? ? ? ? ? ?3 y ? ? 2 x ? ? these the same 3 3 4 2 5 6 the 20 ? ?3 y ? ? 2 x ? ? 15 ? ?3these y ? ? will 2 x ?be? 6 ?same ?3 y ? ? 2 x ? ? ? ?3 y ?
Let's find the coefficient Let's find the coefficient for we'll the second Now find theterm. 6 for the third term. coefficient of the 4th term

? 6 ? 6! 6 ? 5! ? ? 6 ?6 ? 6 5 6! 4 2 6 6 ? ? ? ? 6! 5 ? ? 5 4 ? ? 4! 3! ? ? ? 64 x ? 576 x? y ? 2160 x y ? 4320 x y 1?? ?? ? ? 5! ? ?15 20 term. 1!5! ?? ? 3 2 3!3! 2!4! 5 3 ?2 2??4! 3! 6 2 ? 4?? ? ?4860 x y ? 6 ??2916 729 y 6! xy 6? ? 5! ? ? ?6 ? ? Now we'll apply this formula to our5!1! specific binomial. 5 5! ? ?

Let's confirm thatalso this be is This will also the the coefficient of the coefficient of 3 3 2nd to last theterm. 3rd to last

?定理1.7(二项式定理)当n是一个正整数时 对任何x和y,有 n ? ? n ( x ? y ) n ? ? ( k ) x k y n ?k (1.12)?
k ?0

?证明:

? ( x ? y ) n ? ( x ? y )( x ? y )...( x ? y ) ???? ? ????? ?
n个

k 在这n个因子中,项 x k y n ?是从 n个因子 (x+y)中选取k个因子(x+y),k=0,1,… ,n。在这k个(x+y)里都取x,而从余下的nk个因子(x+y)中选取y作乘积得到。因此 k n ?k 的系数 上述选法的个数,即为 组 x y为 ?n? ? 合数 。故有 ?k ? ? n ? ? ? n ? k n-k n (x + y) = ? ? ?x y k=0 ? k ? 此定理也可用归纳法证明(略)。

当n是正整数时,对任何x,y均有
( x ? y ) ? ? ( n ?k ) x k y n ?k
n n k ?0 n n

( x ? y ) ? ? ( y ) x n ?k y k
n n k ?0 n

( x ? y ) ? ? ( n ?k ) x
n n k ?0

n ?k

y

k

?在实际应用中,y=1的情况经常出现,于是有下 列恒等式

?

推论2当n是正整数时,对所有的x有
(1 ? x )
n

?(1.13)

?

k ( ) x ? n ?k n k ?0

n

令x=1时,有推论3当n是正整数时,都 有 (1.14)
n ( ) ? 2 ? k n k ?0 n

?在式(1.13)中,令x=-1时,有推论4当n 是正整数时,有 (1.15) 注意,推论3表明,在具有n个元素的 集合中,所有子集的个数为2?n。推 论4表明,在具有n(n≠0)个元素的集 合中,偶数子集的个数与奇数子集的 个数相等。
k ?0 k ( ? 1 ) (k ) ? 0 ? n n

对于任何实数a和整数k,有
? a ( a ? 1)...( a ? k ? 1) k ?0 ? k ! ?a? ? 1 k ?0 ? ?k ? ??? ? ? ? 0 k?0 ? ?

? 为了区别二项式系数 为广义的二项式系数。 ?

?k ? ?k ?
n

, a称

?

定理1.8
式中

设α 是一个任意实数,则对于 满足|x/y|<1的所有x和y有
? a ? k a ?k ( x ? y) ? ?? ?k ? ?x y k ?o ? ?
a ?

? a ? a(a ? 1)...(a ? k ? 1) ? ?k ? ?? k! ? ?

在式(1.16)中,若令z=x/y,则有 推论1 对于|z|<1的任何z,有

(1.17)

(1 ? z )

a?

? 在式(1.17)中,若令α =-n(n为正整数),则有推论2 对于|z|<1的任何z,有? (1.18)
(1 ? z )
?n ? 1 k ? n ? k ? 1? k ? ? ? ( ?1) ? z ? n ? ? k (1 ? z ) k ?0 ? ?

?a? k ? ? ?k ? ?z k ?0 ? ?
?

证明:略

?

在式(1.18)中,令n=1,就有 ? n ? k ? 1?=1, ? ? ? ? 于是又得到 k ? ? 推论3 当|z|<1时,有 ? ? 1 k k ? ( ? 1 ) z ? (1.19) ? 1? z k ?0 又在式(1.19)中,用-z代替z,就有? 推论4 当|z|<1时,有

1 ? (1.20) ?? 1? z

?z
k ?0

?

k

2.1. Introductory examples
?

Ex 2.1.
? 12

oranges for three children, Grace, Mary, and Frank. ? Grace gets at least four, and Mary and Frank gets at least two, but Frank gets no more than five. ? (x4+ x5+ x6+ x7+ x8) (x2+ x3+x4+ x5+ x6)(x2+ x3+x4+ x5) ? The coefficient of x12 is the solution.

Ex 2.2
? ?

Four kinds of jelly beans, Red, Green, White, Black In how many ways can we select 24 jelly beans so that we have an even number of white beans and at least six black ones?
Red (green): 1+ x1+ x2+….+ x23+ x24 ? White: 1+ x2+ x4+….+ x22+ x24 ? Black: x6+ x7+….+ x23+ x24
?

?

?

f(x)=(1+ x1+ x2+….+ x23+ x24)(1+ x2+ x4+….+ x22+ x24)(x6+ x7+….+ x23+ x24) The coefficient of x24 is the solution.

Ex 2.3.
?

? ?

How many nonnegative integer solutions are there for c1+c2+c3+c4=25? f(x)=(1+ x1+ x2+….+ x24+ x25)4 The coefficient of x25 is the solution.

2.1母函数的基本概念
? 母函数又称发生函数或生成函数,它是解决 计数问题的一个重要工具。 ? ? 母函数的类型较多,这里仅讨论最常见的 两种类型的母函数: ? 1. 普通母函数 ? 2. 指数母函数 ?

下面,我们分别进行讨论。

一、普通母函数
? 给定一个无穷序列 (a0,a1,…,an,…)(简记为{an}, 下同),
f ( x ) ? a0 ? a1 x1 ? a2 x 2 ? ? ? an x n ? ? ? ? ai x i
i ?0 ?

?称函数

?为序列(a0,a1,…,an,…)的普通母函数。

2.2. Definition and examples: calculational techniques

普通母函数
?

? 必须注意的是,在定义2.1中,普通母函数是一个 无穷级数,没有必要去讨论它的收敛性,实质上它 只是引进一个表示序列的记号而已。

此时变量x只是一种形式变元。对这种级数 可以把它看成形式幂级数,我们可以按通常 方式定义其加法、乘法、形式微分等运算, 从而构成一个代数体系。

由定义2.1可知
一个序列和它的普通母函数是一一对 应的。给定了一个序列就可以得到这个序列 的普通母函数。 反之,如果给定了普通母函数,则序列 也随之而定。 由此可见,普通母函数实质上是序列的 另一种表达形式。

求序列

解:由定义2.1和式(1.13)有

??n? ?n? ?n? ? n?? ?? ?, ? ?1? ?, ? ?2? ?,? , ? ?n? ?? ?? 0? ? ? ? ? ? ? ? ? ? ? ?

的普通母函数。

?n? ?n? 1 ?n? 2 ?n? n f ( x) ? ? ? 0? ??? ?1? ?x ? ? ? 2? ?x ? ?? ? ?n? ?x ? ? ? ? ? ? ? ?

? (1 ? x)

n

求序列(0,1×2×3,2×3×4,…, n(n+1)(n+2),…)的普通母函数。
?

解:由式(1.20)有

? 1 ? ? xn 1 ? x n ?0

将上式两边同时微分两次得
? 2 n?2 ? ? n(n ? 1) x 3 (1 ? x) n ?0

将上式两边再微分有
?

再将上式两边同乘以x得

? 6 n ?3 ? n ( n ? 1 )( n ? 2 ) x ? 4 (1 ? x ) n ?0

? 6x n?2 ? n ( n ? 1)( n ? 2) x ? (1 ? x) 4 n ? 0

? ? n(n ? 1)(n ? 2) x n

?

由定义2.1知
普通母函数。

? 0 ? 1 ? 2 ? 3x1 ? 2 ? 3 ? 4 x 2 ? ? ? n(n ? 1)(n ? 2) x n ? ?

n ?0

f(x)=6x/(1-x)4是序列
(0,1×2×3,2×3×4,…,n(n+1)(n+2),…)的

二、指数母函数
? 由上面的例子可见,普通母函数特别适用 于某些序列,尤其是包含组合数的序列,这 是由于它具有牛顿二项式定理的形式。

但是,对于具有排列数的那些序列,我
们考虑下列类型的母函数(指数母函数)更 为合适。

给定无穷序列(a0,a1,…,an,…),称函数
x1 x2 xn f e ( x ) ? a0 ? a1 ? a2 ? ? ? an ?? 1! 2! n!
? n

x ? ? an n! n ?0 为序列(a0,a1,…,an,…)的指数母函数。
?

之所以称为指数母函数是由于式(4.2)的 右边很像指数函数e的幂级数展开式。 注意,指数母函数也是形式幂级数。

2.4. The exponential generating function

设n是整数,求序列
(p(n,0),p(n,1),…,p(n,n))的

指数母函数fe(x)。
?

解:由定义2.2和式(1.7)以及例1的结论有
x1 x2 xn f ( x) ? p(n,0) ? p(n,1) ? p(n,2) ? ? ? p(n, n) ? 0 ? ? 1! 2! n!
?n? ?n? ?n? 2 ?n? n ?? ? 0? ??? ?1? ?x ? ? ?2? ?x ? ? ? ? ?n? ?x ? ? ? ? ? ? ? ? (1 ? x ) n ? ? (1 ? x )n
n

k ( ) x ? n ?k n k ?0

例4

求序列{1,a,a2,…an,…}的

指数母函数fe(x)。其中α 是实数。

解:由定义2.2知
x 2 x n x f ( x) ? 1 ? a ? a ??? a ? ? ? eax 1! 2! n!
?
1 2 n

若α =1,则序列(1,1,…,1)的

指数母函数为ex。

例5

求序列(1,1×4,1×4×7,…, 1×4×7×…×(3n+1),…)的 指数母函数。 ?

解:由定义2.2和二项式定理式(1.16)有
x1 x2 f e ( x ) ? 1 ? (1 ? 4) ? (1 ? 4 ? 7) ? ? 1! 2! n

1 ? 4 ? 7 ? ? ? (3n ? 1) n ?? x n! n ?0
?

x ? 1 ? 4 ? 7 ? ? ? (3n ?) ? ? n! ? a ( a ? 1)...( a ? k ? 1)
? a ? ? ? ? ?k ? ??? ? ? ? ? ? k! 1 0

? (1 ? 3x)?4 / 3

k ?0 k ?0 k?0

?

由定义4.2易见,序列(a0,a1,…,an,…)的指 数母函数也是序列(a0,a1,a2/2!,…,an/n!,…) 的普通母函数。

这说明普通母函数与指数母函数 之间有着密切的联系,这种联系 可由下面的定理表出。

设f(x),fe(x)分别是序列 (a0,a1,…,an,…)的普通母函数和指数母函数,则

f ( x) ? ? e?s f e ( sx )ds
0

?

证明:将上式两边同乘以e-s并从0到∞积分得

?

?

0

e?s f ( sx )ds ? ?

? ?

0

n n n ? ? s x x ?s ?s n e a ds ? a e s ds ? ? n n ? n! n! 0 n ?0 n ?0

由分部积分法有

?

?

0

e?s s n ds ? n
?



?
证毕

?

0

e?s f e ( sx )ds ? ? an x n ? f ( x )
n ?0

母函数在排列、组合中的应用
从这节开始我们分别讨论母函数在某些问题 中的应用

母函数的应用
?

母函数有着广泛的应用,它不仅可 以用来处理排列组合的计数问题、 整数分拆问题,……而且还可以用 来证明(或推导)各种有用的组合恒 等式。

首先,我们考虑下列事实。令a,b,c表示三个
不同的物体。显然有三种方法从这三个不同的 物体中选取一个,或者选a,或者选b,或者选c 我们把这些可能的选取象征性 ? 地记为 a+b+c?

同样,从这三个不同的物体中选取两个有三种方
法,或者选取a和b,或者选取b和c,或者选取c和a。

我们把这些可能选取也象征性 地记为 ab+bc+ca??

而从这三个不同的物体中选取三个只有一种方法 ,把这种可能的选取象征性地记为 abc? ? ?

考虑多项式? (1+ax)(1+bx)(1+cx) =1+(a+b+c)x1+(ab+bc+ca)x2+(abc)x3

从这个多项式可以看出,以上所有的可能 选取方法都作为x的幂的系数被表示出来了。 特别是,xi的系数就是从三个不同 的物体中选取i个物体的方法的表示。这 并不是偶然的巧合。

下面,利用乘法规则和加法规则对上面的 多项式予以解释。

对物体a, 因子(1+ax)象征性地表示有 两种 选取方法: 不选取a,或选取a。 其中x仅是一个形式变量。 x0的系数表明不选取a, x1的系数表明a被选取。
对于(1+bx),(1+cx)可作类似的解释。这样, (1+ax)(1+bx)(1+cx)就表明:对三个不同的物体 a,b,c,其选择方法是,不选取a或选取a;不选 取b或选取b;不选取c或选取c。

于是这三个因子的乘积中x的幂指数就表示被选取 的物体的个数,而对应的系数则表明了所有可能的 选取方法。 因此,由普通母函数的定义知,三个因子 的乘积 (1+ax)(1+bx)(1+cx)就是选取物体a,b,c的所有不 同方法的普通母函数。

如果由于某种实际的需要,我们只对可能的 选取方法的个数感兴趣,而不是对不同的选取 方法感兴趣,则可令a=b=c=1。

于是有
(1+x) (1+x) (1+x)=(1+x)3=1+3x+3x2+x3

该多项式表明
只有一种方法 从三个物体中一个也不选 ? ? 3? ?? ? 从这三个物体中选取一 取,有三种方法 ? ? 3 ? ? ? 1? ? ?? ? ? ? ? 3? ? ? ? 从这三个物体中选取两 ? 3 ? ? 个,有三种方法 ? ? 2? ? ?? ? ? ? 3? ? 这三个物体中选取三 个。有一种方法 ? ?? ? ? 1? ? ? 3? ? ?? ? ? 个。一般说来,考虑多项式
?n? r (1 ? x )(1 ? x ) ? (1 ? x ) ? (1 ? x ) ? ? ? ?r? ?x r ?0 ? ?
n n

? ? 3? ? ?? ? ? 1? ? ? 0? ? ?? ? ?

对于这个多项式可作上面n=3时的同样 的解释。也就是说,从n个不同的物体中 选其r个物体,其方法数为(1+x)n的幂级 n? 数展开式中xr的系数 ? 。 ? ? ? ?
?r?

以上讨论的是从n个不同物体中选取r个物 体(每个物体至多选取一次)的简单情形。 当从n个不同的物体中,允许重复选取r个 物体时,上面的情况就可作如下的

推广。

由于因子(1+x)象征性地表示某一物体可 以不选,或者只选一次。 那么 , 类 似地,我 们 可以用因子 (1+x+x2) 象 征性地表示某一物体可以不选,或者选一次,或 者选两次。也就是说某一物体至多选两次。 同样 ,用因子 (1+x+x2+x3+…) 象征性地表示 某一物体可以不选,或者选一次,或者选两次, 或者选三次,……。 那么,(1+x+x2+x3+…)n的幂级数展开式中,xr 的系数ar就表示从n个不同的物体中允许重复地 选取r个物体的方式数。

下面,我们举例加以说明。

证明从n个不同的物体中允许重 复地选取r个物体的方式数为 ? n ? r ? 1? F(n,r)= ? ? r ? ?
? ?

例1

这个问题可以等价地叙述为:证明重集B={ n ? r ? 1? ? ∞〃b1,∞〃b2,…,∞〃bn}的r-组合数为 ? ? r ? ?。 ? ? 这就是定理第一讲已经证明过的结论。

下面用母函数法证明:设ar表示从n个不同 物体中允许重复选取r个物体的方式数,由 上面的分析可知,序列(a0,a1,…,ar,…)的普 通母函数为

? 1 ? f ( x) ? (1 ? x ? x ? ?) ? ? ? ?1? x ? ? ? n( ?n ? 1) ? ( ?n ? r ? 1) ?? (? x)r r! r ?0 ? n( n ? 1) ? ( n ? r ? 1) r ?? x r! r ?0 ? ? n ? r ? 1? r ? ?? ? r ? ?x r ?0 ? ? ? n ? r ? 1? ar ? F ( n, r ) ? ? ? r ? ? ? ?
2 n

n

证明从n个不同的物体中允许重复地选 取r个物体,但每个物体至少出现一次的方式 数为 ? r ? 1 ? ? ? ? ? n ? 1 ? ? ?

例2

证明:设ar表示从n个不同物体中允许重复
地选取r个物体,但每个物体至少出现一次 的方式数,则序列(a0,a1,…,ar,…)的普通母 函数为

f ( x) ? ( x ? x2 ? ? ? x r ?)n ? xn (1 ? x ? x2 ? ?)n
? ? n ? r ? 1? r 1 ? n? n ? ?x ? x ? ? x ?? ? ? r ? ?1? x ? r ?0 ? n

? n ? r ? 1? r ? n ? ? r ? 1 ? r ? ?? ? r ? ?x ? ? ? ? r ? n? ?x r ?0 ? r ?0 ? ? ? ? ? r ? 1? r ? ? r ? 1? r ? n? ? ? ?? ? n ? 1? ?x ? ? ? ? n ? 1? ?x (注意,当k ? n时, ?k? ? ? 0) r ?n ? r ?0 ? ? ? ? ?
?

故有

? r ? 1? ar ? ? ? n ? 1? ? ? ?

例3

求从n个不同的物体中允许重复地选取 r个物体,但每个物体出现偶数次的方式数。
? 解 :设 a2r 为所求的方式数,由于每个物体 出现偶数次。故可用因子 (1+x2+x4+…) 表示 某一物体可以不选,或选取两次,或选取4次 ,……。

因此序列(a0,a1,…,ar,…)的普通母函数为

? 1 ? f ( x) ? (1 ? x ? x ? ?) ? ? 2 ? ? 1? x ?
2 4 n

n

? n ? 2 ? n ? 1? 4 ? n ? 2 ? 6 ? n ? r ? 1? 2 r ? 1? ? ?1? ?x ? ? ? 2 ? ?x ? ? ? 3 ? ?x ? ? ? ? ? r ? ?x ? ? ? ? ? ? ? ? ? ? ? ? n ? r ? 1? 2 r ? ?? ? r ? ?x r ?0 ? ?

故有

? n ? r ? 1? a2 r ? ? ? r ? ? ? ?

例4

在一个书架上共有 16本书,其中4本是高等数 学,3本是普通物理,4本是数据结构,5本是离散 数学。求从中选取r本书的方式数,其中r=12。 ? 设ar是选取r本书的方式数。 由于高等数学最多只能选4本, 普通物理最多只能选3本, 数据结构最多只能选4本, 离散数学最多只能选5本。

f ( x) ? (1 ? x ? x2 ? x3 ? x4 )(1 ? x ? x2 ? x3 )(1 ? x ? x2 ? x3 ? x4 )

? (1 ? x ? x2 ? x3 ? x4 ? x5 )
? 1 ? 4 x ? 10x 2 ? 20x3 ? 34x 4 ? 50x5 ? 65x6 ? 76x7 ? 80x8 ? 76x9

? 65x10 ? 50x11 ? 34x12 ? 20x13 ? 4 x14 ? x16

取f(x)展开式中xr的系数即为所求的方式数。 当r=12,x12的系数为34,即 a12=34

Ex 2.3.
?

? ? ?

Determine the coefficient of x15 in f(x)=(x2+x3+x4+…)4. (x2+x3+x4+…)=x2(1+x+x2+…)=x2/(1-x) f(x)=(x2/(1-x))4=x8/(1-x)4 Hence the solution is the coefficient of x7 in (1-x)-4, which is C(-4, 7)(-1)7=C(10, 7).

指数母函数的 应用

以上,我们讨论了普通母函数在组合计数 问题中的应用。下面说明指数母函数在排 列计数问题中的一些应用。
n? r 我们已知道 (1 ? x ) n ? ? ? ? ? ? ?x
n r ?0

?r?

是从n个不同的物体中选取r个物体的组合 数ar所成的序列的普通母函数。 利用式(1.7)将上式变形有
r n n ? ? x n r (1 ? x ) ? ? ? ?r? ?x ? ? p( n, r ) r! r ?0 ? ? r ?0 n

这表明从n个不同的物体中选取r个物体的排列 数恰好是xr/r!的系数。
而(1+x)=(1+x1/1!)象征性地表示某一物体在 排列 中可以不选取,或者选取一次。 由此我们得到启发,某一物体在排列中可以不取 ,或取一次,或取两次,……,或取r次可用如 下形式表示:

x x 1? x ? ??? 2! r!

2

r

特别是 ,如果某物体的重复次数是∞时
,则上式的形式变为 x2 xr 1? x ? ??? ?? 2! r!

同样地,如果某一物体在排列中至少取两 次,至多取五次,则可用下面的形式表示
x 2 x3 x 4 x5 ? ? ? 2! 3! 4! 5!

下面,我们举例说明。

例5

证明从n个不同的物体中允许重复地选 取r个物体的排列数为nr
?? 证明:这个问题实质上是证明重集B={ ∞〃b1,∞〃b2,…,∞〃bn}的r?排列数为nr。 这就是第一讲已经证明过的结论。这里用母 函数的方法证明。

设ar为所求的排列数,由上面的分析知,序 列(a0,a1,…,ar,…)的指数母函数为

x x f e ( x ) ? (1 ? x ? ? ? ? ? ?) n 2! r!
r x ? ( e x ) n ? e nx ? ? n r r! r ?0 ?

2

r

故有

ar ? n

r

例7

求1,3,5,7,9五个数字组成r位数 的个数。其中要求7,9出现的次数为偶数。 其余数字的出现不加限制。
?解:这个问题等价于求重集B={ ∞〃1,∞〃3,∞〃5,∞〃7,∞〃9)}的r排列数 。其中要求7,9出现偶数次。

设所求的r-排列数为ar,则序列(a0,a1,…, ar,…)
的指数母函数为
x x x 2 f e ( x ) ? (1 ? ? ? ?) ? (1 ? x ? ? ?)3 2! 4! 2!
2 3 n x x x e ? x ? 1 ? x ? ? ? ? ? ( ?1) n ?? 2! 3! n! 2 3 n x x x ex ? 1 ? x ? ? ? ? ? ?? 2! 3! n!

2

4

2





e? x ? e x x2 x4 ? 1? ? ?? 2 2! 4!

所以有

?e ?e ? x 3 fe ( x) ? ? ? 2 ? ? (e ) ? ? 1 5x ? ( e ? 2e 3 x e x ) 4 ? 1 ? ? 5r r 3r r ? x r ? ? ? x ? 2? x ? ? ? ? ? ? 4 ? r ?0 r! r ! r ! r ?0 r ?0 ?
x ?x

2

r 1 ? r x ? ? (5 ? 2 ? 3r ? 1) 4 r ?0 r!



1 r r ar ? (5 ? 2 ? 3 ? 1) 4

例6 求1,2,3,4,5五个数字组成的r
位数的个数,其中要求1出现的次数与2出 现的次数的和必须是偶数。
? 解:设ar为所求的符合题意的个数。 由于1出现次数与2出现的次数的和为偶数, 这有两种情况: ?(1) 1出现的次数与2出现的次数都为偶数。 (2) 1出现的次数与2出现的次数都为奇数。

故由加法规则知,序列(a0,a1,…,ar)的指数母 函数为
2 x2 x4 x f e ( x ) ? (1 ? ? ? ?) 2 (1 ? x ? ? ?)3 2! 4! 2! 2 x3 x5 x ? ( x ? ? ? ?) 2 (1 ? x ? ? ?)3 3! 5! 2! 2 ? e x ? e? x ? 3x ? e x ? e? x ? 3 x ?? ? 2 ? ? ?e ? ? ? 2 ? ??e ? ? ? ?

1 ? n xn ? ? (5 ? 1) 2 n ?0 n!

故有

1 n ?1 a n ? (5 ) 2

Partition of integers

§4.4整数的拆分与?Ferrers?图
? 作为母函数应用的一个实例,下面讨论把 n个无区别的球放在一些无区别的盒子中的 问题.
? 把n个无区别的球分放在一些无区别的盒子中 ,究竟有多少种不同的放法? 无区别的盒子意味着,如果有四个相同的球,则 在第一个盒子中放入三个球, 第二个盒子中放入一个球与第一个盒子中放 入一个球,第二个盒子中放入三个球的放法是 一样的。

一个整数的拆分是把整数分拆为若干个正整数 部分。而这些部分的次序是无关紧要的。
?
?

? 如5=3+2和5=2+3被认为是同样的拆分法。显 然整数n的一个拆分等价于把n个无区别的球分 放在一些无区别的盒子中的一种方法。

正整数n的拆分种数记作P(n)。

例如,对于正整数n =1,2,3,4的拆分是
? n=1: 1=1 ∴P(1)=1 ? n=2: 2=2, 2=1+1 ∴P(2)=2 ? n=3: 3=3, 3=2+1,3=1+1+1 ∴P(3)=3 ? n=4: 4=4, 4=3+1,4=2+2, 4=2+1+1, 4=1+1+1+1 ∴P(4)=5

首先考虑恒等式
1 1? x ? x ? x ?? ? 1? x 1 2 4 6 1? x ? x ? x ?? ? 1 ? x2 1 3 6 9 1? x ? x ? x ?? ? 1 ? x3
2 3

于是有

1 2 2 4 3 6 ? ( 1 ? x ? x ? ? )( 1 ? x ? x ? ? )( 1 ? x ? x ? ?) 2 3 (1 ? x )(1 ? x ) (1 ? x )

? 1 ? x ? 2 x 2 ? 3x 3 ? 4 x 4 ? 5 x 5 ? 7 x 6 ? ?

在上式中可以看出 xn 的系数等于 n 拆分为 1 , 2 ,3的和的方法数。例如x3的系数是3,这表示整 数3拆分成1,2,3的和的方法数是3,即 3=3, 3=2+1, 3=1+1+1?? 又例如 x4 的系数是 4 ,它表明有 4 种方法将 4 拆分为1,2,3的和。即 ?4=3+1, 4=2+2, 4=2+1+1, 4=1+1+1+1??

这与上面的例子是吻合的。由此我们可以分析如下:
在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,分别表示数 字1没有被选,选一个1,选二个1,选三个1,…… 。

同样的,因子(1+x2+x4+x6+…)则表示2没有被选
,或选一个2,或选二个2,或选三个2,……。因子 (1+x3+x6+x9+…)则表示3没有被选,或选一个3, 或选二个3,或选三个3,……。这样,上面三个因 子的乘积的xn的系数就是n拆分为1,2,3的和的 方法数。

又如x6的系数是7,它表示6拆分为1,2,3的和 的方法有7种。 由此可见,函数1/(1-x)(1-x2)1-x3)的级数展开式 中,xn的系数就等于把n拆分为1,2,3的和的方 法数P(n)。

一般地,有下面的定理。

设a,b,c,…是大于0的正整数,则
1 a b c (1 ? x )(1 ? x )(1 ? x ) ?

的级数展开式中的xn的系数等于把正整数n拆分 成a,b,c,…的和的方法数P(n)。

证明:如前所述,只需注意
1 a 2a ? ( 1 ? x ? x ? ?) a b c (1 ? x )(1 ? x )(1 ? x ) ?
(1 ? x b ? x 2 b ? ?)(1 ? x c ? x 2 c ? ?)

如果项xn是由x3a,xb,x2c? ,…的乘积所组成,则

n ? a ? a ? a ? b ? c ? c ??
于是每当n可以拆分为a,b,c的和时,xn就 会出现。这就证明了定理的结论。

?定义4.7
?1. 用 Pk(n) 表 示 n 拆 分 成 1,2,… , k 的 允 许 重 复的方法数。 ?2.用Po(n)表示n拆分成奇整数的方法数。 ?3.用Pd(n)表示n拆分成不同的整数的方法数。 ?4.用Pt(n)表示n拆分成2的不同幂(即1,2,4, 8,…)的方法数。 ?

由上面的讨论和定理4.2即可得

推论1{P3(n)}的普通母函数是
1 (1 ? x )(1 ? x 2 )(1 ? x 3 )

推论2{Pk(n)}的普通母函数是 1
(1 ? x )(1 ? x ) ? (1 ? x )
2 k

推论3{P(n)}的普通母函数是
1 2 3 (1 ? x )(1 ? x )(1 ? x ) ?

在定理4.2中,令a,b,c,…是奇整数,我们又有

推论4{P0(n)}的普通母函数是
1 (1 ? x )(1 ? x 3 )(1 ? x 5 )(1 ? x 7 ) ?

定理4.3 设a,b,c,…都是大于0的正整数,则
(1 ? x )(1 ? x )(1 ? x ) ?
a b c

的级数展开式中xn项的系数就是把n拆分成 a,b,c,…的和,且a,b,c,…最多只出现一次 的方法数。

由定理4.3即可得

推论1{Pd(n)}的普通母函数是
(1 ? x )(1 ? x )(1 ? x )(1 ? x ) ?
2 3 4

推论2{Pi(n)}的普通母函数是
(1 ? x )(1 ? x )(1 ? x )(1 ? x ) ?
2 4 8

定理4.4(Euler)对于正整数n都有
p0 (n) ? pd (n)

证明:

4 1 ? x2 1 ? x ?1 ? x ? ,1 ? x 2 ? 1? x 1 ? x2 6 8 1 ? x 1 ? x 4 1 ? x3 ? , 1 ? x ? , 3 4 1? x 1? x

2 4 6 8 1 ? x 1 ? x 1 ? x 1 ? x ? (1 ? x )(1 ? x 2 )(1 ? x 3 )(1 ? x 4 ) ? ? ? ? ? ? 2 3 4 1? x 1? x 1? x 1? x

上式的左端正好是Pd(n)的普通母函数(由定理4.3 的推论1),而上式的右端,可将分子分母的所有 偶次幂约去就得到
1 (1 ? x )(1 ? x 3 )(1 ? x 5 )(1 ? x 7 ) ?

这正好是P0(n)的普通母函数(由推论4)。

∴Po(n)=Pd(n)
? 以上我们证明了把n拆分成奇整数的和的方式数 等于把n拆分成不相同的整数的和的方式数。

2.3 Partition of integers
? ?

?

?

?

?

p(x) is the number of partitions for x. For n, the number of 1’s is 0 or 1 or 2 or 3…. The power series is 1+x+x2+x3+x4+…. For n, the number of 2’s can be kept tracked by the power series 1+x2+x4+x6+x8+…. For n, the number of 3’s can be kept tracked by the power series 1+x3+x6+x9+x12+…. f(x)=(1+x+x2+x3+x4+…)(1+x2+x4+x6+x8+x10+…) (1+x3+x6+x9+…) …(1+x10+…) =1/(1-x)?1/(1-x2)? 1/(1-x3) ?…? 1/(1-x10) At last, we have the following series for p(n) by the coefficient of xn

? [1 /(1 ? x )]
i

? i ?1

下面我们验证当n=7的情况。 ? 7=7 7=7 ? 7=5+1+1 7=6+1 ? 7=3+3+1 7=5+2 ? 7=3+1+1+1+1 7=4+3 ? 7=1+1+1+1+1+1+1 7=4+2+1 ∴Po(7)=5 Pd(7)=5 于是Po(7)=Pd(7)。
?

?

定理4.5(Sylvester)
对正整数n,有 Pt(n)=1? ?

证明:我们知道,任何正整数都可唯一 地用一个二进制数来表示,而一个二进 制数又可唯一地表成2的幂的和。由此即 得结论。

?

如正整数39可以表成 39=100111=20+21+22+25

下面用另一种方法来证明定理4.5。

? 我们知道,序列(1,1,…,1)的普通母函数是
1 ? 1 ? x ? x2 ? x3 ? ? 1? x



1 ? x2 1 ? x4 2 ?1 ? x ? ,1 ? x ? 1? x 1 ? x2 8 16 1 ? x 1 ? x 8 1 ? x4 ? , 1 ? x ? ,?? 4 8 1? x 1? x
2 4 8 16 1 ? x 1 ? x 1 ? x 1 ? x ? (1 ? x )(1 ? x 2 )(1 ? x 4 )(1 ? x 8 ) ? ? ? ? ? ? 2 4 8 1? x 1? x 1? x 1? x

1 ? 1? x

而上式右端是Pt(n)的普通母函数(由定理4.3的推 论2)

? ? pt ( n ) x ? ?1 ? x
n n ?0 n ?0

?

?

n

? pt ( n ) ? 1

定理证毕。

? 因此,这个恒等式表明,任何正整数都可唯 一地拆分成形式为

k ? 10 , k ? 1,2,?; n ? 0,1,2,?
n

的不同部分。换句话说,任何整数的十 进制表示是唯一的。

例如,对于整数349有唯一的拆分:
? 349=9·100+4·101+3·102?

下面,我们讨论与整数拆分有着密切关系的? Ferrers? 图。

设n的一个拆分为
n=a1+a2+…+ak 并假设a1≥a2≥a3≥…≥ak≥1。

下面画一个图,这个图由一行行的点所组成。 在 第一行有a1个点, 第二行有a2个点, ……, 第k行有ak个点,称这图为? Ferrers图。

整数的拆分可以用一个Ferrers图来表示, 例如16=6+5+3+1+1的Ferrers? 图如图4-1

? 当给定 Ferrers 图后,可以将它的行与列对 换,这就得到另一个图。 显然,这个图也是一个 Ferrers 图。也就是说, 一个 Ferrers 图的行与列对换所得的图仍是一 个Ferrers图。

如图4-1作行与列的对换就得到图4-2。称图
4-2为图4? 1的共轭图。这个图表示整数16的 另一个拆分: ? 16=5+3+3+2+2+1?

由此可见,n的一个拆分对应唯一的一个 Ferrers图,反过来,一个Ferrers图又对应 一个 ? n的唯一拆分。 所以n的一个拆分同它的Ferrers图之间是 一一对应的。

定理4.7正整数n拆分成m项的和的方式
数等于n拆分成最大数为m的方式数
? 证明 :只须考虑 Ferrers 图和它的共轭图之间 的关系,本定理结论即可得证。 ? 例如,对n=24,如图4-3(书75页)

Ex 9.21
?

?
? ?

?

Find the number of ways an advertising agent can purchase n minutes if the time slots come in blocks of 30, 60, 120 seconds. Let 30 seconds represent one time unit. a+2b+4c=2n f(x)= (1+x+x2+x3+x4+…) (1+x2+x4+x6+x8+…)( 1+x4+x8+x12+…) =1/(1-x) ? 1/(1-x2) ? 1/(1-x4). The coefficient of x2n is the answer to the problem.

Examples
?

Ex 9.22. pd(n) is the number of partitions of a positive integer n into distinct summands.
? Pd(x)=(1+x)(1+x2)(1+x3)..…

?

Ex 9.23. po(n) is the number of partitions of a positive integer n into odd summands.
(1+x+x2+x3+x4+…) (1+x3+x6+x9+x12+…)( 1+x5+x10+x15+…)… ? Po(x)=1/(1-x) ? 1/(1-x3) ? 1/(1-x5) ? 1/(1-x7) ? ... ? Pd(x)= Po(x)
? Po(x)=

important series


搜索更多“acm 组合数学的艺术2”

网站地图

All rights reserved Powered by 伤城文章网 5xts.com

copyright ©right 2010-2021。
伤城文章网内容来自网络,如有侵犯请联系客服。zhit325@126.com