查看“巴都萬數列”的源代码

'''巴都萬數列'''（Padovan Sequence）是一個[[整數]]數列，由起始數值<math>P_0=P_1=P_2=1</math>和[[遞歸關係]]<math>P_{n} = P_{n-2} + P_{n-3}</math>定義。

首數個值為[[1]], 1, 1, [[2]], 2, [[3]], [[4]], [[5]], [[7]], [[9]], [[12]], [[16]], [[21]], [[28]], [[37]] ...（[[OEIS:A000931]]）

此數列以建築師[[理察·巴都萬]]命名，他的論文Dom（1994年）提及Hans Van Der Laan應用[[銀數]]在建築方面。1996年6月，[[艾恩·史都華]]在《[[科學美國人]]》雜誌提到這個數列。

[[File:Padovan triangles.png|thumb|以巴都萬數為邊長的等邊[[三角形]]組成的螺旋]]

==遞歸關係==
* <math>P_n = P_{n-1} + P_{n-5}</math>（此關係可從圖中見得）
* <math>P_n = P_{n-2} + P_{n-4} + P_{n-8}</math>
* <math>P_n = P_{n-3} + P_{n-4} + P_{n-5}</math>
* <math>P_n = P_{n-4} + P_{n-5} + P_{n-6} + P_{n-7} + P_{n-8}</math>

[[佩蘭數列]]滿足相同的遞歸關係。它亦可從巴都萬數列定義：
<math>Perrin_n = P_{n+1} + P_{n-10}</math>

==反巴都比數列==
使用遞歸關係<math>P_{-n} = P_{-n+3} - P_{-n+1}</math>可將巴都比數列推廣到[[負數]]項。這樣的定義跟將[[斐波那契數]]推廣到[[斐波那契數列#反斐波那契數列|反斐波那契數列]]相似。另一方面，反斐波那契數列取絕對值便和斐波那契數列相等，但反巴都比數列卻不：

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

==項的和==

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

:<math>\sum_{m=0}^n P_m=P_{n+5}-2.</math>

下面是每隔數項的和：

:<math>\sum_{m=0}^n P_{2m}=P_{2n+3}-1</math>
:<math>\sum_{m=0}^n P_{2m+1}=P_{2n+4}-1</math>
:<math>\sum_{m=0}^n P_{3m}=P_{3n+2}</math>
:<math>\sum_{m=0}^n P_{3m+1}=P_{3n+3}-1</math>
:<math>\sum_{m=0}^n P_{3m+2}=P_{3n+4}-1</math>
:<math>\sum_{m=0}^n P_{5m}=P_{5n+1}.</math>

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

:<math>\sum_{m=0}^n P_{m}^2=P_{n+2}^2-P_{n-1}^2-P_{n-3}^2</math>
:<math>\sum_{m=0}^n P_{m}^2 P_{m+1}=P_{n}P_{n+1}P_{n+2}</math>
:<math>\sum_{m=0}^n P_{m}P_{m+2}=P_{n+2}P_{n+3}-1.</math>

==其他恆等式==
:<math>P_{n}^2-P_{n+1}P_{n-1}=P_{-n-7}.</math>

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

:<math> \sum_{2m+n=k}{m \choose n}=P_{k-2}.</math>

==估計值==
<math>x^3-x-1=0</math>有三個根：唯一的[[實數]]根<math>p</math>（即[[銀數]]）和兩個[[複數]]根<math>q</math>和<math>r</math>。

:<math>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)}. </math>

因為<math>q</math>和<math>r</math>的絕對值都少於1，當<math>n</math>趨近無限，其[[冪]]會趨近0。因此，對於很大的<math>n</math>，可以以下面的公式估計：
:<math>P_n \approx \frac {p^n} {\left(3p^2-1\right)} = \frac {p^n} {4.264632...}.</math>

從上面的公式亦知<math>\frac{P_{n+1}}{P_n}</math>的值趨近銀數。

==整數分拆上的定義==
<math>P_n</math>可以用不同的[[整數分拆]]來定義。

* <math>P_n</math>是將<math>n+2</math>寫成一個有序、每項是2或3的和式的方法的數目。例如<math>P_6=4</math>，有4種方法將8寫成這類和式：
: 2+2+2+2 ; 2+3+3 ; 3+2+3 ; 3+3+2

* <math>P_{2n-2}</math>是將<math>n</math>寫成一個有序且式中沒有項為2的和式的方法的數目。例如<math>P_{5 \times 2 - 2}=P_8=7</math>，有7種方法將5寫成這類和式：
: 1+1+1+1+1 ; 1+1+3 ; 1+3+1 ; 3+1+1 ; 4+1 ; 1+4 ; 5
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

* <math>P_n</math>是將<math>n</math>寫成一個有序且「回文型」且式中沒有項為2的和式的方法的數目。例如<math>P_9=9</math>，有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

* <math>P_n</math>是將<math>n+4</math>寫成一個有序的、每項除以3都餘2的和式的方法的數目。例如<math>P_7=5</math>，有5種方法將11寫成這類和式：
: 11 ; 2+2+2+5 ; 2+2+5+2 ; 2+5+2+2 ; 5+2+2+2

==生成函數==
巴都萬數列的[[生成函數]]為
:<math>G(P_n;x)=\frac{1+x}{1-x^2-x^3}.</math>

它可以用於證明巴都萬數跟幾何級數的項的積的等式，例如：
:<math>\sum_{m=0}^{\infty}\frac{P_n}{2^n} = \frac{12}{5}.</math>

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

:<math>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.</math>

首七個巴都萬多項式為：

:<math>P_0(x)=1 \,</math>
:<math>P_1(x)=x \,</math>
:<math>P_2(x)=x^2 \,</math>
:<math>P_3(x)=x^2+1\,</math>
:<math>P_4(x)=x^3+x \,</math>
:<math>P_5(x)=x^3+x^2+x\,</math>
:<math>P_6(x)=x^4+2x^2+1\,</math>
:<math>P_7(x)=x^4+2x^3+x^2+x\,</math>

第<math>n</math>個巴都萬數即<math>P_n(1)</math>。

==其他特質==
*奇偶性：按「奇奇奇偶偶奇偶」的組合重覆出現。
*數列中的[[質數]]：<math>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; ...</math>（[[OEIS:A000931]]）
*數列中的[[平方數]]：<math>P_{0,1,2}=1 ; P_6=2^2 ; P_9=3^2 ; P_{11}=4^2 ; P_{15}=7^2</math>
==外部連結==
* [http://mathworld.wolfram.com/PadovanSequence.html Padovan Sequence]（[[MathWorld]]）
* [https://web.archive.org/web/20030424191509/http://members.fortunecity.com/templarser/padovan.html Tales of a Neglected Number]，艾恩·史都華在雜誌發表的文章
* [https://web.archive.org/web/20041205222003/http://www.student.gov.cn/zxpd/mt880.htm 學生科技網--中學生科技：美丽的螺旋线 黄金分割漫谈之三，李颍伯]
* [http://www.nexusjournal.com/conferences/N2002-Padovan.html Dom Hans Van Der Laan And The Plastic Number], Richard Padovan

[[Category:整数数列|B]]