1000000D Hypercube 別方針

公式解説と異なる方針を紹介します．

最終的に得られる式は同じですが，包除原理を用いることで直接導出します．

実数 $s$ に対し，$N$ 次元空間内で

$$\begin{cases} \forall i.\; x_i \ge 0 \\ x_1 + \dots + x_N \le s \end{cases}$$

を満たす領域の体積を $V(s)$ とします．

$$V(s) = \begin{cases} s^N/N! & (s \ge 0), \\ 0 & (s < 0) \end{cases}$$

です．

求める体積 $V$ は

$$\begin{cases} \forall i.\; x_i \ge 0 \\ x_1 + \dots + x_N \le K \end{cases}$$

に加えて $\forall i. \; x_i \le 1$ を満たす領域の体積です．各 $i$ に対する条件 $x_i \le 1$ たちに対して包除原理を適用します．$N$ 個中 $k$ 個の条件に違反し他の条件を無視したとすると，違反した $i$ に対して $x_i - 1$ を $x_i$ と置き直すことで条件は

$$\begin{cases} \forall i.\; x_i \ge 0 \\ x_1 + \dots + x_N \le K - k \end{cases}$$

となり（境界の差異は体積 $0$ なので無視できます），これを満たす領域の体積は $V(K - k)$ です．よって

$$\begin{aligned} V &= \sum_{k = 0}^N (-1)^k \binom{N}{k} \cdot V(K - k) \\ &= \sum_{k = 0}^K (-1)^k \binom{N}{k} \cdot V(K - k) \qquad (\because k > K \Longrightarrow V(K - k) = 0 ) \\ &= \sum_{k = 0}^K (-1)^k \binom{N}{k} \frac{(K - k)^N}{N!} \\ \end{aligned}$$

です．