组合数学总结(终于写完了

排列组合

基本公式:

A_n^m=\frac{n!}{(n-m)!}\\ C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}\\

为了表示整洁,以下都使用 \left( \begin{array}\\ n\\ m \end{array} \right) 来表示 C_n^m

基本性质与证明

\left(\begin{array}\\n\\m\end{array} \right) =\frac{n!}{m!(n-m)!} =\frac{n!}{\left[n-(n-m)\right]!(n-m)!} =\left(\begin{array}\\n\\n-m\end{array}\right) \\ \\ \\ \\ \begin{align} \left(\begin{array}\\n-1\\m\end{array}\right)+\left(\begin{array}\\n-1\\m-1\end{array}\right) &=\frac{(n-1)!}{m!(n-1-m)!}+\frac{(n-1)!}{(m-1)!\left[n-1-(m+1)\right]}\\ &=\frac{(n-m)(n-1)!}{m!(n-m)!}+\frac{m(n-1)!}{m!(n-m)!}\\ &=\frac{(n-1)!}{m!(n-m)!}\times(n-m+n)\\ &=\frac{n!}{m!(n-m)!} =\left(\begin{array}\\n\\m\end{array}\right) \end{align}

不难发现 (x+y)^n 展开后的第 i 项的系数为 \left(\begin{array}\\n\\i\end{array}\right) ,次数为 n-ii

于是我们可以得出二项式定理:

(x+y)^n =\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)x^{n-k}y^{k} =\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)x^{k}y^{n-k}

由于该式的存在,组合数也被称为二次项系数

证明如下:

\begin{align} (x+y)^n &=x(x+y)^{n-1}+y(x+y)^{n-1}\\ &=x\times\displaystyle\sum_{i=0}^{n-1} \left(\begin{array}\\n-1\\i\end{array}\right)x^{n-1-i}y^i +y\times\displaystyle\sum_{j=0}^{n-1} \left(\begin{array}\\n-1\\j\end{array}\right)x^{n-1-j}y^j \\ &=x\times \left[\begin{array}\\x^{n-1}+\displaystyle\sum_{i=1}^{n-1} \left(\begin{array}\\n-1\\i\end{array}\right)x^{n-1-i}y^i\end{array}\right] +y\times\displaystyle\sum_{j=0}^{n-1} \left(\begin{array}\\n-1\\j\end{array}\right)x^{n-1-j}y^j \\ &=x^n+\displaystyle\sum_{i=1}^{n-1} \left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i+ \displaystyle\sum_{j=0}^{n-1} \left(\begin{array}\\n-1\\j\end{array}\right)x^{n-1-j}y^{j+1} \\ &\ 设\ j=i-1,代入得: \\ 原式 &=x^n+\displaystyle\sum_{i=1}^{n-1} \left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i+ \displaystyle\sum_{i=1}^{n} \left(\begin{array}\\n-1\\i-1\end{array}\right)x^{n-1-(i-1)}y^{(i-1)+1} \\ &=x^n+\displaystyle\sum_{i=1}^{n-1} \left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i+ \displaystyle\sum_{i=1}^{n} \left(\begin{array}\\n-1\\i-1\end{array}\right)x^{n-i}y^{i} \\ &=x^n+\displaystyle\sum_{i=1}^{n-1} \left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i +y^n+\displaystyle\sum_{i=1}^{n-1} \left(\begin{array}\\n-1\\i-1\end{array}\right)x^{n-i}y^{i} \\ &=x^n+y^n+\displaystyle\sum_{i=1}^{n-1} \left[\begin{array}\\ \left(\begin{array}\\n-1\\i \end{array}\right)+ \left(\begin{array}\\n-1\\i-1\end{array}\right) \end{array}\right]x^{n-i}y^i \\ &=x^n+y^n+\displaystyle\sum_{i=1}^{n-1} \left(\begin{array}\\n\\i\end{array}\right)x^{n-i}y^i \\ &=\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)x^{k}y^{n-k} \end{align}

所以,我们可以得出

\begin{align} &=\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)1^{k}1^{n-k}\\ &=(1+1)^n\\ &=2^n \end{align}

我们同时可以得出卢卡斯定理:

\left(\begin{array}\\n\\m\end{array}\right)\mod{p} =\left(\begin{array}\\\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\end{array}\right) \times\left(\begin{array}\\{n}\mod{p}\\{m}\mod{p}\end{array}\right) \mod{p}

证明如下:

