巴都萬數列




巴都萬數列（Padovan Sequence）是一個整數數列，由起始數值P0=P1=P2=1{displaystyle P_{0}=P_{1}=P_{2}=1}{displaystyle P_{0}=P_{1}=P_{2}=1}和遞歸關係Pn=Pn−2+Pn−3{displaystyle P_{n}=P_{n-2}+P_{n-3}}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月，艾恩·史都華在《科學美國人》雜誌提到這個數列。




以巴都萬數為邊長的等邊三角形組成的螺旋




目录






  • 1 遞歸關係


  • 2 反巴都比數列


  • 3 項的和


  • 4 其他恆等式


  • 5 估計值


  • 6 整數分拆上的定義


  • 7 生成函數


  • 8 多項式


  • 9 其他特質


  • 10 外部連結





遞歸關係




  • Pn=Pn−1+Pn−5{displaystyle P_{n}=P_{n-1}+P_{n-5}}{displaystyle P_{n}=P_{n-1}+P_{n-5}}（此關係可從圖中見得）

  • Pn=Pn−2+Pn−4+Pn−8{displaystyle P_{n}=P_{n-2}+P_{n-4}+P_{n-8}}{displaystyle P_{n}=P_{n-2}+P_{n-4}+P_{n-8}}

  • Pn=Pn−3+Pn−4+Pn−5{displaystyle P_{n}=P_{n-3}+P_{n-4}+P_{n-5}}{displaystyle P_{n}=P_{n-3}+P_{n-4}+P_{n-5}}

  • Pn=Pn−4+Pn−5+Pn−6+Pn−7+Pn−8{displaystyle P_{n}=P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8}}{displaystyle P_{n}=P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8}}


佩蘭數列滿足相同的遞歸關係。它亦可從巴都萬數列定義：
Perrinn=Pn+1+Pn−10{displaystyle Perrin_{n}=P_{n+1}+P_{n-10}}{displaystyle Perrin_{n}=P_{n+1}+P_{n-10}}



反巴都比數列


使用遞歸關係P−n=P−n+3−P−n+1{displaystyle P_{-n}=P_{-n+3}-P_{-n+1}}{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 ...



項的和


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


∑m=0nPm=Pn+5−2.{displaystyle sum _{m=0}^{n}P_{m}=P_{n+5}-2.}{displaystyle sum _{m=0}^{n}P_{m}=P_{n+5}-2.}

下面是每隔數項的和：



∑m=0nP2m=P2n+3−1{displaystyle sum _{m=0}^{n}P_{2m}=P_{2n+3}-1}{displaystyle sum _{m=0}^{n}P_{2m}=P_{2n+3}-1}

∑m=0nP2m+1=P2n+4−1{displaystyle sum _{m=0}^{n}P_{2m+1}=P_{2n+4}-1}{displaystyle sum _{m=0}^{n}P_{2m+1}=P_{2n+4}-1}

∑m=0nP3m=P3n+2{displaystyle sum _{m=0}^{n}P_{3m}=P_{3n+2}}{displaystyle sum _{m=0}^{n}P_{3m}=P_{3n+2}}

∑m=0nP3m+1=P3n+3−1{displaystyle sum _{m=0}^{n}P_{3m+1}=P_{3n+3}-1}{displaystyle sum _{m=0}^{n}P_{3m+1}=P_{3n+3}-1}

∑m=0nP3m+2=P3n+4−1{displaystyle sum _{m=0}^{n}P_{3m+2}=P_{3n+4}-1}{displaystyle sum _{m=0}^{n}P_{3m+2}=P_{3n+4}-1}

∑m=0nP5m=P5n+1.{displaystyle sum _{m=0}^{n}P_{5m}=P_{5n+1}.}{displaystyle sum _{m=0}^{n}P_{5m}=P_{5n+1}.}


下面的恆等式跟項與項的乘積之和有關：



∑m=0nPm2=Pn+22−Pn−12−Pn−32{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_{n+2}^{2}-P_{n-1}^{2}-P_{n-3}^{2}}

∑m=0nPm2Pm+1=PnPn+1Pn+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}^{2}P_{m+1}=P_{n}P_{n+1}P_{n+2}}

