离散数学III

排列与组合

基本计数原理

加法原理与乘法原理（略）

减法原理与除法原理

集合的排列

集合的线性排列：

定义：从n哥不同元素取出r个元素有序摆放，称n元素集合的r-排列
集合S的一个排列时某种顺序列出S的所有元素。（称为全排列）

定理：对于整数n和r，$r\leq n$，有$P(n,r)=\frac{n!}{(n-r)!}$

$P(n,r)=n*P(n-1,r-1)$

$P(n,r)=P(n-1,r)+r*P(n-1,r-1)$

循环排列：

定理：n个元素集合的循环r排列个数为：$\frac{P(n,r)}{r}=\frac{n!}{r(n-r)!}$
特别地，n元素的循环排列个数为$(n-1)!$

项链排列：

n个元素集合串起来循环r排列数为$\frac{P(n,r)}{2r}=\frac{n!}{2r(n-r)!}$

集合的组合

$C(n,r)=\frac{n!}{r!(n-r)!}$

$C(n,r)=C(n,n-r)$

$C(n,r)*C(n,k)=C(n,k)*C(n-k,r-k)$

$ \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} = 2^n $

多重集的排列

多重集：允许元素重复。例如$M=\{a,a,b,c,c,c\}=\{2a,1b,3c\}$

无限重复数

定理：令S是多重集，它有k种不同的元素，每个元素都有无限重复次数，那么，S的r-排列个数为$k^r$

有限重复数

定理：令S是多重集，它有k种不同的元素，每种元素的重复数分别为$n_1,n_2,...,n_k$，那么，S的排列数等于$\frac{n!}{n_1!n_2!...n_k!}$，其中$n=n_1+n_2+...+n_k$

定理：设$n=n_1+n_2+...+n_k$，将n个元素集合划分为做了标签的k个盒子$B_1,B_2,...,B_k$，其中$B_i$盒子含有$n_i$个元素，方法数为$\frac{n!}{n_1!...n_k!}$

多重集的组合

多重集S的一个r-组合是S 的子多重集。

定理：令S是多重集，它有k个不同的元素，每个元素都有无线重复次数，那么，S的r-组合个数为$\binom{r+k-1}{r}=\binom{r+k-1}{k-1}$

有元素约束问题？例：方程$x_1+x_2+x_3+x_4=20$的整数解的个数是多少？其中$x_1\geq 3,x_2\geq 1,x_3\geq 0,x_4\geq 5.$

n个元素	r排列问题（choose a list）	r组合问题（choose a set）
无重复	$P(n,r)$	$C(n,r)$
允许重复（无限）	$n^r$	$C(n+r-1,r)$

$n_1+...n_k=r$的非负整数解个数为$C(k+r-1,k-1)$
$n_1+...n_k=r$的正整数解个数为$C(r-1,k-1)$

有限概率

相对于微积分为基础的连续概率。

鸽巢原理

鸽巢原理的简单形式

略。

鸽巢原理的加强形式

定理：令$q_1,q_2,...q_n$为正整数。若将$q_1+q_2+...+q_n-n+1$个物体放进$n$个盒子内，那么：

• 或者第1个盒子至少含有$q_1$个物体，
• 或者第2个盒子至少含有$q_2$个物体，…
• 或者第n个盒子至少含有$q_n$个物体。

简单形式：当$q_1=q_2=...q_n=2$，有$q_1+q_2+...+q_n-n+1=n+1$

推论：设n和r都是正整数。如果$n(r-1)+1$个物体放入n个盒子，则至少有一个盒子含有r个或更多的物体。

平均原理：如果n个非负整数$m_1,m_2,...m_n$的平均数大于$r-1$，即$(m_1+m_2+...+m_n)/n>r-1$，则是稍有一个整数大于或等于$r$。

Ramsey定理

如果$m\geq 2,n\geq 2$是两个整数，则存在正整数$p$，使得$K_p\rightarrow K_m,K_n$

Ramsey数：Ramsey数$r(m,n)$是使$K_p\rightarrow K_m,K_n$成立的最小整数$p$

• $r(m,n)$一定存在（$m\geq 2,n\geq 2$是两个整数）
• $r(m,n)=r(n,m)$

平凡的Ramsey数：

• $r(2,n)=n$
• $r(m,2)=m$

推论：$r(m,n)\leq r(m-1,n)+r(m,n-1)$

Ramsey定理推广

Ramsey定理可推广到任意多种颜色的情况

