Número de arreglos

votos
4

Supongamos que tenemos n elementos, un 1 , un 2 , ..., un n , dispuestos en un círculo. Es decir, un 2 está entre un 1 y un 3 , un 3 está entre un 2 y un 4 , un n está entre un n -1 y un 1 , y así sucesivamente.

Cada elemento puede tomar el valor de 1 o 0. Dos arreglos son diferentes si hay una i correspondiente cuyos valores son diferentes. Por ejemplo, cuando n = 3, (1, 0, 0) y (0, 1, 0) son arreglos diferentes, a pesar de que pueden ser isomorfos bajo rotación o reflexión.

Como hay n elementos, cada uno de los cuales puede tomar dos valores, el número total de arreglos es 2 n .

Aquí está la pregunta:

¿Cuántos arreglos son posibles, de manera que no hay dos elementos adyacentes que tengan el valor 1? Si ayuda, solo considere los casos donde n > 3.

Pregunto aquí por varias razones:

  1. Esto surgió mientras resolvía un problema de programación
  2. Parece que el problema puede beneficiarse de la lógica booleana / aritmética de bits
  3. Tal vez no hay una solución cerrada.
Publicado el 10/12/2008 a las 00:41
fuente por usuario
En otros idiomas...                            


4 respuestas

votos
10

Primero hagamos la pregunta "¿Cuántas secuencias 0-1 de longitud n hay allí sin dos 1 consecutivas?" Deje que la respuesta sea A (n). Tenemos A (0) = 1 (la secuencia vacía), A (1) = 2 ("0" y "1"), y A (2) = 3 ("00", "01" y "10" pero no "11").

Para facilitar la escritura de una repetición, calcularemos A (n) como la suma de dos números:
B (n), el número de tales secuencias que terminan con un 0, y
C (n), el número de tales secuencias que terminan con un 1.

Entonces B (n) = A (n-1) (tome cualquier secuencia de longitud n-1 y añada un 0)
y C (n) = B (n-1) (porque si tiene un 1 en la posición n) , debes tener un 0 en n-1.)
Esto da A (n) = B (n) + C (n) = A (n-1) + B (n-1) = A (n-1) + A (n-2). Por ahora debería ser familiar :-)

A (n) es simplemente el número de Fibonacci F n + 2 donde la secuencia de Fibonacci se define por
F 0 = 0, F 1 = 1 y F n + 2 = F n + 1 + F n para n ≥ 0.

Ahora para tu pregunta. Contaremos el número de arreglos con un 1 = 0 y un 1 = 1 por separado. Para el primero, a 2 ... a n puede ser cualquier secuencia (sin 1 consecutivos), por lo que el número es A (n-1) = F n + 1 . Para este último, debemos tener un 2 = 0, y luego un 3 ... a n es cualquier secuencia sin 1 consecutivos que termina con un 0 , es decir, B (n-2) = A (n-3) = F n- 1 .

Entonces la respuesta es F n + 1 + F n-1 .

En realidad, podemos ir incluso más allá de esa respuesta. Tenga en cuenta que si llama a la respuesta como
G (n) = F n + 1 + F n-1 , entonces
G (n + 1) = F n + 2 + F n , y
G (n + 2) = F n + 3 + F n + 1 , ¡así que incluso G (n) satisface la misma recurrencia que la secuencia de Fibonacci! [En realidad, cualquier combinación lineal de secuencias tipo Fibonacci satisfará la misma recurrencia, por lo que no es tan sorprendente.] Entonces otra forma de calcular las respuestas sería usando:
G (2) = 3
G (3) = 4
G ( n) = G (n-1) + G (n-2) para n≥4.

Y ahora también puedes usar la forma cerrada F n = (α nn ) / (α-β) (donde α y β son (1 ± √5) / 2, las raíces de x 2 -x-1 = 0), para obtener
G (n) = ((1 + √5) / 2) n + ((1-√5) / 2) n .
[Puede ignorar el segundo término porque está muy cerca de 0 para n grande, de hecho G (n) es el entero más cercano a ((1 + √5) / 2) n para todo n≥2.]

Respondida el 10/12/2008 a las 01:00
fuente por usuario

votos
1

Decidí hackear un pequeño script para probarlo:

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

Al ejecutar esto para 5, obtuve un total de 11 posibilidades con 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

PD - Disculpe el no () en el código anterior.

Respondida el 10/12/2008 a las 01:14
fuente por usuario

votos
0

Este problema es muy similar a las representaciones de Zeckendorf . No puedo encontrar una forma obvia de aplicar el Teorema de Zeckendorf, debido a la restricción de circularidad, pero los números de Fibonacci son obviamente muy frecuentes en este problema.

Respondida el 10/12/2008 a las 01:38
fuente por usuario

votos
0

Lanzando mi ingenuo guión a la mezcla. Había muchas oportunidades para almacenar resultados parciales, pero funcionaba lo suficientemente rápido para pequeños n que no me molestaba.

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)
Respondida el 10/12/2008 a las 01:16
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more