排列组合
计数问题分类
| 计数对象 | 有序 | 无序 | |
|---|---|---|---|
| 都不重复 | 排列 | 组合 | 集合 |
| 允许重复 | 重集 |
集合的排列
圆排列
集合\(X\)中互不相同的元素\(x_1,\cdots,x_k\)按顺时针排成圆圈，称为\(X\)的k元圆排列，其数目为\(\frac{n!}{n}=n!\).
线性排列
又称为元排列。集合X的有序k元组(\(x_1,x_2,\cdots,x_k\))称为x的k元排列，元组中元素互不相同。含n个元素的集合中的k元排列数目记为\(P(n,k)\).
\(k>n\)时， \(P(n,k)=0\)；
\(k=n\)时，\(P(n,n)=n!\) （称为全排列）
排列可以表示为元组的形式，例如：\((3,1,2)\).全排列
全排列是线性排列在\(k=n\)时的特殊情况。
置换
置换（双射）：\(1,2,\dots ,n\)这\(n\)个元素的双射，如置换\(\pi:1\mapsto 4,\ 2\mapsto 3,\ 3\mapsto 2,\ 4\mapsto 1\).
置换是排列的另一种视角：
全排列可以视为置换（双射），例如：排列\((3,1,2)\)对应置换\(\pi:1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 2\).循环分解
长为\(l\)的循环\(C\coloneqq(i,\pi(i),\pi^2(i),\cdots,\pi^{l-1}(i))\).
置换\(\pi\)的循环分解式\(C_1,C_2\cdots,C_k\)，若\(\pi\)中长为\(l\)的循环有\(\lambda_l\)个\((1,2,\cdots,n)\)，则称\(\pi\)是\(1^{\lambda_1}2^{\lambda_2}\cdots n^{\lambda_n}\)型的。Cauchy公式
\(S_n\)中\(1^{\lambda_1}2^{\lambda_2}\cdots n^{\lambda_n}\)型的置换个数为
\[ \frac{n!}{\lambda_1!\lambda_2!\cdots\lambda_n!\cdot 1^{\lambda_1}2^{\lambda_2}\cdots n^{\lambda_n}} \]无符号第一类Stirling数
\[C(n,k)\coloneqq\text{\# \{恰有k个循环的n元置换\}} \]
规定：\(C(0,0)=1;\ C(n,0)=0,n\geq1;\ C(n,k)=0,k> n\).
满足递推关系
\[ C(n,k)=C(n-1,k-1)+(n-1)C(n-1,k) \quad n,k\geq1 \]
推论：\(\sum^n_{k=0}C(n,k)x^k=x(x+1)\cdots(x+n-1)\)
Pf . \(F_n(x)\coloneqq RHS=\)集合的组合
组合定义：集合\(X\)的（元素互不相同的）无序k元组(\(x_1,\cdots,x_k\))称为\(X\)的\(k\)元组合，记为
\[\binom{n}{k}\coloneqq\frac{(n)_k}{k!}=\frac{n!}{k!(n-k)!}\]
二项式系数\(\binom{n}{k}\)有如下性质：
\[\binom{n}{k}=\binom{n}{n-k}\]
\[k\binom{n}{k}=n\binom{n-1}{k-1}\]
\[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\]
\[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\cdots+\binom{k-1}{k-1} \tag{4}\]
\[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}+\cdots+\binom{n-k}{1}+\binom{n-k-1}{0} \tag{5}\]
\[\sum^n_{k=0}\binom{n}{k}=2^n\]
\[\sum^n_{k=0}(-1)^k\binom{n}{k}=0,\quad i.e.\sum_{k\%2=0}\binom{n}{k}=\sum_{k\%2=1}\binom{n}{k}=2^{n-1}\]
\[\sum^r_{k=0}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r},\quad m,n,r\in \mathbb{N} \tag{Vandermonde eq.}\]
Pf. 从m+n个人(男生m名，女生n名)中选择r人。
Specially, when \(m=n=r,\ \sum^n_{k=0}\binom{n}{k}^2=\binom{2n}{n}\), denoted as 中心二项数.
二项式定理\[(x+y)^n=\sum^n_{k=0}\binom{n}{k}x^ky^{n-k}\]重集的排列
集合的可重复排列
集合X的有序k元组\(x_{1},\dots,x_{k}\)称为X的k元可重复排列，其中\(x_{i}\in X\)可取相同值，记为\(x_{1},x_{2},\dots,x_{k}\).
e.g. \(X=\{a,b,c\}\)的2元字：\(aa,ab,ac,ba,bb,bc,ca,cb,cc\)
def. let \(X=\{ x_{1},\dots,x_{n} \}\),if \(x_{i}\) appears \(m_{i}\) times in a word (\(i=1,\dots,n\)),则称该字是\(x^{m_{1}}_{1}\cdots x^{m_{n}}_{n}\)型的。
th. let \(X=\{ x_{1},\dots,x_{n} \}\), given \(m_{1},\dots,m_{n}\in \mathbb{N}\text{ and }m_{1}+\cdots+m_{n}=m\), then X 上的\(x^{m_{1}}_{1}\cdots x^{m_{n}}_{n}\)型字个数为\[\frac{m!}{m_{1}!m_{2}!\cdots m_{n}!}\]
多项式系数\[\binom{m}{m_{1},m_{2},\dots,m_{n}}\coloneqq \frac{m!}{m_{1}!m_{2}!\cdots m_{n}!}\]
e.g. \(\mathrm{S}=\{ 3\cdot a,2\cdot b,4\cdot c \}\)的8元字
\(a^{3}b^2c^{3},a^{3}bc^4,\)重集的组合
集合的可重复组合
def. 集合X的无序k元组\(\{ x_{1},\dots ,x_{k} \}\)称为X上的k元可重复组合，其中\(x_{i\in X}\)可取重复值。
重数：\(x_{i}\)出现的次数，
\[\left(\!\!\binom{n}{k}\!\!\right)\coloneqq \#\{\text{n元集的k元重集}\}\]
th.
\[\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}\]
\[ \left(\!\!\binom{n}{k}\!\!\right)=\frac{(n)^k}{k!} \]
p.s. \(\binom{n}{k}=\frac{(n)_{k}}{k!}\)
cor. 方程\(x_{1}+\cdots+x_{n}=k\)的非负整数解个数为\(\binom{n+k-1}{k}\).不等式加松弛变量。变量带下界则构造新的变量使其非负。
def. 称\([n]\)的k元子集为\(l\)间隔的，如果其中任意两数之差\(>l\).
th. \[ \#\{ \text{[n]的l间隔的k元子集} \}=\binom{n-l(k-1)}{k} \]
e.g. \([8]\)的2间隔的3元子集：\(\{ 1,4,7 \},\{ 1,4,8 \},\{ 1,5,8 \},\{ 2,5,8 \}\)
二项式系数
\[ \forall n \in \mathbb{N} ,\binom{n}{k}\coloneqq
\begin{cases}
\frac{n!}{k!_(n-k)!}, 0\leq k\leq n, \\
0, k<0 \text{ or }k>n.
\end{cases}\]
esp:
\[ \binom{n}{1}=n \]
三角形数：\[ \binom{n}{2} = \frac{n(n-1)}{2}\]
四面体数：\[ \binom{n}{3}=\frac{n(n-1)(n-2)}{6} \]
性质
对称 \[ \binom{n}{k}= \binom{n}{n-k}\]
递推 （与杨辉三角有关）\[ \binom{n}{k}\binom{n-1}{k-1}+\binom{n-1}{k} \] \[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\cdots+\binom{k-1}{k-1} \] \[ \binom{n}{k}=\binom{n-1}{k}+\binom{n-2}{k-1}+\cdots+\binom{n-k+1}{0} \]
行和 \[ \sum_{k=0}^n\binom{n}{k}=2^n \]
行交错和 \[ \sum_{k=0}^n(-1)^k\binom{n}{k}=0\ (n\geq1) \]
行平方和 \[ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n} \]
格路
二项式系数的一种表示，可以为二项式系数提供一种组合解释。
从(0,0)到(k,n-k)，只走(1,0)或(0,1)方向的所有可能路径数目为\(\binom{n}{k}\)。因为到每一个点的前序点有2个二项式定理
\[n\in \mathbb{Z}^+,\forall x,y:\quad (x+y)^n=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k} \]
代数证明：数学归纳
cor. \[ n\in \mathbb{Z},\forall x:\quad (x+1)^n=\sum_{k=0}^n\binom{n}{k}x^k \]
可由此推出前面的部分性质:\(\sum_{k=0}^n\binom{n}{k}=2^n\),\(\sum_{k=0}^n(-1)^k\binom{n}{k}=0\ (n\geq1)\).二项式系数的正交性
单峰性
def. \((a_{n})_{n\geq_{0}}=a_{0},a_{1},\dots\)，使得\(a_{0}\leq a_{1}\leq\cdots\leq a_{m}\geq a_{m+1}\geq\cdots\)，则称数列具有单峰性。
二项式系数的单峰性
峰值在\(\left\lfloor \frac{n}{2} \right\rfloor\)取得
分奇偶项讨论，证明奇偶项各自的单峰性。\(n\) 为奇数时，相邻两项相等且均为峰值。
cor. 对固定的\(n\)，数列\(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\)的峰值为\(\binom{n}{\left\lfloor \frac{n}{2} \right\rfloor}=\binom{n}{\left\lceil \frac{n}{2} \right\rceil}\)对数凹性
def. 实数数列\((a_{n})_{n\geq_{0}}=a_{0},a_{1},\dots\)，若\(2a_{k}\geq a_{k-1}+a_{k+1}\ (\forall k\geq1)\)，则称数列是凹的，若\(a_{k}^2\geq a_{k-1}a_{k+1}\ (\forall k\geq 1)\)，则称数列是对数凹的。
th. 对于正数列，凹\(\implies\)对数凹\(\implies\)单峰