ペラン数

ペラン数（）とは、以下の漸化式で定義される数である。
formula_1
また、これによって得られる以下の数列をペラン数列と呼ぶ。
n-頂点の閉路グラフにおける異なる極大独立集合の個数は"n"番目のペラン数となる
歴史.
1878年にはエドゥアール・リュカが
、1899年にはR. Perrin が
この数列について言及している。1982年にはAdamsとShanksがこの数列について詳しく調べ、ペラン数列と名付けた
母関数.
ペラン数列の母関数は以下のようになる。
Binetの公式.
ペラン数は、以下の方程式の解の累乗を用いて表すことが出来る。
この方程式は3つの解を持ち、1つは実数解（"p" とする、プラスチック数と呼ばれる）、2つは複素共役な解（"q", "r" とする）である。これらを用いて、フィボナッチ数列におけるBinetの公式と同様の公式を得ることが出来る。
複素解 "q", "r" の絶対値は1より小さいので、 "n" を大きくすれば "q^n", "r^n" は0に近づく。従って、十分大きな "n" に対しては、公式は以下のように簡略化出来る。
この公式は、大きな "n" に対してペラン数を高速に計算するのに用いられる。ペラン数列の連続する項の比は "p" 、つまりプラスチック数に近づき、その値はおおよそ 1.324718 である。ペラン数列・パドヴァン数列におけるプラスチック数は、フィボナッチ数列における黄金比や、ペル数における白銀比に対応するものとなっている。
乗法公式.
Binetの公式を用いて、 "G"("kn") を "G"("n"−1), "G"("n") , "G"("n"+1) で表すことが出来る。
であるが、これは formula_8 の分解体上の係数を持つ3つの線型方程式であり、逆行列を求めることでformula_9を計算することが出来る。これらを "k" 乗し、和を求めればよい。
magmaでのコードの例を以下に示す。
 P<x> := PolynomialRing(Rationals());
 S<t> := SplittingField(x^3-x-1); 
 P2<y> := PolynomialRing(S);
 p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]);
 Mi:=Matrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1);
 T<u,v,w> := PolynomialRing(S,3);
 v1 := ChangeRing(Mi,T) *Matrix([[u],[v],[w]]);
 [p^i*v1[1,1]^3 + q^i*v1[2,1]^3 + r^i*v1[3,1]^3 : i in [-1..1]];
formula_10とすれば
となる。23という数字は定義多項式の判別式に由来する。
これを用いれば、整数演算によってn番目のペラン数を formula_12 回の乗算で求めることが出来る。
ペラン擬素数.
"P"("n") が "n" で整除できる(割り切れる)ような "n" を列挙すると以下のようになる。
1の後にはしばらく素数が続いている。全ての素数 "p" に対して、 "P"("p") が "p" で割り切れることが証明されている。しかし、その逆は成り立たない。すなわち、"P"("n") が "n" で割り切れるような合成数 "n" が存在する。このような "n" をペラン擬素数（Perrin pseudoprime）と呼ぶ。「ペラン擬素数は存在するか」という疑問はPerrin自身も考察しており、後にAdamsとShanksが最小のペラン擬素数 271441 = 5212 を発見し肯定的に解決された。2番目に小さいペラン擬素数は 904631 = 7 x 13 x 9941 である。10億未満のペラン擬素数は17個存在する。また、無限に多くのペラン擬素数が存在することがJon Granthamによって証明されている。
ペラン素数.
素数であるペラン数をペラン素数（Perrin prime）と呼ぶ（）。
2006年5月にE. W. Weissteinが発見した32,147桁のペラン数 P(263226) はおそらくペラン素数であろうと考えられている。