特殊計數數列

斐波那契數列

斐波那契數列的定義與基本性質

歷史背景 斐波那契數列（Fibonacci sequence），又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為「兔子數列」。

定義 斐波那契數列 \(F_n\) 有遞推定義

列舉參照

性質1 \(\displaystyle \sum_{i=1}^n F_i = F_{n+2} -1\) 。

性質2 \(\displaystyle \sum_{i=1}^n F_{2i-1} = F_{2n}\) 。

性質3 \(\displaystyle\sum_{i=1}^n F_{2i} = F_{2n+1}-1\) 。

性質4 \(\displaystyle \sum_{i=1}^n F_{i}^2 = F_{n}F_{n+1}\) 。

性質5 \(\displaystyle F_{n+m} = F_{n-1}F_{m-1}+F_nF_m\) 。

性質6 \(F_n^2 = (-1)^{n-1} + F_{n-1}F_{n+1}\) 。

性質7 \(F_{2n-1} = F_n^2 - F_{n-2}^2\) 。

性質8 \(F_n = \dfrac{F_{n-2}+F_{n+2}}{3}\) 。

性質9 \(\lim\limits_{n\to\infty} \dfrac{F_{n+1}}{F_n} = \dfrac{\sqrt{5}-1}{2}\) 。

性質10 \(F_n = \dfrac{\left(\dfrac{1+\sqrt5}{2} \right)^n - \left(\dfrac{1-\sqrt5}{2} \right)^n}{\sqrt 5}\) 。

卡特蘭數

卡特蘭數的定義與基本性質

歷史背景 卡特蘭數（Catalan number），又稱卡塔蘭數、明安圖數，是組合數學中一種常出現於各種計數問題中的數列。以比利時的數學家歐仁·查理·卡特蘭的名字來命名。1730年左右被蒙古族數學家明安圖使用於對三角函數冪級數的推導而首次發現，1774年被髮表在《割圜密率捷法》。

定義 卡特蘭數 \(H_n\) 有遞推定義

列舉參照

性質1 \(H_n = \dfrac{1}{n+1} \dbinom{2n}{n}\) 。

性質2 \(H_n = \dbinom{2n}{n} - \dbinom{2n}{n-1}\) 。

性質3 \(H_n = \dfrac{4n-2}{n+1}H_{n-1}\) 。

性質1的證明：

我們設卡特蘭數的生成函數為 \(\displaystyle G(x) = \sum_{i=0}^\infty H_ix^i\) ，可得

\[\begin{aligned} G^2(x) &= H_0^2 + (H_0H_1+H_1H_0)x + (H_0H_2 + H_1^2 + H_2H_0)x^2 + \cdots \\ &= H_1 + H_2x + H_3x^2 + \cdots \\ \end{aligned} \]

於是有 \(xG^2(x) - G(x) + 1 = 0\) ，解得 \(G(x) = \dfrac{1-\sqrt{1-4x}}{2x}\) 並且 \(G(0) = 1,\lim_\limits{x\to 0} G(x) = 1\) 。

我們對 \(G(x)\) 在 \(x = 0\) 處泰勒展開 \(\displaystyle (1+x)^\alpha = \sum_{i=0}^\infty \binom{\alpha}{i}x^i\) ，有

\[\begin{aligned} G(x) &= \frac{1}{2x} \sum_{i=1}^\infty (-1)\binom{1/2}{i}(-4x)^i \\ &= \frac{1}{2x} \sum_{i=1}^\infty (-1)\frac{(1/2)(1/2-1)\cdots(1/2-i+1)}{i!} (-4x)^i \\ &= \frac{1}{2x} \left( 1+\sum_{i=2}^\infty \frac{(2i-3)!!}{i!} (2x)^i \right) \\ &= \frac{1}{2x} \left( 1+\sum_{i=2}^\infty \frac{(2i-2)!}{i! \cdot 2 \cdots (2i-2)} (2x)^i \right) \\ &= \frac{1}{2x} \sum_{i=1}^\infty \frac{(2i-2)!}{i! \cdot (i-1)!} x^i \\ &= \frac{1}{2x} \sum_{i=0}^\infty \frac{(2i)!}{(i+1)! \cdot i!} x^{i+1} \\ &= \sum_{i=0}^\infty \frac{1}{i+1} \frac{(2i)!}{i! \cdot i!} x^{i} \\ &= \sum_{i=0}^\infty \frac{1}{i+1} \binom{2i}{i} x^{i} \\ \end{aligned} \]

