包含排除原理与发生函数方法

数学建模

包含排除原理与发生函数方法

对于组合性质的事物，常常遇到计算个数的问题，即计算问题。我们通过举一些例子说明如何应用包含排除原理与发生函数方法去进行计数。

一 包含排除原理 定理引出

让我们从一个简单的例子谈起：

数学系三年级甲班共有学生30名。在学完英语的基础上，本学期又开了日、德、法三门外语以供选修。班上选修日语的有15人，选修德、法语的各14人，同时选修日、德语的有7人，同时选修日、法语和法、德语的各有6人，三门全选的仅有3人。问此班中本学期选外语的学生有几人？

分析 将此班中每个学生看作一个点，用E1、E2、E3分别表示选修日、德、法各种外语的学生集合。以n(E)表示集合E中所包含的点的个数，于是按题设即有：

n(E1),n(E2) n(E3) 14,n(E1E2) 7,n(E1E3) n(E2E3) 6,n(E1E2E3) 3.

为了求出未选外语的学生人数，我们只需求出选了外语（即至少选一门外语）的学生人数。为此我们先将选各门外语的人数统统加起来，即：

n(E1) n(E2) n(E3) 15 14 14 43.

但这样凡是同时选修任何两门外语的人数均被计算了两次。这样自然就想到了要“排除”，即减去：

n(E1E2) n(E1E3) n(E2E3) 7 6 6 19.

到此为止，我们可以知道三门外语全选的3人在第一次包含中各被计算了3次，在第一次排除中各被减掉了一次，因此，要得到所求人数，就必须把他们再“包含”进来，这样我们得到：

数学建模

43 19 3 27.

这个27就是我们要求的选了外语的学生总数。于是，30-27=3（人），就是说，班上只有3人未选外语。

正是这种“包含”，包含多了再“排除”，排除多了再“包含”，用“包含”和“排除”反复交替来达到求得准确答案的计数方法，大约早在三个世纪之前，就已经被人们发现，并将其总结为一般的原理，即为包含排除原理。下面我们看看什么是包含排除原理。

定理1（包含排除原理 Principle of inclusion and exclusion）设有N个事物，其中有些事物具有性质

p,p,...,p

1

2

s

中的某些性质。令Ni表示具有

p

i

性质的

事物个数，Nij表示兼有

p

i

及

p

j

性质的事物个数，此处i j(1 i,j s).由此定

义，Nij及Nji应代表同一数值，并且凡兼具性质

p

i

，

p

j

性质的事物也认为具有

p

i

或

p

ik

j

。一般地，设

Nii

12

...

具有性质

pi,pi,...pi

1

2

的事物个数。那么，N中不具有任何性质

k

的事物的个数即等于：

N

N Ni Nij 0

i 1

i j

4

i j k

N

k

...( 1)ijk

i1 i2. ...ik

Nii

12

...

ik

... ( 1)sN12...S.

定理直观分析

在给出定理证明之前，让我们先来对公式的结构作些直观的分析。为了求出N个事物中不具任何性质的事物个数，当然只要从N中减去至少具有一个性质的事物的个数就可以了。而至少具有一个性质的事物的个数S就是：

S Ni Nij

i 1

i j

i j k

N

i

k 1

... ( 1)ijk

i1i2.ik

...

Nii

12

...

ik

... ( 1)s 1N12...S.

这是因为在第一个和式 Ni中确实把具有任何一种性质事物都计算过了，但却把具有两种或两种以上性质的事物各多算了若干次。例如，对同时兼具性质

p,p

1

2

的事物，在N1,N2中都各被计数一次，所以就出现了重复计数现象，第

数学建模

二项 Nij用意在于把重复计数的对象个数再排除出去。但这样一来，又会出

i j

现排除过多的现象，虽然在和式 Ni Nij中恰好具有一种或两种性质的事

i

i j

物都正确的计数了一次，但对于譬如具有

p,p

1

2

性质的一个事物，它在 Ni中

i

被计数了三次，多算了两次，而在 Nij中又被排除了3次，结果是一次也没有保留，所以又须靠 Nijk中的一项中补还它一次，仿此类推，可见S等式的右端 Ni Nij Nijk ...的各和式正好起着盈亏相抵的作用。

定理的严格证明

假设N个事物中的任一特定事物T刚好只具有k个性质所以在和式p,p,...,p(1 k s).则此事物在N1,N2,...,Nk中都被计数一次，

1

2

k

k

中显然一共被计数了 k次。同理，在和式 Nij中它显然被计数了 Ni

ii j 1 k 1

k(k 1) 2 2

i

i j

次。依此类推，可见它在下列总和

S Ni Nij ... ( 1)s 1N12...S.中一共被计数的次数是

k k k 1 k k

... ( 1) 1 (1 1) 1(次)，

1 2 k

这表明具有性质的每一个事物在S中都被计算一次，可见S即等于具有任何性质的事物的总数。因此N0 N S，便是不具有任何性质的事物的总数。定理证毕。

包含排除原理的应用

例1 试确定不定方程x1 x2 x3 x4 20,满足要求1 x1 6,0 x2 7,

4 x3 8和2 x4 6的整数解的组数。

分析 首先注意，方程x1 x2 x3 x4 r（r为非负整数）的非负整数解的

数学建模

组数就是n种相异事物中允许重复（重复次数不限）取r个的组合方法数，为

n r 1 。令 r

z x 1,z x,z x 4,z x

1

1

2

2

3

3

4

4

2.则问题化为求方程

z z z z

1

2

3

4

20 7 13的满足条件

0 z1 5,0 z2 7,0 z3 4,0 z4 4的整数解组数。 将此方程的所有非负整数解看作集合 ，则由以上的提示知

4 13 1 16

N n( ) 560

13 3

（记号n( )表示 中所含元素的个数）。对任何一组非负整数解

(z1,z2,z3,z4以性质)

p

1

表示z1 6,

p

2

表示z2 8,

4

p

3

表示z3 5以及

p

4

表示

z

4

则按定理1，所求解组数就是N0 N Ni Nij 5。

i 1

i j

'

i j k

N

ijk

N1234,

作替换z z1 6,易见N

i1...ik

(n k)!.就是方程

z

'

7 3

z2 z3 z4 13 6 7的非负整数解组数。因而N1 120，余

3

皆类似，不难求得

N

N

2

56,N3 N4 165;N13 N14 10,N23 N24 1,N34 20,其它的 及所有的Nijk和N1234统统为0.代入得

ij

N

560 (120 56 2 165) (2 10 2 1 20) 96.

例2 假定有n对夫妇参加某舞会。约定每一男人必须邀请除自己妻子以外的某一女人伴舞。问所有可能的舞伴方法数共多少种？

分析 考虑由1，2，...n这n个数作成的排列，对于这排列中的第k个位置，称为是数k的自身位置；使得每个数都不在其自身位置的排列称为错排序列。显

数学建模

然，所求的舞伴方法数就是长度为n的错排序列的总数。将这总数记作Dn，则

D

以

n