CODEWITHSUNDEEP
binarycombinationscombinatorics
torpedo
torpedo

Reputation: 299

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

Is there an equation I can use for arbitrary M and N?

Example, N=3 and M=2:

3 bits allow for 8 different combinations, but only 2 of them do not contain more than 2 same symbols in a row

000 - Fails

001 - Fails

010 - OK

011 - Fails

100 - Fails

101 - OK

110 - Fails

111 - Fails

Upvotes: 0

Views: 234

Answers (1)

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

One way to frame the problem is as follows: we would like to count binary words of length n without runs of length m or larger. Let g(n, m) denote the number of such words. In the example, n = 3 and m = 2.

If n < m, every binary word works, and we get g(n, m) = 2^n words in total.

When n >= m, we can choose to start with 1, 2, ... m-1 repeated values, followed by g(n-1, m), g(n-2, m), ... g(n-m+1, m) choices respectively. Combined, we get the following recursion (in 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))

To test for correctness, we can compute the number of such binary sequences directly:

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)

Upvotes: 0

Related Questions