组合数学(Richard-A.-Brualdi)重要知识考点
第一章 什么是组合
§1 排列组合
组合数学主要研究有限集合的计数，结构的存在性，以及性质。 几个计数原理
设A是有限多个元素的集合，用A表示A的元素个数
a) 分类与加法原理
设A=A1显然A=A2…Ar，AiAj??，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) 双射原理
设A、对应f:A?B，对A中的每个元素a，有唯一的元素b?f(a)，B是两个集合，
n!，规定：0！=1.
(n?r)!a?D，与之对应，则称f为一个映射.
1 / 4
组合数学(Richard-A.-Brualdi)重要知识考点
?映射：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?
r个A
1?i1?i2?…?it?r 令x?B，x={ai1 ，ai2 ，ai3 ，…,ait}，1?t?r，t=0时表示?，f(x)?(0???1i10???1i20???1it0???),如果x=0，则令f(x)?(00??????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 / 4
组合数学(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个元素作圆排列的个数为
P(n,r)n!n!=，当n?r时，?(n?1)! rr(n?r)!n如：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 / 4