如果连续不超过 Mzeros/ones，则有多少个 N 位的二进制数

Question

是否有可用于任意 M 和 N 的方程式？

示例，N=3 和 M=2：

3 位允许 8 种不同的组合，但其中只有 2 种连续不包含超过 2 个相同的符号

000 - 失败

001 - 失败

010 - 好

011 - 失败

100 - 失败

101 - 好的

110 - 失败

111 - 失败

Answer 1

解决问题的一种方法如下：我们想计算长度为 n 的二进制字，而不需要长度为 m 或更大的游程。让 g(n, m) 表示此类单词的数量。在示例中，n = 3 和 m = 2.

如果n < m，每个二进制字都有效，我们总共得到g(n, m) = 2^n个字。

当n >= m时，我们可以选择从1, 2, ... m-1个重复值开始，接下来分别是 g(n-1, m), g(n-2, m), ... g(n-m+1, m) 个选项。结合起来，我们得到以下递归（在 Python 中）：

from functools import lru_cache

@lru_cache(None) # memoization
def g(n, m):
  if n < m:
    return 2 ** n
  else:
    return sum(g(n-j, m) for j in range(1, m))

为了测试正确性，我们可以直接计算这样的二进制序列的数量：

from itertools import product, groupby

def brute_force(n, k):
  # generate all binary sequences of length n
  products = product([0,1], repeat=n)
  count = 0
  for prod in products:
    has_run = False
    # group consecutive digits
    for _, gp in groupby(prod):
      gp_size = sum(1 for _ in gp)
      if gp_size >= k:
        # there are k or more consecutive digits in a row
        has_run = True
        break
    if not has_run:
      count += 1
  return count

assert 2 == g(3, 2) == brute_force(3, 2)
assert 927936 == g(20, 7) == brute_force(20, 7)

如果连续不超过 Mzeros/ones，则有多少个 N 位的二进制数

How many binary numbers with N bits if no more than M zeros/ones in a row

binary

combinations

combinatorics