ARC009 C - 高橋君、24歳

問題：C - 高橋君、24歳

解答：Submission #13675261 - AtCoder Regular Contest 009

解法：誤って送った友達の組み合わせ数はnCk。
誤って送られた友達を(1, 2, ..., k)とすると、誤って送る送り方は1からnまでの順列(p1, p2, ..., pn)でかつ任意のiに対しpi ≠ i となるような順列の通り数である。このような順列を攪乱順列（もしくは完全順列）と呼ぶ。
攪乱順列の通り数は次のように求めることができる.

①漸化式で解く
an：n項の攪乱順列の通り数とする。まず1の行先がiである場合、すなわちpi = 1である場合を考える。iは2～nのn-1通りある。
そのそれぞれについて、次の2通りを考える。 (1) iの行先が1である場合：1とiが除外され、残りの数は2, 3, ..., i-1, i+1, ..., nのn-2個である。これらの攪乱順列を考えればよいため、a[n-2]通り。
(2) iの行先が1以外である場合：この状態で残りの数は2, 3, ..., i-1, i, i+1, ..., nのn-1個であり、残りの行先は1, 2, ..., i-1, i+1, ..., nのn-1個である。一見攪乱順列でないように見えるが、数iは1に行かないことが分かっているので、数iと数1を同一視することにより、n-1項の攪乱順列と思うことができるため、a[n-1]通り。
よって次のような漸化式を立てることができる。
an =(n-1) * (a[n-1] + a[n-2])

②包除原理で解く
Bi = {(p1, p2, ..., pn) : 1からnの順列, pi = i} とすると、an = n! - |B1 ∨ B2 ∨ ... ∨ Bn| である。
ここで包除原理を適用すると、
|B1 ∨ B2 ∨ ... ∨ Bn| = Σ|Bi| - Σ|Bi ∧ Bj| + Σ|Bi ∧ Bj ∧ Bk| - ...
となる。

Bi ∧ Bj ∧ Bk = {(p1, p2, ..., pn)：1からnの順列, pi = i, pj = j, pk = k} であるため、Σ|Bi ∧ Bj ∧ Bk|は「固定する(i, j, k)の個数 × 固定しない残りの部分の順列の通り数」で求めることができる。
l個の共通部分については、nCl * l!で求めることができる。