how many n-length binary sequence problem

Question

how to find out the solution to this problem in python/java or any other language:

Thanks in advance

Doesn't really seem like a programming problem at all. It seems like a homework problem for a discrete math class. — John Coleman
– John Coleman, Commented Oct 27, 2020 at 18:37
It would be easy enough to write a Python program which would brute-force the answer for small n. For reasons that I can't quite articulate, I suspect that the answer has something to do with Fibonacci numbers. — John Coleman
– John Coleman, Commented Oct 27, 2020 at 18:43

John Coleman · Accepted Answer · 2020-10-27 18:59:31Z

1

Since a program isn't a proof and you would still need to prove it, here is some Python code:

def zig_zag(seq):
    """tests if binary sequence seq satsifies zig-zag pattern"""
    for i in range(len(seq)-1):
        if (i%2 == 0 and seq[i] > seq[i+1]) or (i%2 == 1 and seq[i] < seq[i+1]):
            return False
    return True

def count_zig_zags(n):
    """counts the number of binary zig-zag patterns of length n"""
    count = 0
    for i in range(2**n):
        b = bin(i)[2:]
        if zig_zag(b): count += 1
    return count

For example:

>>> [count_zig_zags(n) for n in range(1,12)]
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]

A proof would be via strong induction.

answered Oct 27, 2020 at 18:59

John Coleman

52.1k7 gold badges59 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Mahdir Over a year ago

I think for the length 3, the output has to be 10, for example. Why 5?!

Mahdir Over a year ago

Is there any recursive solution?

John Coleman Over a year ago

How could the output for n = 3 be 10? 2^3 = 8, so even with no restrictions on the binary sequences it would have to be <= 8. The 5 binary sequences that satisfy the constraints are 000, 010, 011, 110, 111.

John Coleman Over a year ago

For a recursive solution, note that a valid solution of length n can be extended to a valid solution of length n+1 in either 1 way or 2 ways, and that the number that can be extended in 2 ways is the same as the number of valid sequences of length n-1 (proof, which seems to require 2 cases depending on whether n is even or odd, not given).

Collectives™ on Stack Overflow

how many n-length binary sequence problem

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related