パドヴァンのシーケンス

数論において、パドヴァン数列は、初期値によって 定義される整数 P ( n )の列である^[1]。

$${\displaystyle P(0)=P(1)=P(2)=1,}$$

そして再帰関係

$${\displaystyle 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、...（OEISのシーケンスA000931）

パドヴァン数列は、リチャード・パドヴァンにちなんで名付けられました。彼は1994年のエッセイ「ドム・ハンス・ファン・デル・ラーン：モダン・プリミティブ」の中で、この数列をオランダの建築家ハンス・ファン・デル・ラーンが発見したと述べています。^[2]この数列は、1996年6月のサイエンティフィック・アメリカンのコラム「数学的レクリエーション」でイアン・スチュワートによって説明されました。[ ^3]彼はまた、著書の1つ「数学ヒステリー：数学の楽しいゲーム」でもこの数列について書いています。 ^[4]

上記の定義は、Ian Stewart とMathWorldによって与えられたものです。他のソースでは、シーケンスが異なる場所から始まる場合があります。その場合、この記事のいくつかの恒等式は、適切なオフセットで調整する必要があります。

螺旋では、各三角形が他の2つの三角形と1辺を共有しており、パドヴァン数列が再帰関係も満たしていることを視覚的に証明している。

${\displaystyle P(n)=P(n-1)+P(n-5)}$

これを出発点として、定義的再発と他の再発が発見されるにつれて、繰り返し置き換えることで無限の数のさらなる再発を作り出すことができる。${\displaystyle P(m)}$${\displaystyle P(m-2)+P(m-3)}$

ペラン列は初期値が異なりますが、パドヴァン列と同じ再帰関係を満たします。

ペラン配列は、次の式によってパドヴァン配列から得られます。

${\displaystyle \mathrm {Perrin} (n)=P(n+1)+P(n-10).\,}$

再帰関係によって定義される任意の数列と同様に、m <0のパドヴァン数P ( m )は、再帰関係を次のように書き直すことによって定義できます。

${\displaystyle P(m)=P(m+3)-P(m+1),}$

m = −1から始めて逆方向に作業し、P ( m )を負のインデックスに拡張します。

パドヴァン数列の最初のn項の合計はP ( n  +5)より2小さい、つまり

${\displaystyle \sum _{m=0}^{n}P(m)=P(n+5)-2.}$

交互の項の合計、3 つ目の項ごとの合計、および 5 つ目の項ごとの合計も、シーケンス内の他の項と関連しています。

${\displaystyle \sum _{m=0}^{n}P(2m)=P(2n+3)-1}$ OEIS : A077855

${\displaystyle \sum _{m=0}^{n}P(2m+1)=P(2n+4)-1}$

${\displaystyle \sum _{m=0}^{n}P(3m)=P(3n+2)}$ OEIS : A034943

${\displaystyle \sum _{m=0}^{n}P(3m+1)=P(3n+3)-1}$

${\displaystyle \sum _{m=0}^{n}P(3m+2)=P(3n+4)-1}$

${\displaystyle \sum _{m=0}^{n}P(5m)=P(5n+1).}$ OEIS :A012772住所:

パドヴァン数列の項の積を含む和は、次の恒等式を満たします。

${\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(m+1)=P(n)P(n+1)P(n+2)}$

${\displaystyle \sum _{m=0}^{n}P(m)P(m+2)=P(n+2)P(n+3)-1.}$

パドヴァン数列は、

${\displaystyle P(n)^{2}-P(n+1)P(n-1)=P(-n-7).\,}$

パドヴァン数列は、次の恒等式によって 二項係数の和と関連しています。

${\displaystyle P(k-2)=\sum _{2m+n=k}{m \choose n}=\sum _{m=\lceil k/3\rceil }^{\lfloor k/2\rfloor }{m \choose k-2m}.}$

たとえば、k = 12 の場合、2 m  +  n = 12 で ( m、  n ) のペアの値は(6, 0)、(5, 2)、(4, 4) となり、次のようになります。

${\displaystyle {6 \choose 0}+{5 \choose 2}+{4 \choose 4}=1+10+1=12=P(10).\,}$

パドヴァン数列は、方程式の根の累乗で表すことができる^[1]。

${\displaystyle x^{3}-x-1=0.\,}$

この方程式には3つの根があります。1つの実根p （塑性比として知られています）と2つの複素共役根qとrです。^{[5]これら3つの根を考えると、パドヴァン数列は}p、q、rを含む式で表すことができます 。

${\displaystyle P(n)=ap^{n}+bq^{n}+cr^{n}}$

ここでa、b、cは定数である。^[1]

複素根qとrの絶対値は両方とも 1 未満であるため(したがってpはピソット・ヴィジャヤラガヴァン数)、これらの根のべき乗はnが大きい場合に 0 に近づき、ゼロに近づきます。 ${\displaystyle P(n)-ap^{n}}$

すべての に対して、P ( n ) はに最も近い整数です。実際、は上記の定数aの値であり、bとc はそれぞれp をqとrに置き換えることによって得られます。 ${\displaystyle n\geq 0}$${\displaystyle {\frac {p^{5}}{2p+3}}p^{n}}$${\displaystyle {\frac {p^{5}}{2p+3}}}$

パドバン数列の連続する項の比はpに近づき、その値は約 1.324718 になります。この定数は、黄金比がフィボナッチ数列との関係にあるのと同様に、パドバン数列およびペラン数列との関係にあります。

• P ( n ) は 、各項が 2 または 3 である順序付き和としてn + 2を書く方法の数です(つまり、各項が 2 または 3 であるn + 2の合成の数 )。たとえば、P (6) = 4 であり、2 と 3 の順序付き和として 8 を書く方法は 4 つあります。

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

• n をどの項も 2 とならない順序付き和として表す方法の数はP (2 n  − 2) です。たとえば、P (6) = 4 であり、どの項も 2 とならない順序付き和として 4 を表わす方法は 4 つあります。

4 ; 1 + 3 ; 3 + 1 ; 1 + 1 + 1 + 1

• n を、どの項も 2 でない回文順序和として表す方法の数はP ( n ) です。たとえば、P (6) = 4 であり、6 をどの項も 2 でない回文順序和として表す方法は 4 つあります。

6; 3 + 3 ; 1 + 4 + 1 ; 1 + 1 + 1 + 1 + 1 + 1

• n を各項が奇数かつ1 より大きい順序付き和として表す方法の数はP ( n  − 5) に等しい。たとえば、P (6) = 4 であり、11 を各項が奇数かつ 1 より大きい順序付き和として表す方法は 4 つある。

11; 5 + 3 + 3 ; 3 + 5 + 3 ; 3 + 3 + 5

• n を各項が 2 mod 3 と一致する順序付き和として表す方法の数はP ( n − 4)に等しい 。たとえば、P (6) = 4 であり、10 を各項が 2 mod 3 と一致する順序付き和として表す方法は 4 つある。

8 + 2 ; 2 + 8 ; 5 + 5 ; 2 + 2 + 2 + 2 + 2

パドヴァン数列の 生成関数は

${\displaystyle G(P(n);x)={\frac {1+x}{1-x^{2}-x^{3}}}.}$

これは、次のような幾何学的項を含むパドヴァン数列の積を含む恒等式を証明するために使用できます。

${\displaystyle \sum _{n=0}^{\infty }{\frac {P(n)}{2^{n}}}={\frac {12}{5}}.}$

${\displaystyle \sum _{n=0}^{\infty }{\frac {P(n)}{\alpha ^{n}}}={\frac {\alpha ^{2}(\alpha +1)}{\alpha ^{3}-\alpha -1}}.}$

フィボナッチ数がフィボナッチ多項式 と呼ばれる多項式の集合に一般化できるのと同様に、パドバン数列数もパドバン多項式に一般化できます。

次のような簡単な文法を定義します。

変数 : ABC

定数 : なし

開始  :A

ルール  : (A → B)、(B → C)、(C → AB)

このリンデンマイヤー システムまたはL システムでは、次の文字列のシーケンスが生成されます。

n = 0 : A

1 の場合

2 の場合

n = 3 : AB

n = 4 : 紀元前

n = 5 : CAB

n = 6 : ABBC

n = 7 : BCCAB

n = 8 : CABABBC

各文字列の長さを数えると、パドヴァン数が得られます。

1、1、1、2、2、3、4、5、...

また、各文字列のA、B、Cの数を数えると、 n番目の文字列にはP ( n −  5)個のA、P ( n  − 3)個のB、P ( n  − 4)個のCがあります。BBペアとCCペアの数もパドバン数です。

一連の 3 次元直方体の角を接続することで螺旋を形成できます。これがパドバン直方体螺旋です。この螺旋の連続する辺の長さは、パドバン数に2 の平方根を掛けた長さになります。

アーヴ・ウィルソンは論文「メルー山の天秤」^[6]の中でパスカルの三角形の特定の対角線（図参照）を観察し、1993年に紙に描きました。パドヴァン数は1994年に発見されました。ポール・バリー（2004）は、これらの対角線が対角数を足し合わせることでパドヴァン数列を生成することを観察しました。^[7]

• イアン・スチュワート、「コンピュータによる年代測定のガイド（フィードバック）」、サイエンティフィック・アメリカン、第 275 巻、第 5 号、1996 年 11 月、118 ページ。

• OEIS配列 A000931 (パドヴァン配列)
• パドヴァンシーケンス計算機