巴都萬數列

维基百科,自由的百科全书
跳转至: 导航搜索

巴都萬數列(Padovan Sequence)是一個整數數列,由起始數值P_0=P_1=P_2=1遞歸關係P_{n} = P_{n-2} + P_{n-3}定義。

首數個值為1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37 ...(OEIS:A000931

此數列以建築師理察·巴都萬命名,他的論文Dom(1994年)提及Hans Van Der Laan應用銀數在建築方面。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(即銀數)和兩個複數qr

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)}.

因為qr的絕對值都少於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

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寫成一個有序且「回文型」且式中沒有項為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_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)

其他特質[编辑]

外部連結[编辑]