当前位置:主页 > 航空 >计数问题(counting) >

计数问题(counting)

发布时间:2020-08-05作者: 阅读:(924)


高中的排列组合主要是“计数(counting, enumeration)”,延伸到高等数学上就是称为“计数组合(enuemrative combinatorics)”的数学分支。在这篇文章中我们介绍什幺是计数问题。

什幺是计数问题

计数问题说穿了就是“数数看有几个”,如此而已。所有的理论,所有的公式,都只是要帮助我们算得比较快一点。

用数学的语言来说,一个计数问题就是要数一个有限集合的元素个数。例如:“平面上一般位置的四条直线(一般位置即任三线不共点) 把平面分成几块?”亦即,$${S_4}$$ 表示平面上四条直线把平面分成的区域所成的集合,我们要数 $${|S_4|}$$。高中的排列组合大概都停在这个层次,即给一个特殊的情境,我们要算满足这个情境下的集合的元素个数,这个问题的答案是 $$11$$ 块。

但是以数学的观点来看,我们通常想要一劳永逸, 一次解决一整类问题:我们希望可以有一个函数 $${|{S}_1|}$$,$${|{S}_2|}$$,….都算出来。换句话说我们想要知道 $${f(n)} = {|{S}_{n}|}$$ 的公式,即平面上一般位置的 $${n}$$ 条直线可以把平面分成几块。

更抽象一点来说,设有由一堆集合 $${S_n}$$ 所构成的集合族,其中足码 $${n}$$ 跑遍某个集合 $${I}$$(通常是非负整数$$\mathbb{N}_0$$),所谓的计数问题就是要找出计数函数

$${f}:{I} \longrightarrow \mathbb{N}_0$$

其中 $${f(n)} = {|S_n|}$$,在这个例子中,

$$\displaystyle{f(n)} = \frac{n^2+n+2}{2},~~{n} \in \mathbb{N}_0$$

什幺是答案

什幺是一个计数问题的答案?这个问题乍看之下很好笑—不就是数出来就好了吗?非也,什幺样的结果可以称为“计数问题的答案”是值得讨论的。

1. 封闭型式的公式(closed form).

一个计数问题,能得到 $$f(n)$$ 的封闭形式毫无疑问当然是答案。比如上例,平面上一般位置的 $${n}$$ 条直线可以把平面分成 $$\displaystyle{f(n)} = \frac{n^2+n+2}{2}$$ 块。

2. 含有求和符号的公式.

但是计数问题并不总有封闭形式。比如,将 $${n}$$ 封不同的信装入 $${n}$$ 个已写好住址的信封,全部都装错的方法有几种?这是错列(derangement)问题,答案是

$$\displaystyle{f(n)} = n(1- \frac{1}{1!}+ \frac{1}{2!}-\frac{1}{3!} +…+(-1)^{n}\frac{1}{n!})$$

这个式子不能再化简了,我们也接受这是答案。

3. 递迴公式.

在错列问题中,$$f(n)$$ 事实上满足递迴关係式

$$f(n) = (n-1)(f(n-1)+f(n-2)),~~~f(0) = 1,f(1) = 0$$,

读者觉得这个算不算答案?说实在,要求 $$f(20)$$,用递迴式会比用求和式快,而且快许多!

4. 生成函数.

从这里已经跨入高等数学了。我们一样以错列为例,错列数列 $$f(0),f(1),f(2),f(3),f(4),….=1, 0, 1, 2, 9, 44,….$$ 的指数形生成函数(exponential generating function) 定义为

$$\displaystyle 1+0\cdot \frac{x}{1!}+1\cdot \frac{x^2}{2!}+2\cdot \frac{x^3}{3!}+9\cdot \frac{x^4}{4!}+44\cdot \frac{x^5}{5!}+…+f(n)\frac{x^n}{n!}+…$$

透过高等数学的技巧,可以得到这个无穷级数恰好是

$$\displaystyle{\frac{1}{e^{x}(1-x)}}$$

的泰勒展开式。因此 $$f(n)$$ 就是把 $$\frac{1}{e^{x}(1-x)}$$ 作泰勒展开式后,求出 $$x^n$$ 的係数再乘上 $${n!}$$

在高阶的计数组合中,数学家事实上是先想办法求出计数问题的生成函数。神奇的是,只要有生成函数,则要得到递迴公式(或是求和符号的公式, 或是封闭型式的公式) 都有一套公式化的方法!所以求生成函数变成计数组合的核心问题。在计数组合的研究中, 通常求得生成函数表示这个问题已经被解决了。按这个观点来看,生成函数也是答案。

5. 渐近公式.

顾名思义,渐近公式只是近似值,所以它不是答案—毕竟计数问题我们感兴趣的是正确值。但是,有时近似值传达的讯息也许更直接也更多。在错列问题中,显然有

 $$\displaystyle f(n) \sim \frac{n!}{e}$$

这个式子非常清楚地告诉我们 $$f(n)$$ 的大小。以这个角度来看,渐近公式反而最直接。研究并寻找渐近公式也是组合学的一个研究分支,称为分析组合学(analytic combinatorics)。

附带一提,追根究底的读者会问,那 $${n!}$$ 到底多大?这也可以从渐近公式 $${n!}\sim\sqrt{{2}\pi {n}}{(\frac{n}{e})}^n$$ 看出来(这称为Stirling 公式)。

综上所述,相信读者会对组合问题和其答案有一点初步的概念。下一篇文章中我们开始谈计数组合的几个基本原理。

上一篇: 下一篇:

相关阅读