math - 包含至少 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

本题与“某处至少连续3个1的N位二进制数的个数”存在双射(双射为数如果排除在子集，如果包含在子集中则为 1)。

这是一个已知问题，如果您搜索 number of n-digit binary strings with m consecutive 1s，应该有足够的信息来搜索结果，第二个结果是 Finding all n digit binary numbers with r adjacent digits as 1

或者，您可以将其查找为 http://oeis.org/search?q=0%2C0%2C1%2C3%2C8%2C20%2C47 (基于您对前几个术语所做的暴力破解)- 产生一个显式公式 2^n - tribonacci(n+3)，参见 here对于 tribonacci 数的明确公式。它还给出了递归关系。给出的类比是“在 n 次抛硬币中至少出现 1 次正面朝上的概率(总计 2^n)”

我只能假设一般问题的答案是 2^n - F_m(n+m)，其中 F_m 是 m^第 n-step Fibonacci number (编辑:seem to be the case )