CodeIQ：取り違えは何通り？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「取り違えは何通り？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

一人一台のパソコンを支給されている、社員N人の会社があります。
このパソコンは見た目がすべて同じため、他の人のパソコンを間違って持ち帰ってしまう場合がありました。
N人全員が他人のパソコンを持って帰ってしまうような組み合わせが何通りあるかを求めてください。
使用するプログラミング言語は問いません。
なお、出力は64bit整数に収まります。

【入出力サンプル】
Input

5

Output

44

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# OEIS A000166
def solve(n)
	if n == 0 then return 1
	else return n * solve(n-1) + (-1)**n
	end
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	p solve(line.to_i)
end

解説

多分、自力で考えると難しい（数学能力が要求される）です。
私は早々に自力で考えるのを諦めました。

やったこと

問題を言い換えると、0..(n-1)の数字の並び方の全パターンを列挙した時に添字番号と値が一つも同じにならないパターンの数を求めると言う問題です。
この数列は必ずOEISにあるだろうと思い、総当たりで条件を満たすパターンを数えるプログラムを作成しました。Rubyには順列を列挙する関数があるので容易にできます。結果の数列をOEISで検索した結果がA000166で、そのFomulaにあったもっとも簡単な式を実装しました。

solve()

OEISで見つけた数式は次の通りです。これをそのまま実装しました。
a(0)=1, a(n)=n*a(n-1)+(-1)ⁿ

雑感

実は少しだけ自力でやろうと考えました。全パターンはn!で、そのうち2つだけが一致しない、3つだけが一致しない、…、と考えてやめました。最初に書いた通り、このくらい綺麗に数学の問題として言い換えられるならOEISに必ずあるだろうと思ったので。
私が実装した式もよく見るとn!に似ています（a(0)=1, a(n)=n*a(n-1)だとn!です）。でもnが奇数の場合だけ-1することで答えになる理由はわかりません。