問題
，は自然数で，，を満たすものとする．いま，角柱の個の面に1からまでの番号が書いてあるものとする．この個の面に1面ずつ，異なる色の中から1色ずつ選んでは塗っていく．このとき，どの隣り合う面の組も同一色では塗られない塗り方の数をで表す．
(1) とを求めよ．
(2) のとき，を求めよ．
方針
2つの底面は互いには隣り合わず、各底面はすべての側面と隣り合う。そこで底面2つが同色か異色かで分ける。底面の色を決めると、側面で使える色数がそれぞれ , に決まり、側面 枚は輪状に並ぶので、輪 を 色で隣り合う面が異色になるように塗る数 を使う。この公式を側面に適用し、最後に および を代入する。
解答
まず、輪状に並んだ 個の面を 色で、隣り合う面が同色にならないように塗る数を確認しておく。最初の面の色を1つ固定し、 番目の面の色が最初の面と異なる塗り方の数を とする。最初の面と同じ色になる塗り方の数を とすると であり、 番目が最初の面と異なるようにするには、 番目が最初の面と同じなら 通り、異なるなら 通りである。したがって となる。 から帰納的に が得られる。輪にするには最後の面が最初の面と異なればよいので、最初の色の選び方 通りを掛けて、輪状の 個の面の塗り方は 通りである。
(1)
角柱には、 個の側面と2つの底面がある。2つの底面は互いには隣り合わないが、各底面はすべての側面と隣り合う。したがって、まず2つの底面の色の関係で分ける。
底面2つが同色である場合を考える。その色の選び方は 通りである。側面はどれも底面と隣り合うため、その底面の色を使えない。したがって側面では残り 色を使い、輪状に並んだ 個の側面を隣り合う側面が異色になるように塗る。この数は、上の公式で として である。よってこの場合は 通りである。
次に、底面2つが異色である場合を考える。2つの底面の色の選び方は 通りである。側面はどちらの底面とも隣り合うので、底面で使った2色を使えない。したがって側面で使える色は 色であり、輪状の側面の塗り方は 通りである。この場合は 通りである。
以上より である。 のときは、底面が同色でも異色でも側面を適切に塗ることができず、式からも である。 のときは である。 なので であり、 となる。したがって
である。
(2)
, を上の式に代入する。まず底面2つが同色の場合は 通りである。底面2つが異色の場合は、側面で使える色が2色しかなく、奇数個の輪を2色で交互に塗ることはできない。式でも である。よって である。