组合计数(未完待续

发布于 2020-08-08  200 次阅读


本笔记基于Anson的计数课件,加以解释和理解

前置知识:计数原理,容斥原理,鸽巢原理

本文不会纠结于证明一些公式,而更希望从组合意义解决一些问题,解释一些定理

一一对应

一一对应是一种计数时常用的一种技巧,若性质A的计数比较困难,性质B的计数比较容易,但性质A和性质B一一对应,则对A的计数可转换为对性质B的计数

下文中提到的一一对应皆指这种思想

常用公式

二项式定理:

\sum_{i=0}^{n} \binom{n}{i} a^i b^{n-i}

如何理解这个公式?先把有n项二项式相乘的形式展开,形如:(a+b)(a+b)...*(a+b)

我们可以把这个式子看成:从n个a中取出i个a,有\binom{n}{i}种方案,那么取出了i个a,即为a^i,那么取剩下的b会有b^{n-i}

如果了解深入的话,可以发现杨辉三角不仅是组合数递推的图形,而且是n个二项式乘积的各项系数

当然杨辉三角还有很多优美的性质

可重组合:

可重组合是描述一类这样的问题:有m个不同的小球和n个完全相同的盒子,每个盒子可以放任意数量的小球,也可以不放,问有多少种方案

\binom{n + m - 1}{m}

这个式子我太菜了结束不了(也许哪天我想通了我会更回来吧,但是可以证明这个允许重复的组合和从n+m-1个元素中取m个元素的不允许重复组合一一对应就可以证明

详见《组合数学》(第五版,卢开澄 卢华明编著,清华大学出版社)第一章第六节 问题1.6.1

第i种颜色的球有ai个,求排列的方案数

\frac{(\sum a_i)!}{\prod a_i!}

求从 (0,0) 到 (n,m),不碰到直线 y=x+b 的方案数。

解决组合计数的一些问题, 经常会用到的方式就是将问题转化到一个格子图上

比如从(0,0)走到(n,m)的方案数。从(0,0)走到(n,m)我们必然要走n+m步(相当于我们必然要走n次行m次列),那么我们的方案就是要在n+m步中选择n步走行或者m步走列

那么方案数是:

\binom{n+m}{n} = \binom{n+m}{m}

为什么这两式相等,我们可以发现在n+m步中选择n步走行或者m步走列这两个问题一一对应

我们将n+m步看成一条有n+m个格子的纸带,选择n步走行相当于在这个纸带上选择n个格子涂成黑色,那还剩下m个格子留成白色。选择m步走列相当于在纸带上选择m个涂成黑色,n个留成白色。这两种方式一一对应,所以上式成立

我们再来考虑求从 (0,0)(n,m),不碰到直线 y=x+b 的方案数。

建议自己在纸上画个图,这里懒得画

我们把被直线y=x+b的两部分中任意一部分沿这条直线折叠,那么只有(0,0)被翻到上面去或者(n,m)被翻到下面来两种情况,此时我们不需要走过截距b

方案数就是:

\binom{n+m}{n} - \binom{n+m}{b}

圆周排列

讲一排列排到一个圆周上,称为圆周排列问题

圆周排列与排列的不同之处在于圆周排列头尾相邻,比如四个元素a b c d的排列abcd dabc cdab bcda是四个不同的排列,但是把它们围着圆周排列,其实是一回事,属于同一个圆周排列。

此处建议画个图

那么记圆排列为Q(n,r),那么:

Q(n,r) = \frac{P(n,r)}{r}

斯特林数

本文的斯特林数全部通过递推得到

第一类斯特林数

第一类斯特林数是描述一类这样的问题:n个人坐m张圆桌的方案数

我们现在考虑递推式,假设你现在在一个有n-1个人的饭局上,摆了m-1张桌子

事情是这样的,此时新来了一个人,此时你需要为他安排一个座位

有两种方法解决这种问题,单独为他新开一桌和把他放到任意一桌中

为他单开一桌的方案显然直接由\left[ _{n - 1}^{m-1}\right]转移而来

如果把他放到已经开的桌子中


朴实沉毅