Number of arrangements

Question

Suppose we have n elements, a₁, a₂, ..., a_n, arranged in a circle. That is, a₂ is between a₁ and a₃, a₃ is between a₂ and a₄, a_n is between a_n-1 and a₁, and so forth.

Each element can take the value of either 1 or 0. Two arrangements are different if there are corresponding a_i's whose values differ. For instance, when n=3, (1, 0, 0) and (0, 1, 0) are different arrangements, even though they may be isomorphic under rotation or reflection.

Because there are n elements, each of which can take two values, the total number of arrangements is 2ⁿ.

Here is the question:

How many arrangements are possible, such that no two adjacent elements both have the value 1? If it helps, only consider cases where n>3.

I ask here for several reasons:

1. This arose while I was solving a programming problem
2. It sounds like the problem may benefit from Boolean logic/bit arithmetic
3. Maybe there is no closed solution.

Answer 1

I decided to hack up a small script to try it out:

#!/usr/bin/python
import sys

# thx google 
bstr_pos = lambda n: n>0 and bstr_pos(n>>1)+str(n&1) or ""

def arrangements(n):
    count = 0
    for v in range(0, pow(2,n)-1):
        bin = bstr_pos(v).rjust(n, '0')
        if not ( bin.find("11")!=-1 or ( bin[0]=='1' and bin[-1]=='1' ) ):
            count += 1
            print bin
    print "Total = " + str(count)

arrangements(int(sys.argv[1]))

Running this for 5, gave me a total of 11 possibilities with 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

P.S. - Excuse the not() in the above code.

Answer 2

Throwing my naive script into the mix. Plenty of opportunity for caching partial results, but it ran fast enough for small n that I didn't bother.

def arcCombinations(n, lastDigitMustBeZero):
    """Takes the length of the remaining arc of the circle, and computes
       the number of legal combinations.
       The last digit may be restricted to 0 (because the first digit is a 1)"""

    if n == 1: 
        if lastDigitMustBeZero:
            return 1 # only legal answer is 0
        else:
            return 2 # could be 1 or 0.
    elif n == 2:
        if lastDigitMustBeZero:
            return 2 # could be 00 or 10
        else:
            return 3 # could be 10, 01 or 00
    else:
        # Could be a 1, in which case next item is a zero.
        return (
            arcCombinations(n-2, lastDigitMustBeZero) # If it starts 10
            + arcCombinations(n-1, lastDigitMustBeZero) # If it starts 0
            )

def circleCombinations(n):
    """Computes the number of legal combinations for a given circle size."""

    # Handle case where it starts with 0 or with 1.
    total = (
            arcCombinations(n-1,True) # Number of combinations where first digit is a 1.
            +
            arcCombinations(n-1,False) # Number of combinations where first digit is a 0.
        )
    return total


print circleCombinations(13)

Answer 3

This problem is very similar to Zeckendorf representations. I can't find an obvious way to apply Zeckendorf's Theorem, due to the circularity constraint, but the Fibonacci numbers are obviously very prevalent in this problem.