『组合数学基础』-白红宇

『组合数学基础』

阅读量：5144 次

发布时间：2019-06-13

本文共 4265 字，大约阅读时间需要 14 分钟。

基础知识

加法原理

若完成一件事情的方法有\(n\)类，其中第\(i\)类方法包括\(a_i\)种不同的方法，且这些方法互不重合，那么完成这件事共有\(\sum a_i\)中不同的方法。

乘法原理

若完成一件事情需要\(n\)个步骤，其中第\(i\)个步骤有\(a_i\)种不同的完成方法，且这些步骤互不干扰，那么完成这件事共有\(\prod a_i\)中不同的方法。

排列数

从\(n\)个不同元素中依次取出\(m\)个元素排成一列(在乎顺序)，产生的不同排列的数量为：

\[A_n^m=P_n^m=\frac{n!}{(n-m)!}=n*(n-1)*...*(n-m+1)\]

组合数

从\(n\)个不同元素中取出\(m\)个组成一个集合(不在乎顺序)，产生的不同集合数量为：

\[C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}=\frac{n*(n-1)*...*(n-m+1)}{m*(m-1)*...*1}\]

组合数的性质

\(1.\ C_n^m=C_n^{n-m}\)

证明：

由组合数的定义，对于从\(n\)个元素中取出\(m\)个构成的集合，剩余的元素也恰好构成了一个集合，两个集合一一对应，故产生的集合数量也相同，性质成立。

\(2.\ C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}\)

证明：

从\(n\)个不同元素取出\(m\)个数组成一个集合有两类方法：取\(n\)号元素，不取\(n\)号元素。取\(n\)号元素时，则在\(n-1\)个元素中还取了\(m-1\)个数，有\(C_{n-1}^{m-1}\)种取法。不取\(n\)号元素时，则在\(n-1\)个元素中取了\(m\)个元素，有\(C_{n-1}^m\)种取法，故性质成立。

\(3.\ \sum_{i=0}^nC_n^{i}=2^n\)

证明：

从\(n\)个元素中取出若干个元素组成一个集合，有\(n+1\)类方法，即分别取出\(0,1,2,...,n\)个元素，其方案数分别对应\(C_n^1,C_n^2,...,C_n^n\)。从另一方面看，每一个元素有取或不取两种选择，方案数为\(2^n\)，所以性质成立。

常见拓展知识

二项式定理

\[(a+b)^n=\sum_{k=0}^nC_n^ka^kb^{n-k}=\sum_{k=0}^nC_n^ka^{n-k}b^{k}\]

证明：

利用数学归纳法，当\(n=1\)时，\((a+b)^1=C_n^0a^0b^1+C_n^1a^1b^0=a+b\)成立。

若\(n=p\)时命题成立，则\(n=p+1\)时：

\[ (a+b)^{p+1}=(a+b)^p(a+b)=(a+b)\sum_{k=0}^pC_p^ka^kb^{p-k} \\=a\sum_{k=0}^pC_p^ka^kb^{p-k}+b\sum_{k=0}^pC_p^ka^kb^{p-k} \\=\sum_{k=0}^pC_p^ka^{k+1}b^{p-k}+\sum_{k=0}^pC_p^ka^kb^{p-k+1} \\=\sum_{k=1}^{p+1}C_p^{k-1}a^kb^{p-k+1}+\sum_{k=0}^pC_p^ka^kb^{p-k+1} \\=\sum_{k=0}^{p+1}(C_p^{k-1}+C_p^k)a^kb^{p-k+1} \\=\sum_{k=0}^{p+1}C_{p+1}^ka^kb^{p+1-k} \]

故原命题成立。

多重集排列数

多重集指含有重复元素的广义集合。设多重集\(S=\{n_1*a_1,n_2*a_2,...,n_k*a_k\}\)是由\(n_1\)个\(a_1\)，\(n_2\)个\(a_2\)，\(...\)，\(n_k\)个\(a_k\)组成的集合，则\(S\)的全排列个数为\[\frac{(\sum_{i=1}^k n)!}{\prod_{i=1}^k(n_i!)}\]

证明：

对于朴素全排列，显然有\((\sum_{i=1}^k n)!\)种方案，而在多重集的排列过程中，每个\(a_i\)出现了\(n_i\)次，在这\(n_i\)个位置间各个\(a_i\)可以互相调换位置，有\(n_i!\)中方案，故除去每一个\(n_i\)可以调换位置的重复方案即为总排列数。

多重集的组合数

