math - 固定長サブセット内の最小数の要素との組み合わせ

Question

私は長い間探していましたが、これに対する解決策を見つけることができませんでした。私の質問は、「n 個の街灯 (移動できない) があり、それらから m を取得した場合、少なくとも k 個の機能が必要であるとします。これを行う方法はいくつありますか?」

これは組み合わせの問題のようですが、ここでの問題は「m」が連続していなければならないことです。

例: 1 2 3 4 5 6 7 (街灯)
m=3
とすると、有効なセットは
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

で、
1 2 4 などは無効な選択です。

したがって、すべてのセットには少なくとも 2 つの作業灯が必要です。
条件を満たすために必要な最小限のランプを見つける方法を見つけましたが、それを実行できる方法の数をどのように見つけることができますか?

これを行うには確かにいくつかの式があるはずですが、私はそれを見つけることができません.. :(

Answer 1

常にあるべき(n-m)+1です。例: 10 個のライト (n = 10)、5 個のセット (m = 5):

1 2 3 4 5
2 3 4 5 6
3 4 5 6 7 
4 5 6 7 8
5 6 7 8 9
6 7 8 9 10

(10-5)+1 = 6セットを与えます。