\begin{align} &通过二项式定理可得:\\ (1+&x)^p=\displaystyle\sum_{i=0}^{p}\left(\begin{array}\\p\\i\end{array}\right){1^i}\times{x^i}\\ 当\ i&\not=0\ 且\ i\not=p\ 时:\\ \left(\begin{array}\\p\\i\end{array}\right)&\equiv\frac{p!}{i!(p-i)!}\equiv 0\ (mod{\ p})\\ 所以\ &(1+x)^p\equiv\displaystyle\sum_{i=0}^{p} \left(\begin{array}\\p\\i\end{array}\right){1^i}\times{x^i} \equiv(1-x^p)\ (mod\ {p}) \\ \\ 设\ a&=\lfloor\frac{n}{p}\rfloor,i={n}\ mod\ {p}\\ b&=\lfloor\frac{m}{p}\rfloor,j={m}\ mod\ {p}\\ 则\ n&=ap+i,m=bp+j\\ 由于&\left(\begin{array}\\ap+i\\bp+j\end{array}\right) =\left(\begin{array}\\n\\m\end{array}\right),\\ 表示&\ (1+x)^{i+ap}\ ——即\ (1+x)^n,\ 的\ x^{j+bp}\ ——即x^m项的系数\\ 而(1&+x)^{i+ap}\equiv(1+x)^i(1+x)^{ap}\equiv(i+x)^i(1+x^p)^a\ (mod\ p)\\ 所以&求(1+x)^{i+ap}\ 的\ x^{j+bp}项的系数\\ 相当&于求\ (1+x)^{i}\ 中\ x^{j}\ 项的系数,再乘以\ (1+x)^{ap}\ 中\ x^{bp}\ 项的系数\\ 而上&方两者用公式书写为:\left(\begin{array}\\a\\b\end{array}\right)\times \left(\begin{array}\\i\\j\end{array}\right)\\ 所以&得到 \left(\begin{array}\\n\\m\end{array}\right)= \left(\begin{array}\\a\\b\end{array}\right)\times \left(\begin{array}\\i\\j\end{array}\right)\\ 即:\ &\left(\begin{array}\\n\\m\end{array}\right)= \left(\begin{array}\\\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\end{array}\right)\times \left(\begin{array}\\n\ mod\ p\\m\ mod\ p\end{array}\right)\\ 证毕 \end{align}

还有一个不太常用的公式:

\displaystyle\sum_{i=0}^{n}{(-1)^i\times\left(\begin{array}\\n\\i\end{array}\right)}=0

证明如下:

通过二项式定理可得:\\ (-1+1)^n =\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)(-1)^{i}1^{n-i} =\displaystyle\sum_{i=0}^{n}{(-1)^i\times\left(\begin{array}\\n\\i\end{array}\right)}

同时这个式子也告诉我们:

\displaystyle\sum_{i}^{n}{[i\ mod\ 2=0]}\times\left(\begin{array}\\n\\i\end{array}\right) =\displaystyle\sum_{i}^{n}{[i\ mod\ 2=1]}\times\left(\begin{array}\\n\\i\end{array}\right)

-----------------------分----------------割-----------------线--------------------------

讲了那么多公式,我们再回头来看看具体怎么求 \left(\begin{array}\\n\\m\end{array}\right)

法一:

直接套公式 \frac{n!}{m!(n-m)!}

算一下复杂度:预处理阶乘要 O(n)

处理逆元要快速幂,复杂度 O(\log_2n)

总合 O(n+\log_{2}n)

法二:

利用 \begin{align} \left(\begin{array}\\n-1\\m\end{array}\right)+\left(\begin{array}\\n-1\\m-1\end{array}\right)=\left(\begin{array}\\n\\m\end{array}\right)\end{align}

显然复杂度为 O(n^2) ,设询问组数为 q

总复杂度为 O(qn^2)

总复杂度较高,但它可以再次复杂度内求出一定范围内的所有组合数,即单次询问只有 $O(1)$。

但如果要求我们求出一定范围内的所有数,而且 p 很小 n,m 很大呢?

这时候我们就要使用卢卡斯定理:

\left(\begin{array}\\n\\m\end{array}\right)\mod{p} =\left(\begin{array}\\\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\end{array}\right) \times\left(\begin{array}\\{n}\mod{p}\\{m}\mod{p}\end{array}\right) \mod{p}

如果 \lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor 还是很大怎么办呢?——递归即可解决。

所以我们只需要预处理出 p 以内的组合数,剩下的递推解决。

其中预处理复杂度 O(p) ,单次询问递推递推复杂度 O(\log_{p}{n})

总和 O(p+q\log_{p}n)

这是相当可观的复杂度了。

8 个赞

写的很好
必须支持

LaTex 炸了

1 个赞

LATEX炸了的刷新一下

1 个赞

哦,好了

1 个赞

我刚发…

??

你电脑太强了

太强了

\left(\begin{array}\n\i\end{array}\right)

刷新一下啊!!!

现在好了

我也推广一下:数论总结(例题未完成)

1 个赞

快说,你写了多久!!!

一个下午(还没写完
TAT

他问的是我,QWQ

只写了2天

耗时7h,终于写完了,捞一下

2 个赞

一点建议

模运算可以使用正体,如 a \bmod b $a \bmod b$

然后由于有换底公式,对数复杂度的底数可以不写。