Number of events

Question

Suppose we have n elements, a ₁ , a ₂ , ..., a _n , arranged in a circle. That is, ₂ is between ₁ and ₃ , a ₃ is between ₂ and ₄ , _n is between _n-1 and ₁ , and therefore d.

Each element can take the value 1 or 0. Two conventions differ from each other if there are corresponding _i , the values ​​of which differ. For example, when n = 3, (1, 0, 0) and (0, 1, 0) are different arrangements, although they can be isomorphic when rotated or reflected.

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

Here is the question:

How many arrangements are possible, so that none of the two adjacent elements have a value of 1? If this helps, consider only cases where n> 3.

I ask here several reasons:

• This arose when I solved the programming problem.
• It looks like the problem could benefit from logic / bit arithmetic
• There may not be a closed solution.

Answer 1

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

To simplify the notation of repetition, we calculate A (n) as the sum of two numbers:
B (n), the number of sequences that end with 0, and
C (n), the number of sequences that end with 1.

Then B (n) = A (n-1) (take any such sequence of length n-1 and add 0)
and C (n) = B (n-1) (because if you have 1 in position n, you should have 0 on n-1.)
This gives A (n) = B (n) + C (n) = A (n-1) + B (n-1) = A (n-1) + A (n-2). By now, this should be familiar :-)

A (n) is just the Fibonacci number F _{n + 2} , where the Fibonacci sequence is defined:
F ₀ = 0, F ₁ = 1, and F _{n + 2} = F _{n + 1} + F _n for n? 0.

Now for your question. We will calculate the number of agreements with ₁ = 0 and a ₁ = 1 separately. For the first, ₂ ? a _n can be any sequence in general (without consecutive 1s), so the number is A (n-1) = F _{n + 1} . For the latter, we must have ₂ = 0, and then a ₃ & hellip; a _n is any sequence without consecutive 1s that ends with 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 this answer. Please note that if you call the answer as
G (n) = F n + 1 + F n-1 , then
G (n + 1) = F n + 2 + F n and
G (n + 2) = F n + 3 + F n + 1 , so even G (n) satisfies the same recurrence as the Fibonacci sequence! [In fact, any linear combination of Fibonacci-related sequences will satisfy the same repetition, so this is not all that is surprising.] Thus, another way of calculating the answers will use:
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 = ([alpha] ⁿ - [beta] ⁿ ) / ([alpha] - [beta]) (where [alpha] and [beta] are (1 - √5) / 2, the roots x ² -x-1 = 0) to get
G (n) = ((1 + √5) / 2) ⁿ + ((1-√5) / 2) ⁿ .
[You can ignore the second term because it is very close to 0 for large n, in fact G (n) is the closest integer to ((1 + √5) / 2) ⁿ for all n & ge; 2.] Sub>

Answer 2

I decided to hack a little script to try:

#!/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 it in 5 gave me a total of 11 possibilities with 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

PS - Sorry not () in the code above.

Answer 3

Throwing my naive script into the mix. Lots of options for caching partial results, but it worked fast enough for small n, which I didn’t worry about.

 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 4

This issue is very similar to the Zeckendorf view . I cannot find an obvious way to apply the Zeckendorf theorem due to the restriction of circular motion, but the Fibonacci numbers are obviously very common in this problem.