$l$种颜色：如果$n_1,n_2,...,n_l$都是大于或等于2的整数，则一定存在正整数$p$，使得$K_p\rightarrow K_{n_1},K_{n_2},...K_{n_l}$，满足以上条件的最小整数$p$成为Ramsey数$r(n_1,n_2,...,n_l)$

例如：$K_{17}\rightarrow K_3,K_3,K_3$

Ramsey定理更一般形式

把点对（边）扩展至t个元素的子集（$t\geq 2$）：
给定整数$t\geq 2$及整数$q_1,q_2,...,q_k\geq t$，则存在一个整数$p$使得：如果将$p$元素集合种每一个$t$元素子集指定为$k$种颜色$c_1,c_2,...,c_k$中一种，那么：

• 或者存在$q_1$个元素，它的所有$t$自己被指定成颜色$c_1$，
• …
• 或者存在$q_k$个元素，它的所有$t$自己被指定成颜色$c_k$.

满足结论的最小整数$p$为Ramsey数$r_t(q_1,q_2,...,q_k)$

令$K_n^t$表示n个元素集合中所有t个元素的子集的集合。
给定整数$t\geq 2$及整数$q_1,q_2,...,q_k\geq t$，存在一个整数$p$，使得$K_p^t\rightarrow K_{q_1}^t,K_{q_2}^t,...,K_{q_k}^t$

生成排列和组合

生成排列

• 递归生成算法
• 邻位对换算法
• 多重集排列生成算法

递归生成算法

{1}的所有排列->{1,2}的所有排列->…{1,2,…,n}的所有排列

邻位对换算法

• 初始$123...n$

• while存在活动整数时，do

  • 求出最大的活动整数m
  • 交换m和其箭头指向的相邻整数的位置
  • 改变所有满足p>m的整数p的箭头方向

• 不存在活动整数时，算法结束

多重集排列生成算法

字典序算法：next_permutation

适用于多重集。

• 从右向左找第一队“升序”相邻元素：找到最大的$i$满足$A[i]<A[i+1]$。如果没有，说明已经是最大字典序，结束
• 在$i$的右侧找最后一个比$A[i]$大的数：找到最大的$j$，满足$A[j]>A[i]$。
• 交换$A[i]$与$A[j]$。
• 反转：将$A[i+1]...A[n]$反转为$A[n]...A[i+1]$，使其变为升序。

排列中的逆序

逆序：（前>后）
例：31524中几组逆序？有(3,1),(3,2),(5,2),(5,4)

一个排列和一个逆序列一一对应。

已知${1,2,...,8}$的一个排列的逆序列位53402110，确定此排列：

0 -> 8:8
1 -> 7:87
1 -> 6:867
2 -> 5:8657
0 -> 4:48657
4 -> 3:486537
3 -> 2:4862537
5 -> 1:48625137

生成组合

• 压缩序
• 反射Gray码

压缩序

二进制加法。

n元集合$S=\{x_{n-1},x_{n-2},...,x_0\}$的组合与长度为n的二进制数一一对应

• 初始：$a_{n-1}...a_1a_0=0...00$

• 当$a_{n-1}...a_1a_0\neq 1...11$时，执行以下操作：

  • 求出使得$a_j=0的最小整数$j$$
  • 用1替换$a_j$并用0替换每个$a_{j-1},...,a_0$

• 当$a_{n-1}...a_1a_0=1...11$时算法结束

反射Gray码

相邻的组合仅相差一个元素。

• 初始：$a_{n-1}...a_1a_0=0...00$

• 当$a_{n-1}...a_1a_0\neq 1...00$时，进行以下操作：

  • 计算$\sigma(a_{n-1}...a_1a_0)=a_{n-1}+...+a_1+a_0$
  • 如果$\sigma(a_{n-1}...a_1a_0)$是偶数，则改变$a_0$（01互换）
  • 否则，确定$j$，使得$a_j=1$且对于所有$i<j$，$a_i=0$，然后改变$a_{j+1}$

称为逐次法。

生成r组合

基于字典序的r子集生成算法。

// 初始化下标数组 a[1..r]，存储当前子集元素下标
for i ← 1 to r do
    a[i] ← i
end for

输出 a[1..r]

while true do
    // 从后往前找第一个可增大的位置 i
    i ← r
    while i ≥ 1 and a[i] = n - r + i do
        i ← i - 1
    end while

    // 无下一个子集，退出
    if i = 0 then
        break
    end if

    // 增大当前位
    a[i] ← a[i] + 1

    // 后续位依次递增
    for j ← i + 1 to r do
        a[j] ← a[j-1] + 1
    end for

    输出 a[1..r]
end while