离散数学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$

生成排列和组合

生成排列

排列中的逆序

生成组合

生成r-组合