组合数学练习
例1. 证明: 对于任意$n\ge 0$和$k\ge 1$, $x_1+x_2+...+x_k=n$的非负整数解的个数为$\binom{n+k-1}{k-1}$.
令$M(n,k)$为所求方程的解集, $B(a,k)$为集合$\{1,2,...,a\}$的所有大小为$k$的子集构成的集合. 下面我们通过构造一个$M(n,k)$与$B(n+k-1,k-1)$之间的双射来证明结论.
假设$S$为$B(n+k-1,k-1)$中任意一个集合. 我们可以将$S$按照升序排列: $S=\{s_1,s_2,...,s_{k-1}\}$, 其中$s_1 可以发现对于所有$1\le i\le k$, $x_i$都是非负整数, 并且$x_1+x_2+...+x_k=n$, 所以$\mu \in M(n,k)$, 也就是说$S\mapsto\mu$是$B(n+k-1,k-1)$到$M(n,k)$的函数. 下面我们来说明这个函数是双射. 考虑定义$S\mapsto \mu$的反函数. 假设$\mu$为$M(n,k)$中任意一个元素: $\mu=(x_1,x_2,...,x_{k})$, 对于每个$1\le i\le k-1$, 令$s_i=x_1+x_2+...+x_i+i$. 注意到 $$1\le s_1 < s_2 < ... < s_{k-1} \le n+k-1$$ 因此，$S=\{ s_1, s_2,...,s_{k-1}\} \in B_{n+k-1,k-1}$. 这样也就得到了$\mu \mapsto S$. 令$f: S\mapsto \mu, g: \mu \mapsto S$, 为了证明$f$和$g$是双射, 我们还必须验证以下条件： 验证如下： 令$S=\{s_1,...,s_{k-1}\} \in B(n+k-1,k-1), \mu =(x_1,...,x_{k}) \in M(n,k)$ $f(S)=(s_1-s_0-1,...,s_{k}-s_{k-1}-1)$ $g(f(S))=\{s_1-s_0-1+1,(s_1-s_0-1)+(s_2-s_1-1)+2,...,\sum\limits_{i=1}^k (s_{i}-s_{i-1}-1)+k\}=S$ $g(\mu)=\{x_1+1,...,\sum\limits_{i=1}^{k-1}x_i +k-1\}$ $f(g(\mu))=(x_1+1-1,(x_1+x_2+2)-(x_1+1)-1,...,(n+k)-(\sum\limits_{i=1}^{k-1}x_i +k-1)-1)=\mu$ 因此, 我们就证明了$f$和$g$是双射, 又由于$|B(n+k-1,k-1)|=\binom{n+k-1}{k-1}$, 故结论成立. 例2. 证明: 对于任意$n\ge 0$和$k\ge 1$, $x_1+x_2+...+x_k\le n$的非负整数解的个数为$\binom{n+k}{k}$. 令$M(n,k)$为所求方程的解集, $B(a,k)$为集合$\{1,2,...,a\}$的所有大小为$k$的子集构成的集合. 我们可以构造映射$f: M(n,k)\rightarrow B(n+k,k)$, $f$的定义如下: 对于$M(n,k)$中的一个解$\mu=(x_1,x_2,...,x_k)$, 令$f(\mu)=\{s_1,s_2,...,s_k\}$, 其中对于每个$1\le i\le k$, 满足$s_i=x_1+...+x_i+i$. 注意到 $$1\le s_1 < s_2 < ... < s_k \le n+k$$ 因此$f(\mu) \in B(n+k,k)$. 现在, 我们通过证明$f$是单射和满射来证明$f$是双射. 为了证明$f$是单射, 考虑$M(n,k)$中任意两个不同的解$\mu=(x_1,...,x_k)$, $\eta=(y_1,...,y_k)$, 满足$f(\mu)=f(\eta)$. 我们可以将$f(\mu)$按升序排列为: $\{s_1,...,s_k\}$, 其中$s_1<... 为了证明$f$是满射, 考虑$B(n+k,k)$中任意一个集合$S=\{s_1,...,s_k\}$, 其中$s_1<... 因此, 我们证明了$f$是双射. 由于$|B(n+k,k)|=\binom{n+k}{k}$, 故结论成立. 例3. 从$\{1,2,...,n\}$中选出$k$个数, 要求选出的数没有两个数相邻, 求满足条件的选法总数. 首先, 当$n <2k-1$时, 选法数显然是$0$, 下面我们考虑$n\ge 2k-1$的情况 令$M(n,k)$为所有满足条件的选法的集合，$B(a,k)$为集合$\{1,2,...,a\}$的所有大小为$k$的子集构成的集合. 假设$\mu =(x_1,x_2,...,x_k)$为一个选法, 那么必须要满足 $$1\le x_1 \le n, x_1+1< x_2\le n,x_2+1< x_3 \le n,...,x_{k-1}+1< x_k \le n$$ 所以我们可以构造映射$f: M(n,k)\rightarrow B(n-k+1,k)$如下: 对于任意$\mu =(x_1,x_2,...,x_k) \in M(n,k)$, 令$f(\mu)=\{s_1,s_2,...,s_k\}$, 其中对于每个$1\le i\le k$, 满足$s_i=x_i-i+1$, 注意到 $$1\le s_1 < s_2-1 < ... < s_k-k+1 \le n-k+1$$ 因此$f(\mu)\in B(n-k+1,k)$ 易证$f$是双射, 因此$n\ge 2k-1$时, 选法数为$\binom{n-k+1}{k}$. 例4. 圆桌上有$n$个座位, 将数字$1,...,k$依顺时针放到这些座位上(每个座位最多放一个数字), 要求$1$与$2$的座位不相邻, ..., $k-1$与$k$的座位不相邻, $k$与$1$的座位不相邻. 如果两种放置方式可以通过旋转从一种变为另一种, 则视为同一种放置方式, 求满足条件的放置方式总数. 当$n<2k$时, 答案为$0$, 下面考虑$n\ge 2k$时的答案. 假设$\mu =(x_1,x_2,...,x_k)$为一个选法, 由于旋转后相同视为同一种方案, 那么可以假设$a_1=1$. 同时可以得到 $$a_1+1 也就是 $$3\le a_2 < a_3-1 <... 那么容易构造出所有选法的集合到$B(n-1-k,k-1)$的双射, 因此答案为$\binom{n-1-k}{k-1}$. 例5. 正整数$n$可以分解为若干正整数之和, 我们并不关心相加的次序, 这种分解方式称为正整数$n$的划分. 令$g(n,k)$为$n$分为恰好$k$部分的划分的方案数. 求证: 对于任意$n\ge 2$和$0 令$S_{n,k}$为$n$的所有$k$部分的划分的集合, 构造映射$f: S_{n,k} \rightarrow (S_{n-1,k-1} \cup S_{n-k,k})$, 可以注意到$S_{n-1,k-1}$和$S_{n-k,k}$是不相交的. $f$的定义如下: 对于$S_{n,k}$中任意一个划分$n=n_1+n_2+...+n_k$, 将划分按升序排列, 即$n_1\le n_2\le ... \le n_k$, 令 $$f(n)=\begin{cases} n_2+n_3+...+n_k, & if \space n_1=1 \\ (n_1-1)+(n_2-1)+...+(n_k-1), & otherwise \end{cases}$$ 可以发现$n_1=1$时, $f(n)\in S_{n-1,k-1}$, 否则$f(n)\in S_{n-k,k}$. 下面我们证明$f$是双射. 先证$f$是单射, 考虑两个不同的划分$t,s \in S_{n,k}$, 满足$f(t)=f(s)$. 令$t=t_1+...+t_{k},s=s_1+...+s_{k}$, 均按升序排列, 那么分四种情况: