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

斐波那契数列

斐波那契数列是我们较为熟悉的一类数列了，在学习递归和递推的时候我们就已经能求解 \(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})\)。

性质

这里只列出一部分。

1. 卡西尼性质：\(F_{n-1}F_{n+1}-F_{n}^{2}=(-1)^{n}\)

2. 附加性质：\(F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}\)

3. 性质二中 \(k=n\)，我们得到 \(F_{2n}=F_{n}(F_{n+1}+F_{n-1})\)

4. 由性质三可以归纳证明，\(\forall k\in \mathbb{N} ,F_{n}\mid F_{nk}\)

5. 上述性质可逆，即 \(\forall F_{a}\mid F_{b},a\mid b\)

6. 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; 
}

封闭形式

卡特兰数的递推式我们前面说过了，也就是这个：

\[H_{n}=\sum_{i=0}^{n-1}H_{i}H_{n-i-1}(n\ge 2) \]

其中 \(H_{0}=1,H_{1}=1\) 设它的普通生成函数为 \(H(x)\)

我们发现卡特兰数的递推式与卷积的形式很相似，因此我们用卷积来构造关于 \(H(x)\) 的方程：

\[H(x)=\sum_{n\ge 0}^{}H_{n}x^{n} \]

\[=1+\sum_{n\ge 1}^{}\sum_{i=0}^{n-1}H_{i}x^{i}H_{n-i-1}x^{n-i-1}x \]

\[=1+x\sum_{i\ge 0}^{}H_{i}x^{i}\sum_{n\ge 0}^{}H_{n}x^{n} \]

\[=1+xH^{2}(x) \]

解得：

\[H(x)=\frac{1\pm\sqrt{1-4x}}{2x} \]

那么这就产生了一个问题：我们应该取哪一个根呢？我们将其分子有理化：

\[H(x)=\frac{2}{1\mp\sqrt{1-4x}} \]

代入 \(x=0\)，我们得到的是 \(H(x)\) 的常数项，也就是 \(H_{0}\)。当 \(H(x)=\frac{2}{1+\sqrt{1-4x}}\) 的时候有 \(H(0)=1\)，满足要求。而另一个解会出现分母为 \(0\) 的情况，舍去。

因此我们得到了卡特兰数生成函数的封闭形式：

\[H(x)=\frac{1-\sqrt{1-4x}}{2x} \]