以巴都萬數為邊長的等邊三角形組成的螺旋
巴都萬數列（Padovan Sequence）是一個整數數列[1]，其起始數值跟遞歸關係定義為：
P
(
0
)
=
P
(
1
)
=
P
(
2
)
=
1
{\displaystyle P(0)=P(1)=P(2)=1}
P
(
n
)
=
P
(
n
−
2
)
+
P
(
n
−
3
)
{\displaystyle 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）
此數列以建築師理察·巴都萬（英语：Richard Padovan）命名，理察·巴都萬把此数列的发现归功于荷兰建筑师汉斯·范·德·兰（英语：Hans van der Laan）在1994年发表的论文《Dom. Hans van der Laan : Modern Primitive》[2]。1996年6月，艾恩·史都華在《科學美國人》雜誌提到這個數列。
遞歸關係[编辑]
P
n
=
P
n
−
1
+
P
n
−
5
{\displaystyle P_{n}=P_{n-1}+P_{n-5}}
（此關係可從圖中見得）
P
n
=
P
n
−
2
+
P
n
−
4
+
P
n
−
8
{\displaystyle P_{n}=P_{n-2}+P_{n-4}+P_{n-8}}
P
n
=
P
n
−
3
+
P
n
−
4
+
P
n
−
5
{\displaystyle 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
{\displaystyle P_{n}=P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8}}
佩蘭數列滿足相同的遞歸關係。它亦可從巴都萬數列定義：
P
e
r
r
i
n
n
=
P
n
+
1
+
P
n
−
10
{\displaystyle Perrin_{n}=P_{n+1}+P_{n-10}}
反巴都萬數列[编辑]
使用遞歸關係
P
−
n
=
P
−
n
+
3
−
P
−
n
+
1
{\displaystyle 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
{\displaystyle n}
項（包括第0項）之和比
P
n
+
5
{\displaystyle P_{n+5}}
少2：
∑
m
=
0
n
P
m
=
P
n
+
5
−
2.
{\displaystyle \sum _{m=0}^{n}P_{m}=P_{n+5}-2.}
下面是每隔數項的和：
∑
m
=
0
n
P
2
m
=
P
2
n
+
3
−
1
{\displaystyle \sum _{m=0}^{n}P_{2m}=P_{2n+3}-1}
∑
m
=
0
n
P
2
m
+
1
=
P
2
n
+
4
−
1
{\displaystyle \sum _{m=0}^{n}P_{2m+1}=P_{2n+4}-1}
∑
m
=
0
n
P
3
m
=
P
3
n
+
2
{\displaystyle \sum _{m=0}^{n}P_{3m}=P_{3n+2}}
∑
m
=
0
n
P
3
m
+
1
=
P
3
n
+
3
−
1
{\displaystyle \sum _{m=0}^{n}P_{3m+1}=P_{3n+3}-1}
∑
m
=
0
n
P
3
m
+
2
=
P
3
n
+
4
−
1
{\displaystyle \sum _{m=0}^{n}P_{3m+2}=P_{3n+4}-1}
∑
m
=
0
n
P
5
m
=
P
5
n
+
1
.
{\displaystyle \sum _{m=0}^{n}P_{5m}=P_{5n+1}.}
下面的恆等式跟項與項的乘積之和有關：
∑
m
=
0
n
P
m
2
=
P
n
+
2
2
−
P
n
−
1
2
−
P
n
−
3
2
{\displaystyle \sum _{m=0}^{n}P_{m}^{2}=P_{n+2}^{2}-P_{n-1}^{2}-P_{n-3}^{2}}
∑
m
=
0
n
P
m
2
P
m
+
1
=
P
n
P
n
+
1
P
n
+
2
{\displaystyle \sum _{m=0}^{n}P_{m}^{2}P_{m+1}=P_{n}P_{n+1}P_{n+2}}
∑
m
=
0
n
P
m
P
m
+
2
=
P
n
+
2
P
n
+
3
−
1.
{\displaystyle \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
.
{\displaystyle P_{n}^{2}-P_{n+1}P_{n-1}=P_{-n-7}.}
巴都萬數列跟二項式係數之和有關：
∑
2
m
+
n
=
k
(
m
n
)
=
P
k
−
2
.
{\displaystyle \sum _{2m+n=k}{m \choose n}=P_{k-2}.}
估計值[编辑]
x
3
−
x
−
1
=
0
{\displaystyle x^{3}-x-1=0}
有三個根：唯一的實數根
p
{\displaystyle p}
（即銀數）和兩個複數根
q
{\displaystyle q}
和
r
{\displaystyle r}
。
P
n
=
p
n
(
3
p
2
−
1
)
+
q
n
(
3
q
2
−
1
)
+
r
n
(
3
r
2
−
1
)
.
{\displaystyle 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
{\displaystyle q}
和
r
{\displaystyle r}
的絕對值都少於1，當
n
{\displaystyle n}
趨近無限，其冪會趨近0。因此，對於很大的
n
{\displaystyle n}
，可以以下面的公式估計：
P
n
≈
p
n
(
3
p
2
−
1
)
=
p
n
4.264632...
.
{\displaystyle P_{n}\approx {\frac {p^{n}}{\left(3p^{2}-1\right)}}={\frac {p^{n}}{4.264632...}}.}
從上面的公式亦知
P
n
+
1
P
n
{\displaystyle {\frac {P_{n+1}}{P_{n}}}}
的值趨近銀數。
整數分拆上的定義[编辑]
P
n
{\displaystyle P_{n}}
可以用不同的整數分拆來定義。
P
n
{\displaystyle P_{n}}
是將
n
+
2
{\displaystyle n+2}
寫成一個有序、每項是2或3的和式的方法的數目。例如
P
6
=
4
{\displaystyle P_{6}=4}
，有4種方法將8寫成這類和式：
2+2+2+2 ; 2+3+3 ; 3+2+3 ; 3+3+2
P
2
n
−
2
{\displaystyle P_{2n-2}}
是將
n
{\displaystyle n}
寫成一個有序且式中沒有項為2的和式的方法的數目。例如
P
5
×
2
−
2
=
P
8
=
7
{\displaystyle 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
{\displaystyle P_{n}}
是將
n
{\displaystyle n}
寫成一個有序且「回文型」且式中沒有項為2的和式的方法的數目。例如
P
9
=
9
{\displaystyle 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
{\displaystyle 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
{\displaystyle P_{n}}
是將
n
+
4
{\displaystyle n+4}
寫成一個有序的、每項除以3都餘2的和式的方法的數目。例如
P
7
=
5
{\displaystyle 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
)
=
1
+
x
1
−
x
2
−
x
3
.
{\displaystyle G(P_{n};x)={\frac {1+x}{1-x^{2}-x^{3}}}.}
它可以用於證明巴都萬數跟幾何級數的項的積的等式，例如：
∑
m
=
0
∞
P
n
2
n
=
12
5
.
{\displaystyle \sum _{m=0}^{\infty }{\frac {P_{n}}{2^{n}}}={\frac {12}{5}}.}
多項式[编辑]
巴都萬數列可以一般化成一個多項式的集。
P
n
(
x
)
=
{
1
,
if
n
=
0
x
,
if
n
=
1
x
2
,
if
n
=
2
x
P
n
−
2
(
x
)
+
P
n
−
3
(
x
)
,
if
n
≥
3
{\displaystyle 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
{\displaystyle P_{0}(x)=1\,}
P
1
(
x
)
=
x
{\displaystyle P_{1}(x)=x\,}
P
2
(
x
)
=
x
2
{\displaystyle P_{2}(x)=x^{2}\,}
P
3
(
x
)
=
x
2
+
1
{\displaystyle P_{3}(x)=x^{2}+1\,}
P
4
(
x
)
=
x
3
+
x
{\displaystyle P_{4}(x)=x^{3}+x\,}
P
5
(
x
)
=
x
3
+
x
2
+
x
{\displaystyle P_{5}(x)=x^{3}+x^{2}+x\,}
P
6
(
x
)
=
x
4
+
2
x
2
+
1
{\displaystyle P_{6}(x)=x^{4}+2x^{2}+1\,}
P
7
(
x
)
=
x
4
+
2
x
3
+
x
2
+
x
{\displaystyle P_{7}(x)=x^{4}+2x^{3}+x^{2}+x\,}
第
n
{\displaystyle n}
個巴都萬數即
P
n
(
1
)
{\displaystyle 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
;
.
.
.
{\displaystyle 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
{\displaystyle P_{0,1,2}=1;P_{6}=2^{2};P_{9}=3^{2};P_{11}=4^{2};P_{15}=7^{2}}
参考文献[编辑]
^ Weisstein, Eric W. (编). Padovan Sequence. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
^ Richard Padovan. Dom Hans van der Laan: modern primitive: Architectura & Natura Press, ISBN 9789071570407.
外部連結[编辑]
Padovan Sequence （页面存档备份，存于互联网档案馆）（MathWorld）
Tales of a Neglected Number，艾恩·史都華在雜誌發表的文章
學生科技網--中學生科技：美丽的螺旋线 黄金分割漫谈之三，李颍伯
Dom Hans Van Der Laan And The Plastic Number （页面存档备份，存于互联网档案馆）, Richard Padovan