巴都萬數列(Padovan Sequence)是一個整數數列[1],其起始數值跟遞歸關係定義為:
![{\displaystyle P(0)=P(1)=P(2)=1}](//wikimedia.org/api/rest_v1/media/math/render/svg/4139c1e031fd43e3c84fe7e9765f9a3be8ac18d0)
![{\displaystyle P(n)=P(n-2)+P(n-3)}](//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月,艾恩·史都華在《科學美國人》雜誌提到這個數列。
使用遞歸關係
可將巴都萬數列推廣到負數項。這樣的定義跟將斐波那契數推廣到反斐波那契數列相似。另一方面,反斐波那契數列取絕對值便和斐波那契數列相等,但反巴都萬數列卻不:
... -7, 4, 0, -3, 4, -3, 1, 1, -2, 2, -1, 0, 1, -1, 1, 0, 0, 1, 0, 1, 1, 1 ...
![{\displaystyle P_{n}^{2}-P_{n+1}P_{n-1}=P_{-n-7}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/373a05f7ffa53c1c09c7bf8be2ffd7612143a46b)
巴都萬數列跟二項式系數之和有關:
![{\displaystyle \sum _{2m+n=k}{m \choose n}=P_{k-2}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/d71f5d8994a66e05d53b48ef7230ad8f418cf84b)
巴都萬數列的生成函數為
![{\displaystyle G(P_{n};x)={\frac {1+x}{1-x^{2}-x^{3}}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/6fe26eef063fd80a0e9ae370dea45f26a92dd7f9)
它可以用於證明巴都萬數跟幾何級數的項的積的等式,例如:
![{\displaystyle \sum _{m=0}^{\infty }{\frac {P_{n}}{2^{n}}}={\frac {12}{5}}.}](//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.}](//wikimedia.org/api/rest_v1/media/math/render/svg/a7d553e84eaf74c8bea258ea71b168e0892cf022)
首七個巴都萬多項式為:
![{\displaystyle P_{0}(x)=1\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/5ae79f3c1f989d47802dddcb9a7d78846631e81a)
![{\displaystyle P_{1}(x)=x\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/5d62f681eb0aa3c05ca4fce7f2090daf24fa3c83)
![{\displaystyle P_{2}(x)=x^{2}\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/ee5a7eac88448ebf7512f8db5d354353f98d38d8)
![{\displaystyle P_{3}(x)=x^{2}+1\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/300ef07f143262770af7615284cd50c87752d5fb)
![{\displaystyle P_{4}(x)=x^{3}+x\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/f50110233b0d2d7c5f8686444d08e3539518504f)
![{\displaystyle P_{5}(x)=x^{3}+x^{2}+x\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/441c54a28775921bc5046f87f245e10ec4903970)
![{\displaystyle P_{6}(x)=x^{4}+2x^{2}+1\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/3365b4fbcd61a2c0e0fe38826e38cf37f7d3fd59)
![{\displaystyle P_{7}(x)=x^{4}+2x^{3}+x^{2}+x\,}](//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}}](//wikimedia.org/api/rest_v1/media/math/render/svg/680afa3656909fbcdbcb6789514a927482aa1cde)
Richard Padovan. Dom Hans van der Laan: modern primitive: Architectura & Natura Press, ISBN 9789071570407.