No.243

$i$ が嫌いな生徒に割り当たっている事象を $P(i)$ とすると, うまく割り当てられない組み合わせの数は,

$$\vert P(0) \cup P(1) \cup \dots \cup P(2) \vert$$

となる. 包除原理より,

$$\begin{align} &\vert P(0) \cup P(1) \cup \dots \cup P(N-1) \vert \\ &\ = \vert P(0) \vert + \vert P(1) \vert + \dots + \vert P(N-1) \vert \\ &\ \ - \vert P(0,1) \vert + \vert P(0,2) \vert + \dots + \vert P(N-2,N-1) \vert \\ &\ \ + \vert P(0,1,2) \vert + \vert P(0,1,3) \vert + \dots + \vert P(N-3,N-2,N-1) \vert \\ &\ \ \dots \end{align}$$

となる. ここで, $i$ が嫌いな生徒の数を $c_i$ とすると,

$$\begin{align} \vert P(i) \vert &= c_i (N-1)! \\ \vert P(i,j) \vert &= c_ic_j (N-2)! \\ \vert P(i,j,k) \vert &= c_ic_jc_k(N-3)! \end{align}$$

となる. よって,

$$c_0 + c_1 + \dots + c_{N-1} \\ c_0c_1 + c_0c_2 + \dots + c_{N-2}c_{N-1} \\ c_0c_1c_2 + c_0c_1c_3 + \dots + c_{N-3}c_{N-2}c_{N-1}$$

を求めることになる. $n$ 個の数字のうち $k$ 個を使った積の和を $A(n, k)$ とすると,

$$A(n, k) = A(n-1, k) + c_{n-1}A(n-1, k-1)$$

となるので, DP でこれを解けばいい.

最後にすべての組み合わせの数 $N!$ からうまく割り当てられない組み合わせの数を引く.