1O12
限定減縮巡回指標 (RSCI) 法による数え上げとフィボナッチ数
 藤田 眞作
湘南情報数理化学研究所[はじめに] 置換様式に制限を設けない数え上げについては，一般的な方法を開発して，USCI (Unit-SubducedCycle-Index) 法と名づけており，概要をモノグラフとして報告している [1, 2]．立体障碍やそのほかの制限を考慮にいれた数え上げについても，限定減縮巡回指標 (RSCI: Restricted-Subduced-Cycle-Iindex) 法を開発
「嵩高いリガンドが，立体障害のために，隣の位置には置換し得ない」という制限している [3–8]．今回は，のもとにおこなった数え上げ [9–11] が，フィボナッチ数と本質的な関係があることをあきらかにする．
[領域指示変数と領域判別式の導入による限定 SCI-CF] 立体障害によって，隣の位置にリガンドが置換し得ないという条件を考慮するために，隣の位置を検出するための領域指示変数 (territory indicator) を導入する[9–11]．骨格に含まれる頂点 (置換位置) に 1, 2, . . . , v と番号をふり，領域指示変数をダミー変数 x1 , x2 , . . . , xv(iα )として割り当てる．減縮によって生じた軌道 Δ jkβ に含まれる領域指示変数の積:(iα )t jk (x1 , . . . , xv )(1)(iα ) (iα )(iα )t (x1 , . . . , xv ) を各軌道に割り当てる．これにより，軌道 Δ jkβ に含まれる位置が示される．
jk jk
(iα )
(iα ) (iα )通常の $d のかわりに 1 + $d t jk (x1 , . . . , xv ) を代入して，次に示す領域判別式 (territory discriminant) を定jkjkを考えて，$d義する [9–11]．
(iα )DSCI-CF(G j ; $d jk , x1 , x2 , . . . , xv ) =αis(iα ) ZC(G(/Gi ) ↓ G j ; $d jk )
∏ α∏=1i=1αi =0(2)(iα )(iα ) (iα )=1+$d t jk (x1 ,...,xv )
jkjk

$d

この式を展開して生ずる多項式の中から，制限条件に合致する単項式を選ぶ．このため，隣合う頂点の集合(adjacency set, AS) を次のように定義する．
AS = {{k, l} | for all adjacent vertices k and l}(3)

これは，辺の集合に等しい．式 2 に含まれる単項式の中から，AS に由来する xk xl を含むものを除去すれば，所望の単項式が残る．さらに，領域指示変数の部分を除去する操作により，次に示す限定 SCI-CF (RSCI-CF:restricted subduced cycle index chirality fittingness) が得られる．



(iα )
(iα )
SCI-CF(G j ; $d jk ) = DSCI-CF(G j ; $d jk , x1 , x2 , . . . , xv )


(4)
xk xl =0 | ∀{k,l}∈AS
then xi =1(i=1,...v)

これは，通常の SCI-CF から，制限条件に適する軌道のみを選択したことに相当している [9–11]．

[組合せ論とフィボナッチ数] パスカルの三角形について，浅い対角方向の和をとると，フィボナッチ数がえられることは Lucas によって報告されている [12]．パスカルの三角形を左寄せにして，その様子を示したのが図 1 である．
パスカルの三角形とフィボナッチ数の関係は，次の公式であらわされる．

F(n)
 n−12 n−k−1
k= ∑k=0(5)たとえば，n = 7 のところは次のようになる．

∑13
n−k−1
k——1
6

5
5 

64

1
3 01230 1 1 2 3 5 8 13 21 34 フィボナッチ数
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28
図 1: Sum of “shallow” diagonals of Pascal’s triangle
ここにあらわれる組合せの個数は，k 個の黒丸をおくとすると，n − k − 3 個の間隔 (白丸 n − k − 2 個) の前
となる．たとえば，後を考えて，n − k − 1 (= n − k − 3 + 2) の場所に黒丸を割り込ませる組合せの数 n−k−1
kn = 7，k = 2 の場合は，白丸 7 − 2 − 2 = 3 となり，7 − 2 − 1 = 4 の場所に黒丸 2 個を割り込ませることになるから， 42 = 6 がえられる．
[RSCI 法の問題に帰着] 限定 SCI 法 (RSCI 法: restricted-subduced-cycle-index method) の問題に帰着するために，図形的にあらわすと，eeeee(= 7 − 2) の収納場所に，白丸 gと黒丸 wを置くことを考える．上記の組合せの問題は，「黒丸が隣接する位置に置換しない」という制限条件を課した RSCI 法の問題 [9–11] と等価になる (ただし，対称性は考えない)．このような制限条件のもとで許容される配置は次のようになる．総計は 13 となり，フィボナッチ数 F (7) = f (5) に一致する (図 1 の該当する斜線を参照)．のような骨格を考えて，5 個

n=0
n=1
n=2
n=3ggggg
wgggg
wgwgg
wgwgw

gwggg

ggwgg

gggwg

ggggw

wggwg

wgggw

gwgwg

gwggw

