![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
隙間なく積まれた1段以上のコインの段があり, その上の段にあるコイン全てが下の段のちょうど2個のコインと接しているようなコインの配置をコインの噴水(fountain) と呼ぶ. n 個のコインによる配置可能な噴水の数を f(n) としよう. 4個のコインの場合3個の可能な配置がある:
#ref(): File not found: "p519_coin_fountain.png" at page "Problem 519"
この結果 f(4) = 3, そしてさらに f(10) = 78 となる.
n 個のコインによる f(n) 個の噴水全てを, 2個の接するコインが同じ色にならないという条件のもとに三色に塗り分ける配色の数を T(n) としよう. 4個のコインからなる3個の妥当な噴水のうちの1つに対する可能な塗り分け方は以下のようになる:
#ref(): File not found: "p519_tricolored_coin_fountain.png" at page "Problem 519"
T(4) = 48, そして T(10) = 17760 がすでに与えられている.
T(20000) の末尾9桁を求めよ.
