排列组合

基本计数原理

• 加法原理: 分类
• 乘法原理: 分步
• 减法原理: 互补
• 除法原理: 等分

排列组合

\(n\) 元素集合的 \(r\) 排列:

• 从 \(n\) 个不同元素中取出 \(r\) 个元素有序摆放
• 排列数记为 \(P(n,r)\)

循环排列: \(n\) 元素集合的循环 \(r\) 排列个数为 \(\frac{P(n,r)}{r}\)

项链排列: 从 \(n\) 颗不同颜色的珠子中选 \(r\) 颗串成项链的方法数为 \(\frac{P(n,r)}{2r}\)

\(n\) 元素集合的 \(r\) 组合:

• \(n\) 元素集 \(S\) 选出 \(r\) 个元素
• 组合数记为 \(\binom{n}{r}\)
• 帕斯卡公式 \(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\)

多重集

多重集和一般意义上的集合不一样，允许元素重复，例如 \(M=\{a, a, b, c, c, c\}\) ，也可以写为 \(M=\{2\cdot a, 1\cdot b, 3 \cdot c\}\)

多重集的排列

无限重复数: 令 \(S\) 是有 \(k\) 种不同元素的多重集，每种元素都有无限个，那么 \(S\) 的 \(r\) 排列个数为 \(k^r\)

有限重复数的全排列: \(S\) 是多重集 \(\{n_1\cdot a_1, n_2\cdot a_2, \cdots, n_k \cdot a_k\}\)，\(S\) 的排列数等于 \(\frac{n!}{n_1!n_2! \cdots n_k!}\) ，其中 \(n = n_1 + n_2 + \cdots + n_k\) 。证明的方法是先为 \(a_1\) 选 \(n_1\) 个位置，再为 \(a_2\) 选，依此类推

有限重复数的 \(r\) 排列: 要利用生成函数或容斥原理来求解

多重集组合

例子: 假设有 \(k=4\) 个数字，每个数字可以用无数次，其 \(r=5\) 的组合数为多少？

1. 有重组合 \(\rightarrow\) 无重组合
2. 比如 \(\{2,3,3,3,4\} \rightarrow \{2+0,3+1,3+2,3+3,4+4\} = \{2,4,5,6,8\}\)
3. \(\{\infty \cdot 1,\infty \cdot 2,\infty \cdot 3,\infty \cdot 4\}\) 的 \(5\) 组合化为 \(\{1,2, \cdots, 8\}\) 的无重 \(5\) 组合
4. 隔板法
5. 相当于将 \(r\) 个相同的元素分成 \(k\) 个不同的区域，每个区域代表一种数字；在 \(r\) 个元素间插入 \(k-1\) 个隔板
6. 有 \(\binom{r+k-1}{k-1}\) 种
7. 方程的解
8. 等价于方程 \(x_1 + x_2 + \cdots + x_k = r\) 的非负整数解的个数

定理 令 \(S\) 是多重集，有 \(k\) 个不同的元素，每个元素都有无限重复次数，那么 \(S\) 的 \(r\) 组合个数为

\[ \binom{r + k - 1}{r} \]

不相邻选数问题: 从 \(\{1, 2, \cdots,n\}\) 中取出 \(r\) 个不相邻的数，这样的组合有多少种？

_ 1 _ 1 _ 1 _ 1 _

• 假设没选中的数有 \(x_0, x_1, \cdots, x_r\) 个，则 \(x_0 + x_1 + \cdots + x_r = n-r\) 且 \(x_1, \cdots, x_{r-1} \geqslant 1\)
• 则方程的解有 \(\binom{n-r+1}{r}\) 种