CODEWITHSUNDEEP
algorithmmath
user44511
user44511

Reputation: 2851

Number of arrangements

Suppose we have n elements, a1, a2, ..., an, arranged in a circle. That is, a2 is between a1 and a3, a3 is between a2 and a4, an is between an-1 and a1, and so forth.

Each element can take the value of either 1 or 0. Two arrangements are different if there are corresponding ai'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 2n.

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.

Upvotes: 4

Views: 1072

Answers (4)

ShreevatsaR
ShreevatsaR

Reputation: 39083

Let's first ask the question "how many 0-1 sequences of length n are there with no two consecutive 1s?" Let the answer be A(n). We have A(0)=1 (the empty sequence), A(1) = 2 ("0" and "1"), and A(2)=3 ("00", "01" and "10" but not "11").

To make it easier to write a recurrence, we'll compute A(n) as the sum of two numbers:
B(n), the number of such sequences that end with a 0, and
C(n), the number of such sequences that end with a 1.

Then B(n) = A(n-1) (take any such sequence of length n-1, and append a 0)
and C(n) = B(n-1) (because if you have a 1 at position n, you must have a 0 at n-1.)
This gives A(n) = B(n) + C(n) = A(n-1) + B(n-1) = A(n-1) + A(n-2). By now it should be familiar :-)

A(n) is simply the Fibonacci number Fn+2 where the Fibonacci sequence is defined by
F0=0, F1=1, and Fn+2= Fn+1+Fn for n ≥ 0.

Now for your question. We'll count the number of arrangements with a1=0 and a1=1 separately. For the former, a2 … an can be any sequence at all (with no consecutive 1s), so the number is A(n-1)=Fn+1. For the latter, we must have a2=0, and then a3…an is any sequence with no consecutive 1s that ends with a 0, i.e. B(n-2)=A(n-3)=Fn-1.

So the answer is Fn+1 + Fn-1.

Actually, we can go even further than that answer. Note that if you call the answer as
G(n)=Fn+1+Fn-1, then
G(n+1)=Fn+2+Fn, and
G(n+2)=Fn+3+Fn+1, so even G(n) satisfies the same recurrence as the Fibonacci sequence! [Actually, any linear combination of Fibonacci-like sequences will satisfy the same recurrence, so it's not all that surprising.] So another way to compute the answers would be using:
G(2)=3
G(3)=4
G(n)=G(n-1)+G(n-2) for n≥4.

And now you can also use the closed form Fn=(αn-βn)/(α-β) (where α and β are (1±√5)/2, the roots of x2-x-1=0), to get
G(n) = ((1+√5)/2)n + ((1-√5)/2)n.
[You can ignore the second term because it's very close to 0 for large n, in fact G(n) is the closest integer to ((1+√5)/2)n for all n≥2.]

Upvotes: 10

Adam Rosenfield
Adam Rosenfield

Reputation: 400294

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.

Upvotes: 0

Oddthinking
Oddthinking

Reputation: 25292

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)

Upvotes: 0

codelogic
codelogic

Reputation: 73622

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.

Upvotes: 1

Related Questions