綜上，根據 \(G(x)\) 的 \(x^n\) 係數可得 \(H_n = \dfrac{1}{n+1} \dbinom{2n}{n}\) 。

性質2的證明：

由性質1可得，\(H_n = \dfrac{1}{n+1} \dbinom{2n}{n} = \dbinom{2n}{n} - \dfrac{n}{n+1} \dbinom{2n}{n} = \dbinom{2n}{n} - \dbinom{2n}{n-1}\) 。

性質3的證明：

由性質1可得， \(H_n = \dfrac{1}{n+1} \dbinom{2n}{n} = \dfrac{1}{n+1} \dfrac{(2n)!}{n!n!} = \dfrac{4n-2}{n+1} \dfrac{1}{n} \dfrac{(2n-2)!}{(n-1)!(n-1)!} = \dfrac{4n-2}{n+1} H_{n-1}\) 。

卡特蘭數的應用

這裡只列舉了幾個經典的情況，還有許多就不一一列舉了，解釋都是大同的。

這些問題的共同點就是，有具有字首限制的兩種操作，或可以劃分為多個子問題的和。

滿足通項關係的情況

1. 網格圖路徑

   在 \(n \times n\) 的網格圖中，從 \((0,0)\) 走到 \((n,n)\) ，滿足每次可以向上或向右走一格，且任意時刻向右次數不少於向上次數的路徑方案數。

   方法：

   限制可理解為不能越過（可以碰到）直線 \(y=x\) 的方案數。

   不考慮 \(y=x\) 的限制，共有 \(\dbinom{2n}{n}\) 種方案。

   考慮不合法的方案，即越過 \(y=x\) 的方案，等價於碰到 \(y = x+1\) 的方案。每個不合法的方案，找到其碰到 \(y = x+1\) 的第一個交點，將此之後的路徑沿 \(y=x+1\) 對稱翻折，會得到唯一對應的一條 \((0,0)\) 到 \((n-1,n+1)\) 的路徑。同時對於 \((0,0)\) 到 \((n-1,n+1)\) 的每條路徑，也可以找到第一個與 \(y=x+1\) 的交點，將此之後的路徑沿 \(y=x+1\) 對稱翻折，也會得到唯一對應的一條 \((0,0)\) 到 \((n,n)\) 的不合法的路徑。

   綜上， \((0,0)\) 到 \((n,n)\) 的不合法路徑和 \((0,0)\) 到 \((n-1,n+1)\) 的路徑是一一對應的，因此 \((0,0)\) 到 \((n,n)\) 的合法路徑方案數為 \(H_n = \dbinom{2n}{n} - \dbinom{2n}{n-1}\) 。

   當 \(y = x + k\) 時，可以同樣分析。

2. 括號匹配

   有 \(n\) 個左括號和 \(n\) 個右括號，求長度為 \(2n\) 的合法括號序列個數。

   方法：

   限制是任意字首序列中，左括號個數不少於右括號個數。

   可以同網格圖路徑中的方法類似，翻折操作變成左右括號互換。

3. 不相交弦問題

   一個圓周上有 \(2n\) 個點，兩兩配對並在兩點間連一條弦，要求所連的 \(n\) 條弦沒有交點，求有多少種配對數。

   方法：

   我們規定逆時針方向為正，從其中一個點開始，限制是任意字首序列中，左端點個數不少於右端點個數。

   可以同網格圖路徑中的方法類似，翻折操作變成左右端點互換。

4. 出棧序列

   一個棧（無窮大）的進棧序列為 \(1,2,\cdots ,n\) 有多少個不同的出棧序列？

   方法：

   同括號匹配。

滿足遞推關係的情況

1. 階梯矩形的矩形劃分數

   求 \(n\) 層矩形階梯分為 \(n\) 個矩形的方案數。

2. 凸多邊形的三角劃分

   一個凸的 \(n+2\) 邊形，用 \(n-1\) 條直線連線它的兩個頂點使之分成 \(n\) 個三角形，每條直線不能相交，求劃分方案數。

3. 二元樹計數

   二元樹有 \(n\) 個節點，求不同的二元樹的個數。

斯特林數

貝爾數

分拆數

伯努利數