{1,2,3，...，N}包含至少3个连续元素的子集数 [英] Number of subsets of {1,2,3,...,N} containing at least 3 consecutive elements

问题描述

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

Suppose we have a set like {1,2,3} then there is only one way to choose 3 consecutive numbers... it's the set {1,2,3}...

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

For a set of {1,2,3,4} we have 3 ways: 123 234 1234

(从技术上讲，这是无序的数字集，但是连续写会有所帮助)

(technically these are unordered sets of numbers, but writing them consecutively helps)

• 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种方式:...

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

因此，对于给定的N，我可以通过施加蛮力并计算所有具有3个或更多连续数字的子集来获得答案.

So for a given N, I can get the answer by applying brute force, and calculating all such subset having 3 or more consecutive number.

在这里，我只是想找出一种模式，一种获取给定N的所有此类子集的数量的技术.

Here I am just trying to find out a pattern, a technique to get the number of all such subset for a given N.

该问题进一步泛化为.....发现大小为N的集合中的m个连续数.

The problem is further generalized to .....discover m consecutive number within a set of size N.

推荐答案

此问题与某处连续至少有三个连续1的N位二进制数的数量"之间存在双射bijection是一个数字，如果不包含在子集中，则为0；如果包含在子集中，则为1).

There is a bijection between this problem and "the number of N-digit binary numbers with at least three consecutive 1s in a row somewhere" (the bijection being a number is 0 if excluded in the subset, and 1 if included in the subset).

这是一个已知问题，应该足以向Google提供信息以获取结果，如果您搜索number of n-digit binary strings with m consecutive 1s，则第二个匹配项是

This is a known problem, and should be enough information to google for a result, if you search for number of n-digit binary strings with m consecutive 1s, the second hit is Finding all n digit binary numbers with r adjacent digits as 1

或者，您也可以将其查找为 http ://oeis.org/search?q = 0 2^n - tribonacci(n+3)，请参阅此处，以获取有关Tribonacci数字的明确公式.它还给出了递归关系.给出的类比是在公平硬币的n次翻转中至少有3个正面朝上的1个冒牌的概率(在2 ^ n中)"

Alternatively you can just look it up as http://oeis.org/search?q=0%2C0%2C1%2C3%2C8%2C20%2C47 (based on the brute-forcing you did for the first few terms) - resulting in an explicit formula of 2^n - tribonacci(n+3), see here for an explicit formula for tribonacci numbers. It also gives a recurrence relation. The analogy given is "probability (out of 2^n) of getting at least 1 run of 3 heads within n flips of a fair coin"

我只能假设一般问题的答案是2 ^ n-F _m (n + m)，其中F _m 是m n步斐波那契数(

I can only assume that the answer to the general problem is 2^n - F_m(n+m), where F_m is the m^th n-step Fibonacci number (edit: that does seem to be the case)

这篇关于{1,2,3，...，N}包含至少3个连续元素的子集数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！