浅谈斐波那契数列和卡特兰数-Toy模板网

这篇具有很好参考价值的文章主要介绍了浅谈斐波那契数列和卡特兰数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

斐波那契数列

斐波那契数列是我们较为熟悉的一类数列了，在学习递归和递推的时候我们就已经能求解 \(n\) 较小的情况了；斐波那契数列的定义如下：

\[\left\{\begin{matrix} F_{n}=0& n=0\\ F_{n}=1& n=1\\ F_{n}=F_{n-1}+F_{n-2}& n\ge 2 \end{matrix}\right. \]

卢卡斯数列

卢卡斯数列经常作为一个工具来研究斐波那契数列，所以这里也会提到一部分

其定义如下：

\[\left\{\begin{matrix} L_{n}=2& n=0\\ L_{n}=1& n=1\\ L_{n}=L_{n-1}+L_{n-2}& n\ge 2 \end{matrix}\right. \]

斐波那契数列通项公式

第 \(n\) 个斐波那契数列可以在 \(O(n)\) 的时间内用递推来解决，但我们有更快速的方式来计算。

例如我们有下面的公式

\[F_{n}=\frac{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}} \]

证明：

由上面我们知道斐波那契数列的递推公式为

\[F_{n}=F_{n-1}+F_{n-2}(n\ge 2) \]

我们设

\[F_{n}-\lambda F_{n-1}=\mu(F_{n-1}-\lambda F_{n-2}) \]

为什么这么设呢，这是因为我们发现构造一个等差数列的话是很难的，所以我们尝试构造一个等比数列 \(b_{n}=q\times b_{n-1}\)，按照上面的设法，把 \(F_{n}-\lambda F_{n-1}\) 看作 \(b_{n}\) 即可发现我们构造了一个等比数列的公式，然后我们后面才能利用等比数列的通项公式进行求解。

拆开移项得到

\[\left\{\begin{matrix} \lambda+\mu=1\\ -\lambda\times \mu=1 \end{matrix}\right. \]

解得

\[\left\{\begin{matrix} \lambda=\frac{1+\sqrt{5}}{2}\\ \mu=\frac{1-\sqrt{5}}{2} \end{matrix}\right. \text{或} \left\{\begin{matrix} \lambda=\frac{1-\sqrt{5}}{2}\\ \mu=\frac{1+\sqrt{5}}{2} \end{matrix}\right. \]

将其带回原式子可以得到

\[\left\{\begin{matrix} F_{n}-\frac{1+\sqrt{5}}{2}F_{n-1}=\frac{1-\sqrt{5}}{2}(F_{n-1}-\frac{1+\sqrt{5}}{2}F_{n-2})\\ F_{n}-\frac{1-\sqrt{5}}{2}F_{n-1}=\frac{1+\sqrt{5}}{2}(F_{n-1}-\frac{1-\sqrt{5}}{2}F_{n-2}) \end{matrix}\right. \]

然后根据等比数列通项公式，我们得到

\[\left\{\begin{matrix} F_{n}-\frac{1+\sqrt{5}}{2}F_{n-1}=(\frac{1-\sqrt{5}}{2})^{n-2}(F_{2}-\frac{1+\sqrt{5}}{2}F_{1})\\ F_{n}-\frac{1-\sqrt{5}}{2}F_{n-1}=(\frac{1+\sqrt{5}}{2})^{n-2}(F_{2}-\frac{1-\sqrt{5}}{2}F_{1}) \end{matrix}\right. \]

然后上式乘以 \(\frac{1-\sqrt{5}}{2}\) ，下式乘以 \(\frac{1+\sqrt{5}}{2}\) 化简就可以得到上面的通项公式了。

浅谈斐波那契数列和卡特兰数

或者可以看看上面这位b站大佬的证明过程，比上面的方法更好理解。

需要注意的是，这个公式对于精度要求较高。

卢卡斯数列的通项公式

其实他的通项公式和斐波那契的很像

\[L_{n}=(\frac{1+\sqrt{5}}{2})^{n}+(\frac{1-\sqrt{5}}{2})^{n} \]

事实上有：

\[\frac{L_{n}+F_{n}\sqrt{5}}{2}=(\frac{1+\sqrt{5}}{2})^{n} \]

其实还有一个式子：

\[L_{n}^{2}-5F_{n}^{2}=-4 \]

矩阵加速求斐波那契数列

我们在之前的题目遇见的求斐波那契数列第 \(n\) 项的值范围都是很小的，因为递归的速度太慢，如果数据范围到达了 \(10^{18}\) 那么我们递推也是一定 TLE 的，所以这个时候就需要用到我们的矩阵加速递推。

设 \(Fib(n)\) 表示一个 \(1\times 2\) 的矩阵 \(\begin{bmatrix}F_{n}&F_{n+1}\end{bmatrix}\) 。我们希望依据 \(Fib(n-1)=\begin{bmatrix}F_{n-1}&F_{n-2}\end{bmatrix}\) 推出 \(Fib(n)\)。

试着来推导一个矩阵 \(\text{base}\)，使 \(Fib(n-1)\times \text{base}=Fib(n)\)，也就是 \(\begin{bmatrix}F_{n-1}&F_{n-2}\end{bmatrix}\times \text{base}=\begin{bmatrix}F_{n}&F_{n-1}\end{bmatrix}\)。

因为 \(F_{n}=F_{n-1}+F_{n-2}\)，所以 \(\text{base}\) 矩阵第一列一定是 \(\begin{bmatrix}1\\1\end{bmatrix}\)，这样才能在进行乘法运算的时候才能令 \(F_{n-1}\) 与 \(F_{n-2}\) 相加，从而得出 \(F_{n}\)。同理，为了得出 \(F_{n-1}\)，矩阵 \(\text{base}\) 的第二列应该为 \(\begin{bmatrix}1\\0\end{bmatrix}\)。

综上所述，\(\text{base}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\) ，原式化为 \(\begin{bmatrix}F_{n-1}&F_{n-2}\end{bmatrix}\times \begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}F_{n}&F_{n-1}\end{bmatrix}\)。

定义初始矩阵 \(ans=\begin{bmatrix}F_{2}&F_{1}\end{bmatrix}=\begin{bmatrix}1&1\end{bmatrix}\)，\(\text{base}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\)。那么，\(F_{n}\) 就等于 \(ans\times \text{base}^{n-2}\) 这个矩阵的第一行第一列的元素，也就是 \(\begin{bmatrix}1&1\end{bmatrix}\times \begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-2}\) 的第一行第一列的元素。

注意矩阵乘法不满足交换律，所以不能将两个矩阵反过来，另外，对于 \(n\le 2\) 的情况，可以直接输出 \(1\)。

P1962斐波那契数列 - 洛谷

参考代码：

#include<bits/stdc++.h>
#define int long long
#define P 1000000007
#define N 110
using namespace std;
int n;
struct sb{int m[N][N];}ans,base;
inline sb cheng(sb a,sb b,int ok)
{
    sb c;
    for(int i=1;i<=ok;i++)
    {
          for(int j=1;j<=ok;j++)
          {
              c.m[i][j]=0;
            for(int k=1;k<=ok;k++)
              c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%P;
          }
    }
    return c;
}
inline sb jzksm(sb x,int y)
{
    sb res=x;y--;
    while(y)
    {
        if(y&1)res=cheng(res,x,2);
        x=cheng(x,x,2);
        y>>=1;
    }
    return res;
}
signed main()
{
    cin>>n;
    if(n==1||n==2){puts("1");return 0;}
    ans.m[1][1]=1;ans.m[1][2]=1;
    base.m[1][1]=1;base.m[1][2]=1;
    base.m[2][1]=1;base.m[2][2]=0;
    base=jzksm(base,n-2);
    ans.m[1][1]=(base.m[1][1]+base.m[1][2])%P;
    cout<<ans.m[1][1]<<endl;
    return 0;
}

快速倍增法

我们可以用上面的方法得到下面两个等式：

\[F_{2k}=F_{k}(2F_{k+1}-F_{k}) \]

\[F_{2k+1}=F_{k+1}^{2}+F_{k}^{2} \]

于是我们可以通过这样的方法快速计算两个相邻的斐波那契数（常数比矩阵法小）。返回值是一个二元组 \((F_{n},F_{n+1})\)。

性质

这里只列出一部分。

卡西尼性质：\(F_{n-1}F_{n+1}-F_{n}^{2}=(-1)^{n}\)
附加性质：\(F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}\)
性质二中 \(k=n\)，我们得到 \(F_{2n}=F_{n}(F_{n+1}+F_{n-1})\)
由性质三可以归纳证明，\(\forall k\in \mathbb{N} ,F_{n}\mid F_{nk}\)
上述性质可逆，即 \(\forall F_{a}\mid F_{b},a\mid b\)
GCD 性质：\(\gcd(F_{m},F_{n})=F_{\gcd(n,m)}\)

斐波那契数列和卢卡斯数列

不难发现有个上面提到的式子和三角函数公式很像：

\[\frac{L_{n}+F_{n}\sqrt{5}}{2}=(\frac{1+\sqrt{5}}{2})^{n} \]

\[\cos nx+i\sin nx=(\cos x+i\sin x)^{n} \]

上面两个式子很像。

\[L_{n}^{2}-5F_{n}^{2}=-4 \]

\[\cos ^{2}x+\sin ^{2}x=1 \]

这两个式子也很像。

那么我们大胆推测一下，是不是卢卡斯数列构成的图像很像余弦函数，斐波那契数列构成的图像很像正弦函数？

根据：

\[(\frac{1+\sqrt{5}}{2})^{m}(\frac{1+\sqrt{5}}{2})^{n}=(\frac{1+\sqrt{5}}{2})^{n+m} \]

可以得到两下标之和的等式：

\[2L_{m+n}=5F_{n}F_{m}+L_{n}L_{m} \]

\[2F_{m+n}=F_{m}L_{n}+L_{m}F_{n} \]

于是推论就有二倍下标的等式：

\[L_{2n}=L_{n}^{2}-2(-1)^{n} \]

\[F_{2n}=F_{n}L_{n} \]

这也是一种快速倍增下标的办法。

模意义下周期性

考虑模 \(p\) 意义下的斐波那契数列，可以容易地使用抽屉原理证明，该数列是有周期性的。考虑模意义下前 \(p^{2}+1\) 个斐波那契数对（两个相邻数配对）：

\[(F_{1},F_{2}),(F_{2},F_{3}),...,(F_{p^{2}+1},F_{p^{2}+2}) \]

\(p\) 的剩余系大小为 \(p\)，意味着在前 \(p^{2}+1\) 个数对中必有两个相同的数对，于是这两个数对可以往后生成相同的斐波那契数列，那么他们就是周期性的。

卡特兰数

卡特兰数也算是比较常见的一种

其问题灵活多变，较为经典的有：

在圆上选 \(2n\) 个点，将这些点成对连接起来使得所得到的 \(n\) 条线段不相交的方案数。
一个栈的进栈序列为 \(1,2,3,\dots,n\) 有多少个不同的可能的出栈序列。
\(n\) 个节点可以构造多少个不同的二叉树？

如果是给定两种操作，一个操作的个数不超过另一种操作的个数，或者两种操作没有交集，求合法操作方案的总数，那么一般就是卡特兰数。

其对应的序列为 \(1,1,2,5,14,42,132...\)

递推式

为了防止冲突，用 \(H(i)\) 来表示第 \(i\) 个卡特兰数。

该递推关系的解为：

\[H_{n}=\frac{C_{2n}^{n}}{n+1}(n\ge 2) \]

\[H_{n}= \left\{\begin{matrix} 1&n=0\\ 1&n=1\\ \sum_{i=1}^{n}H_{i-1}H_{n-i}&n\ge 2 \end{matrix}\right. \]

\[H_{n}=\frac{H_{n-1}(4n-2)}{n+1} \]

实际上最常用的是第一个公式的变形：

\[H_{n}=C_{2n}^{n}-C_{2n}^{n-1} \]

例题：P1044[NOIP2003 普及组] 栈 - 洛谷

直接套用公式二即可。

参考代码：

#include<bits/stdc++.h>
#define int long long
#define N 1000100 
using namespace std;
int n,c[N];
signed main()
{
	c[0]=1;
	cin>>n;
	for(int i=1;i<=n;i++)
	  c[i]=(c[i-1]*(4*i-2))/(i+1);
	cout<<c[n]<<endl;
	return 0; 
}