AtCoder 典型90 015問題 解説補足
典型90問 015 - Don’t be too close
1 から N までの整数列において、1つ以上の整数を選択する際に、どの整数もその差が K (≥ 1) 以上となる選び方は何通りあるか?
解説
公式解説にもある通り、選択できない組み合わせは結合していく。
![](https://assets.st-note.com/img/1701434339181-939htRVk9b.png?width=1200)
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)
![](https://assets.st-note.com/img/1701434185214-E2uhWXV6bd.png?width=1200)
例2 N 個の整数列から 3 個ずつ選択していった際。(r = 3)
![](https://assets.st-note.com/img/1701434301615-6CO8u22Ft6.png?width=1200)
![](https://assets.st-note.com/img/1701434327213-FreOKOsF40.png?width=1200)
ゆえにその差が K となる選び方の総数は、以下の等式で得ることができる。
$$
\sum_{r=1}^{\frac{N+K-1}{K}} {}_{n\lparen K, r\rparen }C_r
$$
この記事が気に入ったらサポートをしてみませんか?