連続する3つの値が禁止された占有問題の一般公式

概要

論文の詳細を見る
拘束付き置換の総数を求める問題を考える. n 次の置換P=([numerical formula])において, a_i は i から始まる連続した3つの値はとれないものとする(a_i≠i, a_i≠i+1, a_i≠i+2, ただし n+1≡1, n+2≡2). 求めるべき置換の総数は, 包含と排除の原理をもちいて U^<(3)>_n = Σ^n_<r=0> (-1)^r c^<(n)>_r (n-r)! と書くことができる. 我々は, コンピュータによる数値実験の結果, 係数 c^<(n)>_r の一般形が c^<(n)>_r = ((3n))/r! [ (3n)^<r-1>-Σ^r_<i=2> (-1)^i f_i(r) (i^^r) (3n)^(r-i) ] + (1+(-1)^n) δn,r と表されることを発見した. ここに, f_i(r) は変数 r についての (i-2) 次多項式である. さらに, 我々は関数 f_i(r) の係数間にもまた簡単な規則のあることを発見した. これらの結果は, c^<(n)>_r < 3 × 10^<10> の範囲において直接に数え上げる方法で求めたものと一致している.
一般社団法人情報処理学会の論文
1996-11-15