天才一秒记住【做客中文网】地址：https://www.zk01.net
这一数字为28，因为一般一个有n个元素的集合拥有2n个子集。
上面这一事实也可以直接推出，原因是一个n个元素集合的任意一个子集可以使用长度为n的二进制字符串来识别。
方法如下：我们考虑一个集合，比如{a1，a2，…，an}，则一个长度为n的二进制字符串定义了它的一个子集，因为字符串中的每个1表示相应的元素ai存在于我们的子集中。
例如，假设n=4，字符串0111和0000分别代表{a2，a3，a4}和空集。
由于二进制字符串的每个位置都有两种取值选择，因此共有2n个这样的字符串，一个n元素集合便含有2n个子集。
卡特兰数
这种数有种最简单的图形表达，是用n段上斜线段和n段下斜线段能画出多少组不同的“山脉”
（见图3）。
每种不同的山脉构型都对应一组有意义的括号，因此将n对括号有意义地排列起来的方法个数，恰好是第n个卡特兰数。
例如，（（））（）和（（（）））是有意义的括号方法，但（））（（）不是：有意义是指从左向右数时，左括号的个数从不小于右括号的个数。
这对应于山脉始终位于地面上方这一自然条件。
比方说，图3中第一个和最后一个山脉的构型分别对应于（）（（））和（）（）（）这两种括号排列。
第n个卡特兰数还代表将n+2边的正多边形被互不相交的对角线分成三角形的方法个数。
沿着这一思路，卡特兰数还有其他解读方法。
正如二项式系数，也有公式联系了卡特兰数和更小的卡特兰数，这使对它们的计算变得很简便。
斐波那契数列
恐怕没有第二个数列像斐波那契数列（Fibonace）那样使普罗大众着迷了，它是如下的数列：
1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，…
在起始的两个数之后，每个数都是其之前两数之和。
在这一点上，二项式系数与其有相似之处，因为那里每一项也是之前两数之和。
但是斐波那契数列的组成方式更简单：
fn=fn-1+fn-2
这里fn表示第n个斐波那契数，并且我们规定f1=f2=1。
我们将这种用先行项来定义当前项的公式叫作递归（re）或递推关系（recerelation）。
这一数列是从哪里来的呢？它最先是由比萨的莱昂纳多（LeonardoofPisa）——更有名的称呼是斐波那契——在他著名的兔子问题中引入的。
一只雌兔出生两个月后达到生育年龄，并在这之后的每个月生下一只雌兔。
那么每个月初雌兔的总数由斐波那契数列给出。
第一个和第二个月初当然只有一只兔子。
第三个月初雌兔生下一只雌兔，因而我们有2只雌兔。
到了下个月，它又生下一只，于是共有3只雌兔。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！