AtCoder 典型90 015問題 解説補足

典型90問 015 - Don’t be too close

015 - Don't be too close（★6）

1 から N までの整数列において、1つ以上の整数を選択する際に、どの整数もその差が K (≥ 1) 以上となる選び方は何通りあるか？

解説

公式解説にもある通り、選択できない組み合わせは結合していく。

N = 5, K = 2のとき

r-元部分集合 において、その元の数を $${n \lparen k, r \rparen}$$ とすると、

$$
n \lparen k, r \rparen = N - \lparen K - 1 \rparen \lparen r - 1 \rparen
$$

例1 N 個の整数列から 2 個ずつ選択していった際。 (r = 2)

例2 N 個の整数列から 3 個ずつ選択していった際。(r = 3)

ゆえにその差が K となる選び方の総数は、以下の等式で得ることができる。

$$
\sum_{r=1}^{\frac{N+K-1}{K}} {}_{n\lparen K, r\rparen }C_r
$$