常用数列一栏表
<1>Fibonacci数列
{ 0 n=0
Fib(n)={ 1 n=1
{ Fib(n-1)+Fib(n-2) 其他情况
Fib(n)的前十项
Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2, Fib(4)=3, Fib(5)=5, Fib(6)=8, Fib(7)=13 Fib(8)=21, Fib(9)=34, Fib(10)=55.
当n>45 int已经超出范围了, long long int 也只能到91.大于这个数就必须用高精度了.
1.取石子游戏,
有N粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方
如果数是Fibonacci数列,则甲必败.
2. 楼梯上有n阶台阶,上楼时可以一步上一阶,也可以一步上两阶,问一共有多少种不同的上楼梯的方法.
3．杨辉三角对角线上各数之和构成斐波拉契数列 ．
4．多米诺牌（可以看作一个2×1大小的方格）完全覆盖一个n×2的棋盘，覆盖的方案数等于斐波拉契数列。
5． 从蜜蜂的繁殖来看，雄峰只有母亲，没有父亲，因为蜂后产的卵，受精的孵化为雌蜂，未受精的孵化为雄峰。人们在追溯雄峰的祖先时，发现一只雄峰的第n代祖先的数目刚好就是斐波拉契数列的第n项Fn。
6．钢琴的13个半音阶的排列完全与雄峰第六代的排列情况类似，说明音调也与斐波拉契数列有关。
7．自然界中一些花朵的花瓣数目符合于斐波拉契数列，也就是说在大多数情况下，一朵花花瓣的数目都是3,5,8,13,21,34,……(有6枚是两套3枚;有4枚可能是基因突变)。
8．如果一根树枝每年长出一根新枝，而长出的新枝两年以后，每年也长出一根新枝，那么历年的树枝数，也构成一个斐波拉契数列
以上的问题都能应用到Fibonacci数列.
A，Fibonacci数列的一些特殊性质
随着数列项数的增加，前一项与后一项之比越逼近黄金分割0.6180339887…… (后一项与前一项之比1.6180339887…… )
还有一项性质，从第二项开始，每个奇数项的平方都比前后两项之积多1，每个偶数项的平方都比前后两项之积少1。
Fibonacci数列还有变种,就是前两项的值变了,但是递推的公式没有变.
Note: 斐波拉契数列的变式
■１.帕多瓦数列：1，1，1，2，2，3，4，5，7，9，12，16，21，……这样的数列称为帕多瓦数列。它和斐波拉契数列非常相似，稍有不同的是：每个数都是跳过它前面的那个数，并把再前面的两个数相加而得出的。这个数列可以用另一幅图来表示，它是由一些等边三角形构成的(如右图)。开始的三角形用灰色表示，为了使这些三角形天衣无缝地拼在一起，头三个三角形的边长均为1，其后的两个三角形的边长为2，然后依次是3、4、5、7、9、12、16、2l……等等。
■２.冬冬有15块糖，如果每天至少吃3块，吃完为止，那么共有多少种不同的吃法？
如果冬冬有3块糖、4块糖或者5块糖，都只有1种吃法；如果有6块糖，则有2种吃法；如果有7块糖，则有3种吃法；如果有8块糖，则有4种吃法；如果有9块糖，则有6种吃法．
既：吃糖的粒数：３ ４ ５ ６ ７ ８ ９ １０ １１ １２．．．
糖的吃法：１ １ １ ２ ３ ４ ６ ９ １３ １９．．．
这样的数列，它和斐波拉契数列不同的是，每次都是跳过中间的那个数，再把第1、3两个数相加，等于第4个数。它的规律和斐波拉契数列既相似之处又有不同之处．
■３.小明要上楼梯，他每次能向上走一级、两级或三级，如果楼梯有10级，他有几种不同的走法？
这里我们不妨也来研究一下其中的规律：如果楼梯就一级，他有1种走法；如果楼梯有两级，他有2种走法；如果楼梯有三级，他有4种走法；如果有五级楼梯，他有7种走法．
既：楼梯的级数：１ ２ ３ ４ ５ ６ ７ ８ ．．．
上楼梯的走法：１ ２ ４ ７ １３ ２４ ４４ ８１．．．
这其中的规律就是，这里从第4个数开始，每一个数都等于它前面的3个数之和。
<2> Catalan数
原理：
令h(1)＝1，catalan数满足递归式：
h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)
该递推关系的解为：
h(n-1)=c(2n-2,n-1)/n (n=1,2,3,...)
前十项
1, 1, 2, 5, 14, 42,132 ,429, 1430, 4862
正如你看到的,增长的速度十分快, n>20 就已经超出int的范围了.数据一大用高精度是必然的了.
我并不关心其解是怎么求出来的，我只想知道怎么用catalan数分析问题。
我总结了一下，最典型的三类应用：（实质上却都一样，无非是递归等式的应用，
就看你能不能分解问题写出递归式了）
1.括号化问题。
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，
只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
2.出栈次序问题。
一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，
另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，
售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，
持10元者到达视作使栈中某5元出栈)
3.将多边行划分为三角形问题。
将一个凸多边形区域分成三角形区域的方法数?
类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。
每天她走2n个街区去上班。如果他
从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
Catalan数的几个变种:只给出前十项与递推式:
1. (1-(1-4*x)^(1/2))/(2*x*(1-x))
前十项 1, 2, 4, 9, 23, 65, 197, 626, 2056, 6918 跟上面一样增长速度非常快,
x大于20就超出int 的范围了.
2. (1-sqrt(1-4x))/(2x(1-x)) = C(x)/(1-x)
前十项 1, 3, 8, 22, 64, 196, 625, 2055, 6917, 23713,跟上面一样增长速度非常快,
x大于20就超出int 的范围了.
3. a(n, k) = C(n-1, k-1)C(n, k-1)/k for k!=0; a(n, 0)=0
前 n 项(我也没有数有多少项)
1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 20, 10, 1, 1, 15, 50, 50, 15, 1, 1, 21, 105, 175, 105, 21, 1, 1, 28, 196, 490, 490, 196, 28, 1, 1, 36, 336, 1176, 1764, 1176, 336, 36, 1, 1, 45, 540, 2520, 5292, 5292, 2520, 540, 45, 1, 1, 55, 825, 4950, 13860, 19404, 13860,
4950, 825
这个的增长速度是很慢的.可以不用高精度.
4. a(n+1)=a(n)+a(1)a(n-2)+a(2)a(n-3)+...+a(n-1)a(0).
前十几项 1, 1, 1, 2, 4, 8, 17, 37, 82, 185, 423, 978, 2283, 5373, 12735, 30372, 72832, 175502
这个当 n>28 int就无能为力了.用高精度是选择的一个方向.
<3> 大衍数列
０、 ２、４、８、１２、１８、２４、３２、４０、５０
递推公式:（ｎ＊ｎ－１）／２（ｎ为奇数）、ｎ＊ｎ／２（ｎ为偶数）
我没有用用过这个,但是能记住更好.
<4>等差数列 (只记几个特殊的公式)
等差数列的通项公式为 an=a1+(n-1)d (1)
前n项和公式为：
Sn=na1+n(n-1)d/2或Sn=n(a1+an)/2(2)
an=am+(n-m)d
它可以看作等差数列广义的通项公式。
从等差数列的定义、通项公式，前n项和公式还可推出：
a1+an=a2+an-1=a3+an-2=…=ak+an-k+1，k∈{1,2,…,n}
若m，n，p，q∈N*，且m+n=p+q，则有
am+an=ap+aq
Sm-1=(2n-1)an，S2n+1=(2n+1)an+1
Sk，S2k-Sk，S3k-S2k，…，Snk-S(n-1)k…或等差数列
和＝（首项＋末项）*项数÷2
项数＝（末项-首项）÷公差＋1
首项=2和÷项数-末项
末项=2和÷项数-首项
项数=(末项－首项）/公差＋1
〈5〉 等比数列
（1）等比数列的通项公式是：An=A1*q^（n－1）
（2）前n项和公式是：Sn=[A1(1-q^n)]/(1-q)
且任意两项am，an的关系为an=am·qn-m
（3）从等比数列的定义、通项公式、前n项和公式可以推出： a1·an=a2·an-1=a3·an-2=…=ak·an-k+1，k∈{1,2,…,n}
（4）若m，n，p，q∈N*，则有：ap·aq=am·an，
等比中项：aq·ap=2ar ar则为ap，aq等比中项。
记πn=a1·a2…an，则有π2n-1=(an)2n-1，π2n+1=(an+1)2n+1
另外，一个各项均为正数的等比数列各项取同底数数后构成一个等差数列；反之，以任一个正数C为底，用一个等差数列的各项做指数构造幂Can，则是等比数列
①若 m、n、p、q∈N，且m＋n=p＋q，则am·an=ap*aq；
②在等比数列中，依次每 k项之和仍成等比数列.
“G是a、b的等比中项”“G^2=ab（G≠0）”.
在等比数列中，首项A1与公比q都不为零.
注意：上述公式中A^n表示A的n次方。
概率问题:
10粒围棋中有6粒黑4粒白 求任取两粒为一黑一白的概率
两种解决方式1：全概率法：
取两粒黑的概率是(6/10)*(5/9)=1/3
取两粒白的概率是(4/10)*(3/9)=2/15
取一黑一白的概率就是1减前两个情况，就是8/15
2 排列组合法：
c（6 1）c（4 1）/ c（10 2）算出来为8/15
转播
