巴都万数列

<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