设多重集\(S=\{n_1*a_1,n_2*a_2,...,n_k*a_k\}\)是由\(n_1\)个\(a_1\)，\(n_2\)个\(a_2\)，\(...\)，\(n_k\)个\(a_k\)组成的集合，对于\(r\leq n_i\ (\forall\ i \in [1,k])\)，从\(S\)中取出\(r\)个元素组成一个多重集，产生不同的多重集数量为\[C_{k+r-1}^{k-1}\]

证明：

该问题等价于统计如下集合的数量：\(\{x_1*a_1,x_2*a_2,...,x_k*a_k\}\)，其中\(\sum_{i=1}^kx_i=r\)。故原问题等价于多重集\(\{r*0,(k-1)*1\}\)的全排列数，即类似于插板法，每连续的一串\(0\)代表元素\(a_1\)的个数，使用\(k-1\)个\(1\)将\(r\)个\(0\)分成\(k\)部分。利用多重集的排列数公式可得方案数为\(C_{k+r-1}^{k-1}\)。

Lucas定理

\(Lucas\)定理：\(p\)为质数时，\(C_n^m\equiv C_{n\ mod\ p}^{m\ mod\ p}*C_{n/p}^{m/p}(mod\ p)\)。

证明：

预备和引理

\(1.\)费马小定理：\(p\)为质数时，有\(a\equiv a^p(mod\ p)\)。

\(2.\)二项式定理：\((a+b)^n=\sum_{k=0}^nC_n^{k}a^{k}b^{n-k}\)。

\(3.\)引理：\(p\)为质数时，有\((1+x)^p\equiv 1+x^p(mod\ p)\)。

证明：由费马小定理可得\((1+x)^p\equiv 1+x(mod\ p)\)，又因为\(x\equiv x^p(mod\ p)\)，则可得\((1+x)^p\equiv 1+x^p(mod\ p)\)。

\(4.\)引理：\((1+x)^n\)第\(m\)项的系数即为\(C_n^m\)。

证明：由二项式定理展开可得。

主体证明

对于\((1+n)^p\)，分解指数得： \[(1+x)^n\equiv (1+x)^{\lfloor \frac{n}{p} \rfloor p}(1+x)^{n\ mod\ p}(mod\ p)\] 利用引理\(3\)，可得： \[(1+x)^n\equiv(1+x^p)^{\lfloor \frac{n}{p} \rfloor}(1+x)^{n\ mod\ p}(mod\ p)\] 二项式定理展开，得： \[(1+x)^n\equiv\sum_{i=0}^{\lfloor \frac{n}{p} \rfloor}C_{\lfloor \frac{n}{p} \rfloor}^ix^{pi}*\sum_{j=0}^{n\ mod\ p}C_{n\ mod\ p}^jx^j\] 当且仅当\(pi+j=m\)时，\(x\)指数为\(m\)，故\(i=\lfloor \frac{p}{m} \rfloor,j=p \ mod\ m\)。而此时\(x^m\)的系数为\[C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{p}{m} \rfloor}*C_{p\ mod\ n}^{p\ mod\ m}\] 所以\(C_n^m\equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{p}{m} \rfloor}*C_{p\ mod\ n}^{p\ mod\ m}(mod\ p)\)，证毕。

Catalan数列

给定\(n\)个\(0\)和\(n\)个\(1\)，将他们排成长度为\(2n\)的序列，满足任意前缀中\(0\)的个数都不少于\(1\)的个数的排列的数量为\[Cat_n=\frac{C_{2n}^n}{n+1}\]

证明：

对于\(n\)个\(0\)和\(n\)个\(1\)任意排成的一个序列\(S\)，若\(S\)不满足要求，则必然存在一个最小位置\(2p+1\in[1,2n]\)，使得\(S[1,2p+1]\)中存在\(p\)个\(0\)，\(p+1\)个\(1\)，那么将\(S[2p+2,2n]\)这一部分取反，就可以得到由\(n-1\)个\(0\)和\(n+1\)个\(1\)排成的序列。

同理，对于一个\(n-1\)个\(0\)和\(n+1\)个\(1\)随意排成的一个序列\(S'\)，也必定存在一个最小的位置\(2p'+1\)，使得\(S'[1,2p'+1]\)中有\(p'\)个\(0\)，\(p'+1\)个\(1\)，那么将\(S'[2p'+2,2n]\)这一部分取反，也能得到由\(n\)个\(0\)和\(n\)个\(1\)排成的一个序列，并且存在前缀\(1\)比\(0\)多的位置。