Skip to content
Notes

第二章 排列与组合

2.1 四个基本的计数原理

  • 加法
  • 减法
  • 乘法
  • 除法

2.2 集合的排列

线性排列

一个 n\displaystyle{ n } 元素集合 S\displaystyle{ S } 的 r\displaystyle{ r } 排列为 n\displaystyle{ n } 个元素中的 r\displaystyle{ r } 个元素的有序放置

Anr=n!(n−r)!\displaystyle{ A _{ n } ^{ r } = \frac{ {n !} }{ {\left( n - r \right) !} } }

循环排列

Anrr=n!r(n−r)!\displaystyle{ \frac{ A _{ n } ^{ r } }{ r } = \frac{ {n !} }{ r {\left( n - r \right) !} } }

2.3 集合的组合

从 n\displaystyle{ n } 元集合 S\displaystyle{ S } 中选出 r\displaystyle{ r } 个元素构成一个子集

(nr)=n!r!(n−r)!\displaystyle{ { n \choose r } = \frac{ {n !} }{ {r !} {\left( n - r \right) !} } }

帕斯卡公示

对于所有满足 1⩽k⩽n−1\displaystyle{ 1 \leqslant k \leqslant n - 1 } 的整数 n\displaystyle{ n } 和 k\displaystyle{ k }

(nk)=(n−1k)+(n−1k−1)\displaystyle{ { n \choose k } = { n - 1 \choose k } + { n - 1 \choose k - 1 } }

有性质

∑i=0n(ni)=2n\displaystyle{ \sum _{ i = 0 } ^{ n } { n \choose i } = 2 ^{ n } }

2.4 多重集合的排列

如果 S\displaystyle{ S } 是一个多重集合，那么 S\displaystyle{ S } 的一个 r\displaystyle{ r } 排列是 S\displaystyle{ S } 中 r\displaystyle{ r } 个对象的一个有序放置。如果 S\displaystyle{ S } 的对象总数是 n\displaystyle{ n } (重复对象计数在内)，那么 S\displaystyle{ S } 的 n\displaystyle{ n } 排列也称为 S\displaystyle{ S } 的排列。

如果 S={2⋅a,1⋅b,3⋅c}\displaystyle{ S = \left\lbrace 2 \cdot a , 1 \cdot b , 3 \cdot c \right\rbrace }，则 acbc,cbcc\displaystyle{ a c b c , c b c c } 都是 4 排列。

定理 2.4.1

设 S\displaystyle{ S } 是有 k\displaystyle{ k } 种不同类型对象的多重集合，每一个元素都有无限重复数。那么，S\displaystyle{ S } 的 r\displaystyle{ r } 排列的数目是 kr\displaystyle{ k ^{ r } }

定理 2.4.2

设 S\displaystyle{ S } 是多重集合，它有 k\displaystyle{ k } 种不同类型的对象，且每一种类型的有限重复数分别是 n1,n2,…,nk\displaystyle{ n _{ 1 } , n _{ 2 } , \ldots , n _{ k } } 。 设 S\displaystyle{ S } 的大小为 n=n1+n2+…+nk\displaystyle{ n = n _{ 1 } + n _{ 2 } + \ldots + n _{ k } } 。 则 S\displaystyle{ S } 的排列数目等于

n!n1!n2!…nk!\displaystyle{ \frac{ {n !} }{ {n _{ 1 } !} {n _{ 2 } !} \ldots {n _{ k } !} } }

定理 2.4.3

将上述变为 k\displaystyle{ k } 个标签的盒子，每个盒子有 ni\displaystyle{ n _{ i } } 个对象，n=∑i=1kni\displaystyle{ n = \sum _{ i = 1 } ^{ k } n _{ i } }，如果盒子没有标签，且 n1=n2=…=nk\displaystyle{ n _{ 1 } = n _{ 2 } = \ldots = n _{ k } }，则划分数等于

n!k!n1!n2!…nk!\displaystyle{ \frac{ {n !} }{ {k !} {n _{ 1 } !} {n _{ 2 } !} \ldots {n _{ k } !} } }

2.5 多重集合的组合

定理 2.5.1

x1,…xk\displaystyle{ x _{ 1 } , \ldots x _{ k } } 为非负整数，且 x1+…+xk=r\displaystyle{ x _{ 1 } + \ldots + x _{ k } = r }，则满足这个方程的解的个数有

(r+k−1r)=(r+k−1k−1)\displaystyle{ { r + k - 1 \choose r } = { r + k - 1 \choose k - 1 } }

2.6 有限概率