Problem 519 「三色コイン噴水」

隙間なく積まれた1段以上のコインの段があり, その上の段にあるコイン全てが下の段のちょうど2つのコインと接しているようなコインの配置をコインの噴水(fountain) と呼ぶ. n 個のコインによる配置可能な噴水の数を f(n) としよう. 4個のコインの場合3つの可能な配置がある:

この結果 f(4) = 3, そしてさらに f(10) = 78 となる.

n 個のコインによる f(n) 個の噴水全てを, 2つの接するコインが同じ色にならないという条件のもとに三色に塗り分ける配色の数を T(n) としよう. 4個のコインからなる3個の妥当な噴水のうちの1つに対する可能な塗り分け方は以下のようになる:

T(4) = 48, そして T(10) = 17760 がすでに与えられている.

T(20000) の末尾9桁を求めよ.


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS