离散数学-Counting

离散 2025-11-06

2025-11-06

Counting / 11.6

排列数（下降幂）：$\frac{n!}{(n-k)!}=n^{\underline{k}}$.

组合数（二项式系数）：$\frac{n!}{k!(n-k)!}=\binom{n}{k}$.

Property:

$\binom{n}{k}=\binom{n}{n-k}$
$(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$
$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$
$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$
使用 $\binom{n}{k}=\frac{n^{\underline{k}}}{k!}$，可以得到 $n\in \mathbb R$ 时的广义二项式级数定义

在 $|x|<1$ 时，有 $(1+x)^r=\sum_{k=0}^{+\infty}\binom{r}{k}x^k$
$\sum_{k=0}^{n}\binom{n}{k}k=2^{n-1}n$.

Proof：$\sum_{k=0}^{n}\binom{n}{k}k=\sum_{k=0}^{n}\binom{n-1}{k-1}n=2^{n-1}n$.
$\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$.

Proof：一方面，可以直接用数学归纳证明. 另一方面，考虑其组合意义：$n+m$ 个人中需要选出 $m+1$ 个人，左侧和式相当于在枚举最后一个未选中的人是哪个.
网格图 $(0,0)\to (n,m)$ 的最短路径数：$\binom{n+m}{n}$.

Proof：考虑递推式 $f_{n,m}=f_{n-1,m}+f_{n,m-1}$，形成了斜着的杨辉三角.

\[ C_n=\frac{1}{n+1}\binom{2n}{n} \]

问题引入：$(0,0)\to (n,n)$ 的，不经过 $x<y$ 部分的最短路径数为 $C_n$.

Catalan Number 同样是以下问题的答案：

$n$ 对括号的合法括号序列数（同理，$n$ 个节点的森林数）

Proof：将左括号看作 $x+1$，右括号看作 $y+1$，即回到路径计数问题.

这个问题也启发我们获得卡特兰数的递推式：考虑枚举第一个左括号对应的右括号位置，则得到 \[ C_n=\sum_{k=1}^n C_{k-1}C_{n-k} \]
$n+1$ 个叶节点的满二叉树（同理，$n+2$ 边形的三角剖分方案数）

Proof：考虑枚举左儿子的数量，得到上面的递推式，知其为卡特兰数.

对于 $n$ 个桶，$m$ 个球的模型，考虑将球放进桶的方案数.

当球桶都可区分，方案数显然为 $n^m$.
当桶可区分而球不可区分，不允许有空桶的方案数为 $\binom{m-1}{n-1}$.

Proof：相当于在 $m$ 个球之间插 $n-1$ 块板，即从 $m-1$ 个空档中选择 $n-1$ 个空挡插板.
当桶可区分而球不可区分，允许有空桶的方案数为 $\binom{m+n-1}{n-1}$.

Proof：多给 $m$ 个球，不允许有空桶地放完之后再从每个桶拿出来一个球即可.

若给定每个桶的最终球数 $m_i$，则有方案数 $\binom{m}{m_1,m_2,\dots,m_n}=\frac{m!}{\prod m_i!}$.

$n=3$ 时得到三项式系数 \[ (x+y+z)^m=\sum_{i,j}\binom{m}{i,j,m-i-j}x^iy^jz_{m-i-j} \]

考虑多重集意义下的加法，我们有 \[ \bigcup_{k\in[n]} A_k=\sum_{T\subseteq [n]} (-1)^{|T|-1}(\bigcap_{k\in T} A_k) \]

Proof：考虑每个 $x\in \bigcup A_k$ 在右式中的出现次数 $f_x$ \[ f_x=\sum_{T\subseteq [n],T\neq \varnothing} (-1)^{|T|-1}[x\in\bigcap_{k\in T} A_k] \] 注意到只要 $\exist k,x\notin A_k$，求和项就会变成 $0$. 于是令 $S$ 为 $A_1,\dots,A_n$ 中所有包含 $x$ 的集合，即 $S=\{i|x\in A_i\}$，于是有 \[ f_x=\sum_{T\subseteq S,T\neq \emptyset} (-1)^{|T|-1}=1-\sum_{T\subseteq S}(-1)^{|T|}=1 \] 这是因为 $\sum_{T\subseteq S}(-1)^{|T|}=\sum_{k}(-1)^k\sum_{T\subseteq S,|T|=k}1=\sum_{k}(-1)^k\binom{|S|}{k}=0$.

例 1. 对于 $S\subseteq[2n]$，$|S|\ge n+1$，则

$\exist i\neq j\in S$，$i,j$ coprime.

Proof：令第 $i$ 个 hole 为 $\{2i-1,2i\}$，则一定存在一个 hole 有两个元素同时在 $S$，于是互素.
$\exist i\neq j\in S$，$i|j$.

Proof：令第 $i$ 个 hole 为 $\{(2i-1)\times 2^k\}$，则一定存在一个 hole 有两个元素同时在 $S$，这两个元素的商为 $2$ 的幂次.

例 2. 对于序列 $a_1,\dots, a_n$. 对于 $r\times s<n$，有：要么存在长 $r+1$ 的非升子序列（即 LNIS $>r$），要么存在长 $s+1$ 的非降子序列（即 LNDS $>s$）.

Proof：令 $r_i$ 表示 $a_i$ 结尾的最长非降子序列，$s_i$ 表示 $a_i$ 结尾的最长非升子序列.

若 LNIS $\le r$ 且 LNDS $\le s$，则 $(r_i,s_i)\in [r]\times [s]$. 则考虑所有的 $(r_i,s_i)$，由鸽笼原理知一定存在 $i\neq j$ 使得 $(r_i,s_i)=(r_j,s_j)$.

不妨设 $i<j$. 由于 $r_i=r_j$ 所以 $a_i<a_j$. 由于 $s_i=s_j$ 所以 $a_i>a_j$. 矛盾.

例 3. Short-Integer Solution (SIS)：对于 $M\in \mathbb M_p^{n\times m}$，令在模 $p$ 意义下 $Mx=0$ 的一个 SIS 为满足 $x_i{-1,0,1} $ 的解. 证明：$M>n\log P$ 时，SIS 一定存在.

Proof：考虑 $\{0,1\}^{m}\to \mathbb Z_p^n$ 的映射，将 $x$ 映成 $M x$.

则由鸽笼原理知，存在 $x\neq x'\in \{0,1\}^m$ 使得 $Mx=Mx'$，于是 $M(x-x')=0$. 故 $x-x'$ 为一个 SIS.