巴都萬數列

<image>

巴都萬數列（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, ...

此數列以建築師理察·巴都萬命名，理察·巴都萬把此數列的發現歸功於荷蘭建築師漢斯·范·德·蘭在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\ge3 \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