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

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 F_n+2 where the Fibonacci sequence is defined by
F₀=0, F₁=1, and F_n+2= F_n+1+F_n for n ≥ 0.

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

So the answer is F_n+1 + F_n-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 F_n=(αⁿ-βⁿ)/(α-β) (where α and β are (1±√5)/2, the roots of x²-x-1=0), to get
G(n) = ((1+√5)/2)ⁿ + ((1-√5)/2)ⁿ.
[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)ⁿ for all n≥2.]