AtCoder 典型90 015問題 解説補足
典型90問 015 - Don’t be too close
1 から N までの整数列において、1つ以上の整数を選択する際に、どの整数もその差が K (≥ 1) 以上となる選び方は何通りあるか？
解説
公式解説にもある通り、選択できない組み合わせは結合していく。
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
$$