包含至少3个连续元素的{1,2,3,...,N}的子集数

Question

假设我们有一个像那样的集合,{1,2,3}只有一种方法可以选择3个连续数字...它是集合{1,2,3} ...

对于一组{1,2,3,4},我们有3种方式: 123 234 1234

(从技术上讲,这些是无序的数字集,但连续写它们有帮助)

• f(5); {1,2,3,4,5} - > 8种方式:123 1234 1235 12345 234 2345 345 1345
• f(6); {1,2,3,4,5,6} - > 20种方式:......
• f(7); {1,2,3,4,5,6,7} - > 47种方式:......

因此对于给定的N,我可以通过应用强力,并计算具有3个或更多连续数的所有这样的子集来得到答案.

在这里,我只是想找出一种模式,一种技术来获得给定N的所有这样的子集的数量.

该问题进一步推广到.....在一组大小N内发现m个连续数.

Answer 1

在这个问题与" 1某个地方连续至少有三个连续s 的N位二进制数的数量"之间存在一个双射(如果在子集中排除,则双射数为0,如果包含在子集中则为1) .

这是一个已知的问题,应该有足够的信息谷歌搜索结果,如果你搜索number of n-digit binary strings with m consecutive 1s,第二个命中是查找所有n位二进制数字与r相邻数字为1

或者,您可以查看http://oeis.org/search?q=0%2C0%2C1%2C3%2C8%2C20%2C47(基于您在前几个术语中执行的强制执行) - 结果在一个明确的公式中2^n - tribonacci(n+3),请参见此处有关tribonacci数的显式公式.它还给出了递归关系.给出的类比是"在公平硬币的n个翻转中获得至少1次3个头的概率(超过2 ^ n)"

我只能假设答案的一般问题是2 ^ N - ˚F _米(N + M),其中F _米是第m ^个 正步骤Fibonacci数(编辑:,它似乎是的情况下)