巴都萬數列

**巴都萬數列**（Padovan Sequence）是一個整數數列，其起始數值跟遞迴關係定義為：

　
: $P(0)=P(1)=P(2)=1$

　
: $P(n)=P(n-2)+P(n-3)$

_P_(_n_) 的前幾個值是：

　
: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... （OEIS 數列 A000931）

此數列以建築師理察・巴都萬命名，理察・巴都萬把此數列的發現歸功於荷蘭建築師漢斯・范・德・蘭在 1994 年發表的論文《Dom. Hans van der Laan : Modern Primitive》。1996 年 6 月，艾恩・史都華在《科學美國人》雜誌提到這個數列。

## 遞迴關係

 * $P_{n}=P_{n-1}+P_{n-5}$ （此關係可從圖中見得）
* $P_{n}=P_{n-2}+P_{n-4}+P_{n-8}$
* $P_{n}=P_{n-3}+P_{n-4}+P_{n-5}$
* $P_{n}=P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8}$

佩蘭數列滿足相同的遞迴關係。它亦可從巴都萬數列定義： $Perrin_{n}=P_{n+1}+P_{n-10}$

## 反巴都萬數列

使用遞迴關係 $P_{-n}=P_{-n+3}-P_{-n+1}$ 可將巴都萬數列推廣到負數項。這樣的定義跟將斐波那契數推廣到反費氏數列相似。另一方面，反費氏數列取絕對值便和費氏數列相等，但反巴都萬數列卻不：

... -7, 4, 0, -3, 4, -3, 1, 1, -2, 2, -1, 0, 1, -1, 1, 0, 0, 1, 0, 1, 1, 1 ...

## 項的和

首 $n$ 項（包括第 0 項）之和比 $P_{n+5}$ 少 2：

　
: $\sum _{m=0}^{n}P_{m}=P_{n+5}-2.$

下面是每隔數項的和：

　
: $\sum _{m=0}^{n}P_{2m}=P_{2n+3}-1$

　
: $\sum _{m=0}^{n}P_{2m+1}=P_{2n+4}-1$

　
: $\sum _{m=0}^{n}P_{3m}=P_{3n+2}$

　
: $\sum _{m=0}^{n}P_{3m+1}=P_{3n+3}-1$

　
: $\sum _{m=0}^{n}P_{3m+2}=P_{3n+4}-1$

　
: $\sum _{m=0}^{n}P_{5m}=P_{5n+1}.$

下面的恆等式跟項與項的乘積之和有關：

　
: $\sum _{m=0}^{n}P_{m}^{2}=P_{n+2}^{2}-P_{n-1}^{2}-P_{n-3}^{2}$

　
: $\sum _{m=0}^{n}P_{m}^{2}P_{m+1}=P_{n}P_{n+1}P_{n+2}$

　
: $\sum _{m=0}^{n}P_{m}P_{m+2}=P_{n+2}P_{n+3}-1.$

## 其他恆等式

　
: $P_{n}^{2}-P_{n+1}P_{n-1}=P_{-n-7}.$

巴都萬數列跟二項式係數之和有關：

　
: $\sum _{2m+n=k}{m \choose n}=P_{k-2}.$

## 估計值

 $x^{3}-x-1=0$ 有三個根：唯一的實數根 $p$ （即銀數）和兩個複數根 $q$ 和 $r$ 。

　
: $P_{n}={\frac {p^{n}}{\left(3p^{2}-1\right)}}+{\frac {q^{n}}{\left(3q^{2}-1\right)}}+{\frac {r^{n}}{\left(3r^{2}-1\right)}}.$

因為 $q$ 和 $r$ 的絕對值都少於 1，當 $n$ 趨近無限，其冪會趨近 0。因此，對於很大的 $n$ ，可以以下面的公式估計：

　
: $P_{n}\approx {\frac {p^{n}}{\left(3p^{2}-1\right)}}={\frac {p^{n}}{4.264632...}}.$

從上面的公式亦知 ${\frac {P_{n+1}}{P_{n}}}$ 的值趨近銀數。

