巴都万数列

巴都万数列（Padovan Sequence）是一个整数数列^[1]，其起始数值跟递归关系定义为：

${\displaystyle P(0)=P(1)=P(2)=1}$

${\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月，艾恩·史都华在《科学美国人》杂志提到这个数列。

递归关系

• ${\displaystyle P_{n}=P_{n-1}+P_{n-5}}$（此关系可从图中见得）
• ${\displaystyle P_{n}=P_{n-2}+P_{n-4}+P_{n-8}}$
• ${\displaystyle P_{n}=P_{n-3}+P_{n-4}+P_{n-5}}$
• ${\displaystyle P_{n}=P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8}}$

佩兰数列满足相同的递归关系。它亦可从巴都万数列定义： ${\displaystyle Perrin_{n}=P_{n+1}+P_{n-10}}$

反巴都万数列

使用递归关系${\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 ...

项的和

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

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

下面是每隔数项的和：

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

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

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

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

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

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

下面的恒等式跟项与项的乘积之和有关：

${\displaystyle \sum _{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_{m+1}=P_{n}P_{n+1}P_{n+2}}$

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

其他恒等式

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

巴都万数列跟二项式系数之和有关：

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

估计值

${\displaystyle x^{3}-x-1=0}$有三个根：唯一的实数根${\displaystyle p}$（即银数）和两个复数根${\displaystyle q}$和${\displaystyle r}$。

${\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)}}.}$

因为${\displaystyle q}$和${\displaystyle r}$的绝对值都少于1，当${\displaystyle n}$趋近无限，其幂会趋近0。因此，对于很大的${\displaystyle n}$，可以以下面的公式估计：

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

从上面的公式亦知${\displaystyle {\frac {P_{n+1}}{P_{n}}}}$的值趋近银数。

整数分拆上的定义

${\displaystyle P_{n}}$可以用不同的整数分拆来定义。

• ${\displaystyle P_{n}}$是将${\displaystyle n+2}$写成一个有序、每项是2或3的和式的方法的数目。例如${\displaystyle P_{6}=4}$，有4种方法将8写成这类和式：

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

• ${\displaystyle P_{2n-2}}$是将${\displaystyle n}$写成一个有序且式中没有项为2的和式的方法的数目。例如${\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

• ${\displaystyle P_{n}}$是将${\displaystyle n}$写成一个有序且“回文型”且式中没有项为2的和式的方法的数目。例如${\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

• 若上述情况改为${\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

• ${\displaystyle P_{n}}$是将${\displaystyle n+4}$写成一个有序的、每项除以3都馀2的和式的方法的数目。例如${\displaystyle P_{7}=5}$，有5种方法将11写成这类和式：

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

生成函数

巴都万数列的生成函数为

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

它可以用于证明巴都万数跟几何级数的项的积的等式，例如：

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

多项式

巴都万数列可以一般化成一个多项式的集。

${\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.}$

首七个巴都万多项式为：

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

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

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

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

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

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

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

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

第${\displaystyle n}$个巴都万数即${\displaystyle P_{n}(1)}$。

其他特质

• 奇偶性：按“奇奇奇偶偶奇偶”的组合重复出现。
• 数列中的质数：${\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）
• 数列中的平方数：${\displaystyle P_{0,1,2}=1;P_{6}=2^{2};P_{9}=3^{2};P_{11}=4^{2};P_{15}=7^{2}}$

参考文献

1. Weisstein, Eric W. (编). Padovan Sequence. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
2. 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