Skip to content

第二章 排列与组合

2.1 四个基本的计数原理

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

2.2 集合的排列

线性排列

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

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

循环排列

Anrr=n!r(nr)!\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!(nr)!\displaystyle{ { n \choose r } = \frac{ {n !} }{ {r !} {\left( n - r \right) !} } }

帕斯卡公示

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

(nk)=(n1k)+(n1k1)\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={2a,1b,3c}\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+k1r)=(r+k1k1)\displaystyle{ { r + k - 1 \choose r } = { r + k - 1 \choose k - 1 } }

2.6 有限概率