算术三角形蕴含着丰富的规律。比如:将每行的数分别相加可以得到倍增数列1,2,4,8,16,32,…,即2的各次幂。以1,8,28,56,…这行为例,我们是在将从8个元素中选出0个、1个、2个、3个……元素的方法个数相加,最后得到的是从8个元素中一次选取任意个数的元素共有多少种方法。这一数字为28,因为一般一个有n个元素的集合拥有2n个子集(subset)。
上面这一事实也可以直接推出,原因是一个n个元素集合的任意一个子集可以使用长度为n的二进制字符串来识别。方法如下:我们考虑一个集合,比如{a1,a2,…,an},则一个长度为n的二进制字符串定义了它的一个子集,因为字符串中的每个1表示相应的元素ai存在于我们的子集中。例如,假设n=4,字符串0111和0000分别代表{a2,a3,a4}和空集。由于二进制字符串的每个位置都有两种取值选择,因此共有2n个这样的字符串,一个n元素集合便含有2n个子集。
卡特兰数
这种数有种最简单的图形表达,是用n段上斜线段和n段下斜线段能画出多少组不同的“山脉”(如图3)。
图3 用3段上斜线段和3段下斜线段,共有5种山脉形态