∑m=0nPmPm+2=Pn+2Pn+3−1.{displaystyle sum _{m=0}^{n}P_{m}P_{m+2}=P_{n+2}P_{n+3}-1.}{displaystyle sum _{m=0}^{n}P_{m}P_{m+2}=P_{n+2}P_{n+3}-1.}



其他恆等式


Pn2−Pn+1Pn−1=P−n−7.{displaystyle P_{n}^{2}-P_{n+1}P_{n-1}=P_{-n-7}.}{displaystyle P_{n}^{2}-P_{n+1}P_{n-1}=P_{-n-7}.}

巴都萬數列跟二項式係數之和有關：


∑2m+n=k(mn)=Pk−2.{displaystyle sum _{2m+n=k}{m choose n}=P_{k-2}.}{displaystyle sum _{2m+n=k}{m choose n}=P_{k-2}.}


估計值


x3−x−1=0{displaystyle x^{3}-x-1=0}x^{3}-x-1=0有三個根：唯一的實數根p{displaystyle p}p（即銀數）和兩個複數根q{displaystyle q}q和r{displaystyle r}r。


Pn=pn(3p2−1)+qn(3q2−1)+rn(3r2−1).{displaystyle P_{n}={frac {p^{n}}{left(3p^{2}-1right)}}+{frac {q^{n}}{left(3q^{2}-1right)}}+{frac {r^{n}}{left(3r^{2}-1right)}}.}{displaystyle P_{n}={frac {p^{n}}{left(3p^{2}-1right)}}+{frac {q^{n}}{left(3q^{2}-1right)}}+{frac {r^{n}}{left(3r^{2}-1right)}}.}

因為q{displaystyle q}q和r{displaystyle r}r的絕對值都少於1，當n{displaystyle n}n趨近無限，其冪會趨近0。因此，對於很大的n{displaystyle n}n，可以以下面的公式估計：


Pn≈pn(3p2−1)=pn4.264632....{displaystyle P_{n}approx {frac {p^{n}}{left(3p^{2}-1right)}}={frac {p^{n}}{4.264632...}}.}{displaystyle P_{n}approx {frac {p^{n}}{left(3p^{2}-1right)}}={frac {p^{n}}{4.264632...}}.}

從上面的公式亦知Pn+1Pn{displaystyle {frac {P_{n+1}}{P_{n}}}}{displaystyle {frac {P_{n+1}}{P_{n}}}}的值趨近銀數。



整數分拆上的定義


Pn{displaystyle P_{n}}P_{n}可以用不同的整數分拆來定義。



  • Pn{displaystyle P_{n}}P_{n}是將n+2{displaystyle n+2}n+2寫成一個有序、每項是2或3的和式的方法的數目。例如P6=4{displaystyle P_{6}=4}{displaystyle P_{6}=4}，有4種方法將8寫成這類和式：

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


  • P2n−2{displaystyle P_{2n-2}}{displaystyle P_{2n-2}}是將n{displaystyle n}n寫成一個有序且式中沒有項為2的和式的方法的數目。例如P5×2−2=P8=7{displaystyle P_{5times 2-2}=P_{8}=7}{displaystyle P_{5times 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



  • Pn{displaystyle P_{n}}P_{n}是將n{displaystyle n}n寫成一個有序且「回文型」且式中沒有項為2的和式的方法的數目。例如P9=9{displaystyle P_{9}=9}{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


  • Pn{displaystyle P_{n}}P_{n}是將n+4{displaystyle n+4}{displaystyle n+4}寫成一個有序的、每項除以3都餘2的和式的方法的數目。例如P7=5{displaystyle P_{7}=5}{displaystyle P_{7}=5}，有5種方法將11寫成這類和式：

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


生成函數


巴都萬數列的生成函數為


G(Pn;x)=1+x1−x2−x3.{displaystyle G(P_{n};x)={frac {1+x}{1-x^{2}-x^{3}}}.}{displaystyle G(P_{n};x)={frac {1+x}{1-x^{2}-x^{3}}}.}

它可以用於證明巴都萬數跟幾何級數的項的積的等式，例如：


∑m=0∞Pn2n=125.{displaystyle sum _{m=0}^{infty }{frac {P_{n}}{2^{n}}}={frac {12}{5}}.}{displaystyle sum _{m=0}^{infty }{frac {P_{n}}{2^{n}}}={frac {12}{5}}.}


多項式


巴都萬數列可以一般化成一個多項式的集。


Pn(x)={1,if n=0x,if n=1x2,if n=2xPn−2(x)+Pn−3(x),if n≥3{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 }}ngeq 3end{matrix}}right.}{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 }}ngeq 3end{matrix}}right.}