6
=1
05
=51
ggwgw 4 =623
3 =1

対称性を考えると，たとえば n = 1 の最初と最後の配置は，同じとみなさなければならないが，フィボナッチ数を求める場合は，別物とみなす．このことは，対称性を C1 (無対称) と考えていることになる．

[フィボナッチ数を RSCI 法で求める] n 個の格納場所が直線状に並んだ次のような骨格を考えよう．
1 2 3ne e e ··· e

この骨格に白丸 gと黒丸 wを置くとし，黒丸が隣り合わないような配置の個数を求める．
通常の SCI (キラリティーは考慮外) は，C1 の場合には次のように求められる:SCI(C1 ; s1 ) = sn1(6)

ただし，キラリティ適合性を考慮に入れないので，$d jk は減縮して，単一の s1 と考えてよい．
式 2 に従って，式 6 に対応する領域判別式 (territory discriminant) を求めると次のようになる．
nDSCI(C1 ; s1 , x1 , x2 , . . . , xn ) = ∏ (1 + s1 xv )

(7)

v=1

この式から，式 4 に従って，RSCI を求めると次のようになる．


SCI(C1 ; s1 ) = DSCI(C1 ; s1 , x1 , x2 , . . . , xn )

xk xl =0 | ∀{k,l}∈ASthen xi =1(i=1,...n)(8)

式 8 は，s1 をダミー変数とする母関数である．この母関数 (式 8) における sv1 の係数は，n 個の収納場所をもつ骨格に v 個の黒丸を隣り合わないように置く配置の個数である．

s1 = 1 とおくと，フイボナッチ数 F (n+2) がえられる．
F (n+2) = f (n) = SCI(C1 ; 1)(9)

たとえば，n = 5 の場合は，式 7 および式 8 を用いて RSCI を実際に計算すると，次の母関数がえられる．

SCI(C1 ; s1 ) = 1 + 5s1 + 6s21 + s31(10)s1 = 1 とおくと，フイボナッチ数 F (7) がえられる．
F (7) = f (5) = SCI(C1 ; 1) = 13(11)[漸化式] 上記のように n を固定した場合の領域判別式 7 を個別に計算することによって，n ごとの母関数とフィボナッチ数を求めることができる．ここでは，さらに漸化式をもとめて，RSCI 法による計算とフィボナッチ数の計算とが本質的に関係していることを説明する．
領域判別式 7 において，xv のみを残すように RSCI (cf. 式 8) が計算できたとする:
nf (n) (s1 , xn ) = ∑ (αv + βv xn )sv1(12)v=1

ただし，xn は領域指示変数，s1 はダミー変数．上限のところでは，αn = 0 である．式 8 と異なるのは，xnが残っている点である．次の n + 1 の項は，次のようになる．

f(n+1)(s1 , xn+1 ) ==f(n)n(s1 , xn )(1 + s1 xn+1 )

n=(αv + βv xn )sv1 (1 + s1 xn+1 )

xn xn+1 =0,xn =1v=1xn xn+1 =0,xn =1∑∑ (αv + βv )sv1 + αv sv+11 xn+1 )

(13)

v=1

条件 xn xn+1 = 0 は，黒丸が隣合わないようにするためである．さらに，xn = 1 とおき，領域指示変数 xn+1を残すようにする．αn = βn+1 ，αn+1 = 0 などと置き換えたうえで，上限を v = n + 1 となるように，sv1 の級数として並べ替える．
n+1f (n+1) (s1 , xn+1 ) = ∑ (αv + βv xn+1 )sv1(14)v=1式 12 と式 14 を比較すると同じ形をしており，漸化式がえられたことになる．この漸化式は，xn = 1 と置いて s1 のみを残すと，フィボナッチ数列をあたえる母関数 f (n) (s1 , 1) (cf. 式 12) となる[漸化式がフィボナッチ数列を与えることの証明] 同様にして，次の n + 2 項を計算すると次のようになる．
f (n+2) (s1 , xn+2 ) ==f (n) (s1 , xn ) × (1 + s1 xn+1 )(1 + s1 xn+2 )| xn xn+1 =0,xn+1 xn+2 =0,(xn =1,xn+1 =1)

f (n) (s1 , xn )(1 + s1 xn+1 ) + f (n) (s1 , xn )s1 xn+2  xn xn+1 =0,xn+1 xn+2 =0,(xn =1,x=f (n+1) (s1 , xn+1 ) + f (n) (s1 , xn )s1 xn+2n+1
 xn xn+1 =0,xn+1 xn+2 =0,=1)(15)(xn =1,xn+1 =1)

ただし，xn xn+1 = 0 および xn+1 xn+2 = 0 の条件は，黒丸が隣り合ったときに消去することをあらわす．この消去操作ののち，xn = 1, xn+1 = 1, xn+2 = 1 とおくと，RSCI の母関数としての漸化式がえられる:f (n+2) (s1 , 1) = f (n+1) (s1 , 1) + f (n) (s1 , 1)s1

(16)

さらに，s1 = 1 とおくと，次の漸化式がえられる:f (n+2) (1, 1) = f (n+1) (1, 1) + f (n) (1, 1)(17)

