组合数学(Richard A. Brualdi)重要知识考点

组合数学（Richard A. Brualdi）重要知识考点整理 第一章 什么是组合

§1 排列组合

组合数学主要研究有限集合的计数，结构的存在性，以及性质。 几个计数原理

设A是有限多个元素的集合，用A表示A的元素个数

a) 分类与加法原理

A的一个分类，设A=A1?A2?…?Ar，Ai?Aj??，i?j，则称?Ai?1?i?r为

显然A=?Ai?1ri（加法原理）

b) 分步骤乘法原理

设A1、A2、…Ar是有限集

令B=A，称B1?A2?…?Ar??(a1,a2,a3，…，ar)|ai?Ai,1?i?r?（笛卡尔乘积）为A1，A2，…，Ar的积，显然B的每个元素(a1,a2,a3，…，ar)是有序数对，是按步骤确定的且B=?Ai?1ri（乘法原理）

【例1】A1,2?,A2??3,4?,则A1?A2??1,3?,(2,4),(1,4),(2,4) 1??【例2】求120的因数的个数

解：120=23?3?5，?n|120?n?21?32?53，其中0?a1?3,0?a2?1,0?a3?1 令A,2,3?,A2??0,1?,A3??0,1?，记120的因数的集合为B 1??0,1故|B|=|A1?A2?A3|=4?2?2=16.

【例3】有限集?a1 ，a2 ，a3 ，…，an?的一个有序列ai1 ，ai2 ，ai3 ，…,air称为

aaa??a1 ，a2 ，a3 ，…，an的一个r排列，其中ai?aj，i?j，所有r排列的个数记为

P(n,r)?n(n?1)……(n?r?1)，令P(n,n)?n!，则P(n,r)?c) 双射原理

n!，规定：0！=1.

(n?r)!B是两个集合，设A、对应f:A?B，对A中的每个元素a，有唯一的元素b?f(a)，

1

组合数学（Richard A. Brualdi）重要知识考点整理 a?D，与之对应，则称f为一个映射.

???映射：sr?r不是映射.

1. 如果?a1,a2?A(a1?a2),有f(a1)?f(a2)，则称f是单射.

显然，这时有A?B.

2. 如果?b?B,有a?A,使f(a)?b,则称f为满射. 3. 如果f既是单射又是满射，则称f为双射.这时A=B.

【例4】设A??a1 ，a2 ，a3 ，…，ar?，计算A的所有子集的个数（组合证明） 解：设B表示A的所有子集所成的子集（或者用幂集2表示） 设f：B??0,1???0,1???0,1??……?0,1?

A

?????????????r个1?t?r，t=0时表示?，1?i1?i2?…?it?r 令x?B，x={ai1 ，ai2 ，ai3 ，…,ait}，

则令f(x)?(00??????0) f(x)?(0???1i10???1i20???1it0???),如果x=0，易知f是双射.由双射原理和乘法原理得：B=2r 补充：例如A??1,2?，B???，{1}，{2}，{1,2}?

在上述映射下，有B={0,1}?{0,1}，f(?)?(0,0)，f({1})?(1,0)，f({2})?(0,1) 【例5】?a1 ，a2 ，a3 ，…，an?的r个元素所成的集合成为A的一个r组合

?n?P(n,r)所有这样的r组合的个数记为???，称之为二项式系数.

rr!??一般来讲r?0，特别的当r=0时，???1，今后，令???且x为任意实数. 注意！是没有意义的.

?n??0??x??r?x(x?1)???(x?r?1)，r?0r!122

组合数学（Richard A. Brualdi）重要知识考点整理 【例6】 1)

?n?n!?(n为正整数，n?r?0) ???r?r!(n?r)!?n??n??????(对称性) rn?r?????n??n?1??n?1????????? ?r??r??r?1??n??n??n?n++……???????2 ?0??1??n?2)

3)

4)

循环排列（圆排列）：从?a1 ，a2 ，a3 ，…，an?中取出r个元素作圆排列的个数为

n!P(n,r)n!=，当n?r时，?(n?1)!

nrr(n?r)!如：1,2,3三个元素作圆排列，一共有

3!?2种不同的排列方法. 3§3 重集

设a1 ，a2 ，a3 ，…，ak是个不同的元素，我们用?n1?a1 ，n2?a2 ，…，nk?ak?表示有n1个a1 ，n2个a2 ，…，nk个ak的集合称为一个重集，这里0?ni??(1?i?k) 注：ni=0表示ai不出现，ni=?表示ai取之不尽

这个集合的r元子集称为一个r组合，r元有序集合称为一个r排列.

【例1】?2?a1 ，3?a2 ，1?a3?的5组合有：?2?a1 ，3?a2?、?2?a1 ，2?a2 ，1?a3?、

3?a2 ，1?a3?3个；6排列共有?1?a1 ，

6!?60个.

2！?3！！?1§4 重集的排列

a)

???a1 ，??a2 ，…，??ak?的n排列的个数等同于?n?a1 ，n?a2 ，…，n?ak?的n排列的个数=kn

3

组合数学（Richard A. Brualdi）重要知识考点整理 b)

?n1?a1 ，n2?a2 ，…，nk?ak?的全排列（这里1?ni??）的个数为

k?n?n!，其中n??ni ???！n2！…nk！i?1?n1n2…nk?n1n??注：??称为多项式系数，这里只有当n?n1?n2?…?nk时才有意义.

nn…nk??12证明：要得到?n1?a1 ，n2?a2 ，…，nk?ak?一个n排列，我们只需从n个有序位置中选

?n?取n1个位置来放a1，共有??种方法，再在余下的n?n1个位置中选n2个位置来放a2，

?n1?共有??n?n1??种方法，继续下去，由乘法原理，n排列的个数等于

?n2??n?n1?n2?…?nk?1??n??n?n1??n?n1?n2??……???????nnknn3?1??2?????（n?n1?n2?…?nk?1)!(n?n1)!(n?n1?n2)!n!???……n1!(n?n1)!n2!(n?n1?n2)!n3!(n?n1?n2?n3)nk!(n?n1?n2?…?nk?1?nk)!?n!n1！n2！…nk！

c) 多重集合的组合

4

本文来源：https://www.bwwdw.com/article/om4.html