常用数列

1.等差数列 【通项公式】 an=a1+(n-1)d an=Sn-S(n-1) (n>=2) 【前n项和】 Sn=n(a1+an)/2=n*a1+n(n-1)d/2 2.等比数列 【通项公式】 an=a1q^(n-1) an=Sn/S(n-1) (n>=2) 【前n项和】 当q≠1时，等比数列的前n项和的公式为 Sn=a1(1-q^n)/(1-q)=(a1-an*q)/(1-q) (q≠1) 3.斐波那契数列

0、1、1、2、3、5、8、13、21 【通项公式】 an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n} 【前n项和】 Sn=(1/√5)* [((1+√5)/2 )^(n+2)-[((1-√5)/2 )^(n+2)]-1 4.大衍数列

0、2、4、8、12、18、24、32、40、50……　 【通项公式】 an=(n^2-1)/2 (n=2k-1，k∈N) an=n^2/2 (n=2k，k∈N) 【前n项和】 Sn=(n-1)(n+1)(2n+3)/12 (n=2k-1，k∈N) Sn=n(n+2)(2n-1)/12 (n=2k，k∈N)

又有

等记法，称为 二项式系数，即取的 组合数目。此 系数亦可表示为 杨辉三角形。

常用数列一栏表

<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.…… (后一项与前一项之比1.…… )

   还有一项性质，从第二项开始，每个奇数项的平方都比前后两项之积多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,

这个当 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粒白 求任取两粒为一黑一白的概率

取两粒黑的概率是(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