この漸化式は，フィボナッチ数列の漸化式と一致している．

[計算結果] 漸化式 12 をもとに，Maple 言語でプログラミングして，実際に計算した結果を表 1 に示す．
表 1 に示した母関数 (式 8 に相当) における sv1 の係数は，n 個の収納場所をもつ骨格に v 個の黒丸を隣り合わないように置く配置の個数である．図 1 も参照のこと．また，表 1 の右端の列に示すように，s1 = 1 とおくとフィボナッチ数を与える．ただし， f (n) = F (n+2) ．

表 1: フィボナッチ数列をあたえる母関数の逐次計算
母関数 f (n) (s1 , 1)n+2n34561234

1 + s1
1 + 2s1
1 + 3s1 + s21
1 + 4s1 + 3s2178910111213

567891011

1 + 5s1 + 6s21 + s31
1 + 6s1 + 10s21 + 4s31
1 + 7s1 + 15s21 + 10s31 + s41
1 + 8s1 + 21s21 + 20s31 + 5s41
1 + 9s1 + 28s21 + 35s31 + 15s41 + s51
1 + 10s1 + 36s21 + 56s31 + 35s41 + 6s51
1 + 11s1 + 45s21 + 84s31 + 70s41 + 21s51 + s61

1415161718
19202112131415
16171819

1 + 12s1 + 55s21 + 120s31 + 126s41 + 56s51 + 7s61
1 + 13s1 + 66s21 + 165s31 + 210s41 + 126s51 + 28s61 + s71
1 + 14s1 + 78s21 + 220s31 + 330s41 + 252s51 + 84s61 + 8s71
1 + 15s1 + 91s21 + 286s31 + 495s41 + 462s51 + 210s61 + 36s71 + s81
1 + 16s1 + 105s21 + 364s31 + 715s41 + 792s51 + 462s61 + 120s71 + 9s81
1 + 17s1 + 120s21 + 455s31 + 1001s41 + 1287s51 + 924s61 + 330s71 + 45s81 + s91
1 + 18s1 + 136s21 + 560s31 + 1365s41 + 2002s51 + 1716s61 + 792s71 + 165s81 + 10s91
1 + 19s1 + 153s21 + 680s31 + 1820s41 + 3003s51 + 3003s61 + 1716s71 + 495s81 + 55s91 + s101377610987
15972584
4181
6765
10946

222017711

25

231 + 20s1 + 171s21 + 816s31 + 2380s41 + 4368s51 + 5005s61 + 3432s71 + 1287s81 + 220s91 + 11s101(中略)1 + 23s1 + 231s21 + 1330s31 + 4845s41 + 11628s51 + 18564s61 + 19448s71
1112+ 12870s81 + 5005s91 + 1001s10
1 + 78s1 + s1

フィボナッチ数

23581321345589
14423375025

形式的に，F (1) = f (−1) = 1, F (2) = f (0) = 1 とおいて，RSCI の母関数としての漸化式 16 を適用すれば，F (3) = f (1) = 1 + s1 および F(4) = f (2) = 1 + 2s1 がえられる (表 1 参照)．順次計算して，F (7) = f (5) についても，次のように計算できる．
f (4) (s1 , 1) + f (3) (s1 , 1)s1= (1 + 4s1 + 3s21 ) + (1 + 3s1 + s21 )s1= 1 + 5s1 + 6s21 + s31 = f (5) (s1 , 1)

(18)

このことは，漸化式 12 のかわりに，漸化式 16 を用いて順次計算しても，表 1 の結果がえられることを示している．

[参考文献][1] S. Fujita, “Symmetry and Combinatorial Enumeration in Chemistry,” Springer-Verlag, Berlin-Heidelberg (1991).
[2] S. Fujita, “Diagrammatical Approach to Molecular Symmetry and Enumeration of Stereoisomers,” University of Kragujevac, Faculty of Science, Kragujevac (2007).
[3] S. Fujita, Bull. Chem. Soc. Jpn., 85, 282–304 (2012).
[4] S. Fujita, Bull. Chem. Soc. Jpn., 85, 439–449 (2012).
[5] S. Fujita, MATCH Commun. Math. Comput. Chem., 69, 263–290 (2013).
[6] S. Fujita, MATCH Commun. Math. Comput. Chem., 69, 291–310 (2013).
[7] S. Fujita, MATCH Commun. Math. Comput. Chem., 69, 311–332 (2013).
[8] S. Fujita, MATCH Commun. Math. Comput. Chem., 69, 333–354 (2013).
[9] S. Fujita, J. Comput. Chem. Jpn., 11, 131–139 (2012).
[10] S. Fujita, J. Comput. Chem. Jpn., 11, 140–148 (2012).
[11] 藤田眞作, 日本コンピュータ化学会 2011 秋季年会, 1O05 (2011), 置換様式の制限を考慮した化合物の数え上げ.
[12] E. Lucas, “Théorie des Nombres,” Gauthier-Villars et Fils, Paris (1891).