首七個巴都萬多項式為：



P0(x)=1{displaystyle P_{0}(x)=1,}{displaystyle P_{0}(x)=1,}

P1(x)=x{displaystyle P_{1}(x)=x,}{displaystyle P_{1}(x)=x,}

P2(x)=x2{displaystyle P_{2}(x)=x^{2},}{displaystyle P_{2}(x)=x^{2},}

P3(x)=x2+1{displaystyle P_{3}(x)=x^{2}+1,}{displaystyle P_{3}(x)=x^{2}+1,}

P4(x)=x3+x{displaystyle P_{4}(x)=x^{3}+x,}{displaystyle P_{4}(x)=x^{3}+x,}

P5(x)=x3+x2+x{displaystyle P_{5}(x)=x^{3}+x^{2}+x,}{displaystyle P_{5}(x)=x^{3}+x^{2}+x,}

P6(x)=x4+2x2+1{displaystyle P_{6}(x)=x^{4}+2x^{2}+1,}{displaystyle P_{6}(x)=x^{4}+2x^{2}+1,}

P7(x)=x4+2x3+x2+x{displaystyle P_{7}(x)=x^{4}+2x^{3}+x^{2}+x,}{displaystyle P_{7}(x)=x^{4}+2x^{3}+x^{2}+x,}


第n{displaystyle n}n個巴都萬數即Pn(1){displaystyle P_{n}(1)}{displaystyle P_{n}(1)}。



其他特質



  • 奇偶性：按「奇奇奇偶偶奇偶」的組合重覆出現。

  • 數列中的質數：P3,4=2;P5=3;P7=5;P8=7;P14=37;P19=151;P30=3329;P37=23833;...{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;...}{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）

  • 數列中的平方數：P0,1,2=1;P6=22;P9=32;P11=42;P15=72{displaystyle P_{0,1,2}=1;P_{6}=2^{2};P_{9}=3^{2};P_{11}=4^{2};P_{15}=7^{2}}{displaystyle 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




-

Popular posts from this blog

Guess what letter conforming each word

Image
6 $begingroup$ This is an entry in the Fortnightly Topic Challenge #41: Short and Sweet. 1 letter only could be mean anything . With an additional letter in front , could be used as medicine component and something you definitely learn or at least heard once. Add another letter in front , you would possibly hear that many times . Add an additional letter in front , you would found an independent country . With an additional letter, in the end , you would found something related to apple . Add another letter in the end , you would found something bad . Hint: Each letter is unique . word knowledge letters chemistry share | improve this question ...
Read more

Port of Spain

Image
For ports in the country of Spain, see List of ports in Spain. City in City of Port of Spain, Trinidad and Tobago Port of Spain City City of Port of Spain Top to bottom (left to right): Skyline of Port of Spain from Gulf of Paria; National Academy for the Performing Arts, Independence Square, Eric Williams Plaza; MovieTowne, Port of Port of Spain Motto(s):  "We Gather Strength As We Go Along" Port of Spain Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Country   Trinidad and Tobago Jurisdiction City of Port of Spain Settled 1560 Incorporated (town) 1853 Incorporated (city) 1914 Government  • Mayor Joel Martinez  • Governing body City Corporation Area [1]  • City 12 km 2 (5 sq mi) Elevation [2] 66 m (217 ft) Population (2011) [1]  • City 37,074  • Rank 3rd  • Density 3,090/km 2 (8,000/sq mi)...
Read more

Run scheduled task as local user group (not BUILTIN)

Image
0 I am trying to run a scheduled task with User Group (not a single user). This is working fine when I in the field "when running a task, use the following user account:" insert BUILTIN User Group (for example: Administrators or Users). But when I try it with the created Local User Group (example: TestGroup) it is not working. The Users in the TestGroup are the same as in the Administrators group. What could be the problem? Are there some restrictions to the Created User Group compared to BUILTINUsers? scheduled-tasks taskscheduler windowstaskschedule share | improve this question asked Nov 15 '18 at 15:36 Far...
Read more