以巴都万数为边长的等边三角形组成的螺旋
巴都万数列(Padovan Sequence)是一个整数数列[1],其起始数值跟递归关系定义为:
![{\displaystyle P(0)=P(1)=P(2)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4139c1e031fd43e3c84fe7e9765f9a3be8ac18d0)
![{\displaystyle P(n)=P(n-2)+P(n-3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b4abec62702110888b8f0ca817c6ac3a07185d3)
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)
此数列以建筑师理察·巴都万命名,理察·巴都万把此数列的发现归功于荷兰建筑师汉斯·范·德·兰在1994年发表的论文《Dom. Hans van der Laan : Modern Primitive》[2]。1996年6月,艾恩·史都华在《科学美国人》杂志提到这个数列。
递归关系
(此关系可从图中见得)
![{\displaystyle P_{n}=P_{n-2}+P_{n-4}+P_{n-8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e3bf9764d38b6cdc112362bc7a99e57f402ecb9)
![{\displaystyle P_{n}=P_{n-3}+P_{n-4}+P_{n-5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c21a9bda2288551c77053a5e400f957c3f71d36)
![{\displaystyle P_{n}=P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2300fa2979c087bd8dc8904b224e1c2d8d6b4e94)
佩兰数列满足相同的递归关系。它亦可从巴都万数列定义:
反巴都万数列
使用递归关系
可将巴都万数列推广到负数项。这样的定义跟将斐波那契数推广到反斐波那契数列相似。另一方面,反斐波那契数列取绝对值便和斐波那契数列相等,但反巴都万数列却不:
... -7, 4, 0, -3, 4, -3, 1, 1, -2, 2, -1, 0, 1, -1, 1, 0, 0, 1, 0, 1, 1, 1 ...
项的和
首
项(包括第0项)之和比
少2:
![{\displaystyle \sum _{m=0}^{n}P_{m}=P_{n+5}-2.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5da3266fb80caed61517cd15178e93024a7a5028)
下面是每隔数项的和:
![{\displaystyle \sum _{m=0}^{n}P_{2m}=P_{2n+3}-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f0c634b8e1f6b984dfb6e782bc6b0410cfa8a09)
![{\displaystyle \sum _{m=0}^{n}P_{2m+1}=P_{2n+4}-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/968658c3b586a1eefb9509e1df4a754418df287e)
![{\displaystyle \sum _{m=0}^{n}P_{3m}=P_{3n+2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ea8aa9f0caf8701014c81b1fbff3258751ff289)
![{\displaystyle \sum _{m=0}^{n}P_{3m+1}=P_{3n+3}-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b72210ba7d656338779f98776dae509d494babf0)
![{\displaystyle \sum _{m=0}^{n}P_{3m+2}=P_{3n+4}-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5bbb801ba33e75ce75c090d57e6812acc8f6359)
![{\displaystyle \sum _{m=0}^{n}P_{5m}=P_{5n+1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/893911583a82b4e530e0aff346b19e4d9cf6f65d)
下面的恒等式跟项与项的乘积之和有关:
![{\displaystyle \sum _{m=0}^{n}P_{m}^{2}=P_{n+2}^{2}-P_{n-1}^{2}-P_{n-3}^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4dcbd31bcb757223ad3cfaa6659c4d3a43f4bc9e)
![{\displaystyle \sum _{m=0}^{n}P_{m}^{2}P_{m+1}=P_{n}P_{n+1}P_{n+2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4df222cee3470cb2454af81a0350091ad32b424)
![{\displaystyle \sum _{m=0}^{n}P_{m}P_{m+2}=P_{n+2}P_{n+3}-1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef5109a22b6dba9988c881943f8e0a293cc03028)
其他恒等式
![{\displaystyle P_{n}^{2}-P_{n+1}P_{n-1}=P_{-n-7}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/373a05f7ffa53c1c09c7bf8be2ffd7612143a46b)
巴都万数列跟二项式系数之和有关:
![{\displaystyle \sum _{2m+n=k}{m \choose n}=P_{k-2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d71f5d8994a66e05d53b48ef7230ad8f418cf84b)
估计值
有三个根:唯一的实数根
(即银数)和两个复数根
和
。
![{\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)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6970719fbb5f3181a65fa4e00a62d13b4063c1b6)
因为
和
的绝对值都少于1,当
趋近无限,其幂会趋近0。因此,对于很大的
,可以以下面的公式估计:
![{\displaystyle P_{n}\approx {\frac {p^{n}}{\left(3p^{2}-1\right)}}={\frac {p^{n}}{4.264632...}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b57e08f6f37bb356b4666b329f5904956e51cd8d)
从上面的公式亦知
的值趋近银数。
整数分拆上的定义
可以用不同的整数分拆来定义。
是将
写成一个有序、每项是2或3的和式的方法的数目。例如
,有4种方法将8写成这类和式:
- 2+2+2+2 ; 2+3+3 ; 3+2+3 ; 3+3+2
是将
写成一个有序且式中没有项为2的和式的方法的数目。例如
,有7种方法将5写成这类和式:
- 1+1+1+1+1 ; 1+1+3 ; 1+3+1 ; 3+1+1 ; 4+1 ; 1+4 ; 5
是将
写成一个有序且“回文型”且式中没有项为2的和式的方法的数目。例如
,有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
- 若上述情况改为
,则数列如下:
- 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
是将
写成一个有序的、每项除以3都馀2的和式的方法的数目。例如
,有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}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fe26eef063fd80a0e9ae370dea45f26a92dd7f9)
它可以用于证明巴都万数跟几何级数的项的积的等式,例如:
![{\displaystyle \sum _{m=0}^{\infty }{\frac {P_{n}}{2^{n}}}={\frac {12}{5}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fe491ab79b602cee860bdb0d975ab4c82963283)
多项式
巴都万数列可以一般化成一个多项式的集。
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d553e84eaf74c8bea258ea71b168e0892cf022)
首七个巴都万多项式为:
![{\displaystyle P_{0}(x)=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ae79f3c1f989d47802dddcb9a7d78846631e81a)
![{\displaystyle P_{1}(x)=x\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d62f681eb0aa3c05ca4fce7f2090daf24fa3c83)
![{\displaystyle P_{2}(x)=x^{2}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee5a7eac88448ebf7512f8db5d354353f98d38d8)
![{\displaystyle P_{3}(x)=x^{2}+1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/300ef07f143262770af7615284cd50c87752d5fb)
![{\displaystyle P_{4}(x)=x^{3}+x\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f50110233b0d2d7c5f8686444d08e3539518504f)
![{\displaystyle P_{5}(x)=x^{3}+x^{2}+x\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/441c54a28775921bc5046f87f245e10ec4903970)
![{\displaystyle P_{6}(x)=x^{4}+2x^{2}+1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3365b4fbcd61a2c0e0fe38826e38cf37f7d3fd59)
![{\displaystyle P_{7}(x)=x^{4}+2x^{3}+x^{2}+x\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55ca727f20958b0f451fde9f5b2e5f6b3f8e1198)
第
个巴都万数即
。
其他特质
- 奇偶性:按“奇奇奇偶偶奇偶”的组合重复出现。
- 数列中的质数:
(OEIS:A000931)
- 数列中的平方数:
![{\displaystyle P_{0,1,2}=1;P_{6}=2^{2};P_{9}=3^{2};P_{11}=4^{2};P_{15}=7^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/680afa3656909fbcdbcb6789514a927482aa1cde)
参考文献
外部链接