Количество договоренностей

Question

Предположим, у нас есть n элементов, a ₁ , a ₂ , ..., a _n , расположенных по кругу. То есть a ₂ находится между a ₁ и a ₃ , a ₃ находится между a ₂ и a ₄ , a _n находится между a _{n -1} и a ₁ и пр.

Каждый элемент может принимать значение 1 или 0. Два расположения различны, если есть соответствующие a _i , значения которых отличаются. Например, когда n = 3, (1, 0, 0) и (0, 1, 0) - это разные расположения, даже если они могут быть изоморфными при вращении или отражении.

Поскольку имеется n элементов, каждый из которых может принимать два значения, общее количество расположений составляет 2 ⁿ .

Вот вопрос:

Сколько возможно расположений, чтобы никакие два соседних элемента не имели значение 1? Если это поможет, рассмотрите только случаи, когда n > 3.

Я спрашиваю здесь по нескольким причинам:

1. Это возникло, когда я решал проблему программирования
2. Похоже, что проблема может быть полезна из булевой логики / битовой арифметики
3. Может быть, нет закрытого решения.

Answer 1

Давайте сначала зададим вопрос "сколько существует последовательностей 0-1 длины n без двух последовательных 1?" Пусть ответ будет A (n). У нас есть A (0) = 1 (пустая последовательность), A (1) = 2 («0» и «1»), и A (2) = 3 («00», «01» и «10», но не "11").

Чтобы упростить запись повторения, мы вычислим A (n) как сумму двух чисел:
B (n), число таких последовательностей, заканчивающихся на 0, и
C (n), число таких последовательностей, которые заканчиваются на 1.

Тогда B (n) = A (n-1) (возьмите любую такую ​​последовательность длины n-1 и добавьте 0)
и C (n) = B (n-1) (потому что если у вас есть 1 в позиции n, вы должны иметь 0 в n-1.)
Это дает A (n) = B (n) + C (n) = A (n-1) + B (n-1) = A (n-1) + A (n-2). К настоящему времени это должно быть знакомо: -)

A (n) - это просто число Фибоначчи F _{n + 2} , где последовательность Фибоначчи определяется как
F ₀ = 0, F ₁ = 1 и F _{n + 2} = F _{n + 1} + F _n для n & ge; 0.

Теперь на ваш вопрос. Мы посчитаем количество договоренностей с ₁ = 0 и ₁ = 1 отдельно. Для первых, ₂ & hellip; _n может быть любой последовательностью (без последовательных 1 с), поэтому число A (n-1) = F _{n + 1} . Для последнего у нас должно быть ₂ = 0, а затем ₃ & hellip; a _n - любая последовательность без последовательных 1, которые заканчиваются с 0 , то есть B (n-2) = A (n-3) = F _n-1 .

Итак ответ F _{n + 1} + F _n-1 .

_{На самом деле, мы можем пойти еще дальше, чем этот ответ. Обратите внимание, что если вы называете ответ как
G (n) = F n + 1 + F n-1 , то
G (n + 1) = F n + 2 + F n и
G (n + 2) = F n + 3 + F n + 1 , поэтому даже G (n) удовлетворяет тому же самому повторению, что и последовательность Фибоначчи! [На самом деле, любая линейная комбинация последовательностей, подобных Фибоначчи, будет удовлетворять одному и тому же повторению, так что это не так уж удивительно.] Поэтому другой способ вычисления ответов будет использовать:
G (2) = 3
G (3) = 4
G (n) = G (n-1) + G (n-2) для n & ge; 4.}

И теперь вы также можете использовать закрытую форму F _n = (& alpha; ⁿ - & beta; ⁿ ) / ( & alpha; - & beta;) (где & alpha; и & beta; равны (1 ± √5) / 2, корни x ² -x-1 = 0), чтобы получить
G (n) = ((1 + √5) / 2) ⁿ + ((1-√5) / 2) ⁿ .
[Вы можете игнорировать второй член, потому что он очень близок к 0 для больших n, на самом деле G (n) является ближайшим целым числом к ​​((1 + √5) / 2) ⁿ для всех n & ge; 2.]

Answer 2

Я решил взломать небольшой скрипт, чтобы опробовать его:

#!/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]))

Выполнение этого для 5, дало мне всего 11 возможностей с 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

P.S. - Извините, но () в приведенном выше коде.

Answer 3

Эта проблема очень похожа на представления Цекендорфа . Я не могу найти очевидный способ применить теорему Цекендорфа из-за ограничения округлости, но числа Фибоначчи, очевидно, очень распространены в этой задаче.

Answer 4

Бросаю свой наивный сценарий в микс. Множество возможностей для кеширования частичных результатов, но оно работало достаточно быстро для малых n, что меня не беспокоило.

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)