3色の玉がn個ずつ同じ個数だけある。この3n個の玉を一列に並べるとき、 隣り合う色が互いに異なる色の並べ方の総数を計算せよ。
うーむ。なかなか難しい問題ですね。 「こんなのを考えたからってなんになるんでしょうか！」 という声が聞こえてきそうです。（笑）
私もそう思います！ しかしながら、計算できてしまったので計算しておきましょう。 500年後くらいには、なにかの役に立つかもしれません。
プログラムは以下の通りです。
nStagger :: Int -> Int -> Int -> Int -> Int
nStagger l m n k
| (l == 0) && (m == 0) && (n == 0) = 1
| (l < 0) || ( m < 0 ) || ( n < 0 ) = 0
| k == 0 = (nStagger (l-1) m n 1) + (nStagger l (m-1) n 2)
+ (nStagger l m (n-1) 3)
| k == 1 = (nStagger l (m-1) n 2) + (nStagger l m (n-1) 3)
| k == 2 = (nStagger (l-1) m n 1) + (nStagger l m (n-1) 3)
| k == 3 = (nStagger (l-1) m n 1) + (nStagger l (m-1) n 2)
短いプログラムですが、再帰的にしらみつぶしに調べています。 うまくいかなかったら、0としてカウントしています。
計算結果は以下の通りです。
*Main> nStagger 1 1 1 0 6 *Main> nStagger 2 2 2 0 30 *Main> nStagger 3 3 3 0 174 *Main> nStagger 4 4 4 0 1092 *Main> nStagger 5 5 5 0 7188 *Main> nStagger 6 6 6 0 48852 *Main> nStagger 7 7 7 0 339720 *Main> nStagger 8 8 8 0 2403588 *Main> nStagger 9 9 9 0 17236524
三色がそれぞれ1個しかない場合は、明らかで、3!=6通りです。それ以外は、難しいそうですが、 検索エンジンで、「互いに異なる色」で検索すると結構記事があるみたいです。 30通りは、たしかどこかでみたような・・・
一般解は求められているようです。 http://www.research.att.com/~njas/sequences/?q=6%2C30%2C174%2C1092%2C7188&sort=0&fmt=0&language=english&go=Search