## 整數分拆上的定義

 $P_{n}$ 可以用不同的整數分拆來定義。

 * $P_{n}$ 是將 $n+2$ 寫成一個有序、每項是 2 或 3 的和式的方法的數目。例如 $P_{6}=4$ ，有 4 種方法將 8 寫成這類和式：

　
: 2+2+2+2 ; 2+3+3 ; 3+2+3 ; 3+3+2

 * $P_{2n-2}$ 是將 $n$ 寫成一個有序且式中沒有項為 2 的和式的方法的數目。例如 $P_{5\times 2-2}=P_{8}=7$ ，有 7 種方法將 5 寫成這類和式：

　
: 1+1+1+1+1 ; 1+1+3 ; 1+3+1 ; 3+1+1 ; 4+1 ; 1+4 ; 5

 * $P_{n}$ 是將 $n$ 寫成一個有序且「回文型」且式中沒有項為 2 的和式的方法的數目。例如 $P_{9}=9$ ，有 9 種方法將 9 寫成這類和式：

　
: 9 ; 1+7+1 ; 1+1+5+1+1 ; 1+1+1+3+1+1+1 ; 1+1+1+1+1+1+1+1+1; 3+3+3 ; 4+1+4 ; 3+1+1+1+3; 1+3+1+3+1

* 若上述情況改為 $P_{8}=8$ ，則數列如下：

　
: 1+1+1+1+1+1+1+1: 4+4; 3+1+1+3; 1+3+3+1; 1+1+4+1+1; 1+6+1; 8

 * $P_{n}$ 是將 $n+4$ 寫成一個有序的、每項除以 3 都餘 2 的和式的方法的數目。例如 $P_{7}=5$ ，有 5 種方法將 11 寫成這類和式：

　
: 11 ; 2+2+2+5 ; 2+2+5+2 ; 2+5+2+2 ; 5+2+2+2

## 生成函數

巴都萬數列的生成函數為

　
: $G(P_{n};x)={\frac {1+x}{1-x^{2}-x^{3}}}.$

它可以用於證明巴都萬數跟幾何級數的項的積的等式，例如：

　
: $\sum _{m=0}^{\infty }{\frac {P_{n}}{2^{n}}}={\frac {12}{5}}.$

## 多項式

巴都萬數列可以一般化成一個多項式的集。

　
: $P_{n}(x)=\left\{{\begin{matrix}1,\qquad \qquad \qquad \qquad &{\mbox{if }}n=0\\x,\qquad \qquad \qquad \qquad &{\mbox{if }}n=1\\x^{2},\qquad \qquad \qquad \qquad &{\mbox{if }}n=2\\xP_{n-2}(x)+P_{n-3}(x),&{\mbox{if }}n\geq 3\end{matrix}}\right.$

首七個巴都萬多項式為：

　
: $P_{0}(x)=1\,$

　
: $P_{1}(x)=x\,$

　
: $P_{2}(x)=x^{2}\,$

　
: $P_{3}(x)=x^{2}+1\,$

　
: $P_{4}(x)=x^{3}+x\,$

　
: $P_{5}(x)=x^{3}+x^{2}+x\,$

　
: $P_{6}(x)=x^{4}+2x^{2}+1\,$

　
: $P_{7}(x)=x^{4}+2x^{3}+x^{2}+x\,$

第 $n$ 個巴都萬數即 $P_{n}(1)$ 。

## 其他特質

* 奇偶性：按「奇奇奇偶偶奇偶」的組合重覆出現。
* 數列中的質數： $P_{3,4}=2;P_{5}=3;P_{7}=5;P_{8}=7;P_{14}=37;P_{19}=151;P_{30}=3329;P_{37}=23833;...$ （OEIS:A000931）
* 數列中的平方數： $P_{0,1,2}=1;P_{6}=2^{2};P_{9}=3^{2};P_{11}=4^{2};P_{15}=7^{2}$

## 參考文獻

## 外部連結

* Padovan Sequence （頁面存檔備份，存於網際網路檔案館）（MathWorld）
* Tales of a Neglected Number，艾恩・史都華在雜誌發表的文章
* 學生科技網 -- 中學生科技：美麗的螺旋線 黃金分割漫談之三，李潁伯
* Dom Hans Van Der Laan And The Plastic Number （頁面存檔備份，存於網際網路檔案館）, Richard Padovan