No.802
\[\begin{align}
B_i &= A_i - (i-1)D_1 - 1 \\
D &= D_2-D_1 \\
M^{\prime} &= M-(N-1)D_1-1
\end{align}\]
とする. こうすることで, 差分が \(D\) 以下で
\[0 \leq B_1 \leq \cdots \leq B_N \leq M^{\prime}\]となる数列の個数を数えればいいことになる.
ここで
\[\begin{align} B_0 &= 0 \\ B_{N+1} &= M^{\prime} \\ C_i &= B_i-B_{i-1} \end{align}\]とすると, \(C_i \leq D \ (1 \leq i \leq N-1)\) かつ \(\sum C_i = M^{\prime}\) となる \(C_i\) の個数を数える問題となる.
\(C_i \leq D\) の条件をはずせば \(M^{\prime}\) を \(N+1\) 個のグループに分割する方法の数となるので, \(\homoprod{N+1}{M^{\prime}}\) 通りである.
ここから \(C_1, C_2, \dots C_{N-1}\) のどれかが \(D+1\) 以上になる個数を引けばいい. すなわち \(C_i\) が \(D+1\) 以上となる事象を \(D_i\) とすると \(\abs{D_1 \cup D_2 \cup \cdots \cup D_{N-1}}\) を求めれはいい. これには包除定理が使え, その個数は
\[\sum_{i=1}^{N-1} (-1)^{i-1} \cdot \combi{N-1}{i} \cdot \homoprod{N+1}{M^{\prime} - i(D+1)}\]となる.