私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「隣の人と異なる仮装」（CodeIQ）を参照してください。
いよいよハロウィンの季節がやってきました。
ハロウィンと言えば仮装ですね。
ただ、せっかく仮装しても他の人と同じ衣装になるのは避けたいもの。
そこで、全員が横一列に並んだときに、隣の人とは異なる仮装をすることにしました。
m 人が仮装をしたとき、衣装の数がちょうど n 種類である「並び方」が何通りあるかを求めてください。
例えば、m = 5, n = 3 のとき、同じ文字が同じ衣装を表すものとすると、以下の7通りの並び方があります。
(1) A B A B C
(2) A B A C A
(3) A B A C B
(4) A B C A B
(5) A B C A C
(6) A B C B A
(7) A B C B C
※衣装の内容は問わないものとし、衣装を入れ替えたものは同じと考えます。
（例：B A B A Cは(1)と同じなのでカウントしない。）
標準入力から m, n が与えられたとき、その並び方が何通りあるかを求め、標準出力に出力してください。
なお、m, n はともに整数で 0 < n < m < 20 を満たすものとします。
【入出力サンプル】
標準入力
5 3
標準出力
7
Rubyで解答しています。
#!/usr/bin/ruby
def binomial(n,k)
ret = 1
for i in (k+1)..n
ret *= i
end
for j in 1..(n-k)
ret /= j
end
return ret
end
def mfrac(n)
ret = 1
for i in 2..n
ret *= i
end
return ret
end
def a008277(n, k)
sum = 0
for i in 0..k
sum += ((-1)**(k-i)) * (i**n) * binomial(k, i)
end
return sum/mfrac(k)
end
# main
while line = gets
line.strip!
next if line.empty?
m,n = line.split.map{|a| a.to_i}
p a008277(m-1, n-1)
end
入力値を数値にしてm-1, n-1をa008277()に渡し、結果を印字します。
OEISのa008277の式を実装したものです。
二項係数を求めます。
nの階乗を求めます。
「区別できるn個のものを区別できないkグループに分類する方法の場合の数は S(n,k) である」と言うのが第二種スターリング数と言うことです。何で、問題の(m-1, n-1)のスターリング数を求めると答えになるのかはよくわかっていません。確かに1〜mを区別できないnグループに分けています（m=5, n=3の例では1〜5をA,B,Cの区別できない3グループに分けている）。何で-1するのかがよくわかりません。必ず1個しか要素のないグループが一つ必要なのかな？
ちなみに、スターリング数と言うものをこの問題で初めて知りました。OEISで調べたらMAPLEか何かのコードにstarling2（みたいな）関数があって、googleで検索したらスターリング数と説明があったのでそれで知りました。