Una luz puede solamente encendida si hay una luz al lado encendido. ¿De cuántas maneras puede encender todas las luces?

Question

Hay $n$ luces(numerados de $1$$n$), algunos de ellos están encendidos. Un apagado la luz puede ser activada sólo si hay una luz junto a él encendido. De cuántas maneras se puede encender todas las luces?

Por ejemplo: $$n=5$$ y la luz de número de $3$ es. $$0 0 1 0 0$$

la respuesta es 6.

6 maneras

43*12

32*14

42*13

41*23

31*24

21*34

El * significa que el inicial enciende la luz. Los números indican el orden en el que las luces estaban encendidas

Me han tratado de forma recursiva la construcción de la solución. Pero el tiempo no es factible.

Un encendido la luz nunca se apaga.

Answer 1

Vamos a no ser de m secuencias de consecutivos de las luces que se apagan, y $a_i$ ser el número de luces de cada secuencia,$i\in\{1,...,m\}$.

Si usted mira una única secuencia hay diferencia si la secuencia es entre dos aligerado lightballs o está al final de la fila. Si es que entre entonces no es $2^{a_m-1}$ formas de elegir el orden en el que va a la luz de ellos, LRRLRR f.e. Si es que en el final de la fila, a continuación, sólo hay un camino para que se conviertan en ir uno por uno.

Una vez que has elegido el orden de encendido de luces de cada secuencia debe decidir el orden de las secuencias que se encienda una luz en cada ronda. Número del es $\frac{(\sum a_i)!}{\Pi (a_i!)}$

Y el número total es de $\frac{(\sum a_i)!}{\Pi (a_i!)}\Pi (2^{a_j-1})$ donde $j$ son los índices de las secuencias que hay en medio, por lo que posiblemente sin 1 o n.

En su ejemplo, no hay secuencias en el medio, así que sólo tienes $\frac{(2+2)!}{ 2!2!}=6$

Aquí hay un ejemplo que es más complicado: 0010001100001

Por lo $a_1=2, a_2=3, a_3=4$ respuesta es $\frac{(2+3+4)!}{ 2!3!4!}2^{3-1}2^{4-1}$

Answer 2

• No sé lo que es dado como datos, pero si las posiciones de encendido de las lámparas se da en primer lugar usted debe extraer todos los contiguos extinguido bombillas.

Ejemplo:

000111010100110000

S= {{1,2,3},{7},{9},{11,12},{15,16,17,18}}

Próxima a los cardenales: |S|={3,1,1,2,4}

Si intenta visualizar el problema como un conjunto de permutaciones, la solución es simplemente una distribución multinomial $\binom{n}{3,4,(1-1),(1-1),(2-1)}$

Para un conjunto de cardenales $|S|=\{x_0,x_1,x_2,x_3,x_4,...x_i\}$

La solución es $\binom{n}{x_0,\sum_j(x_1-j-1,j_1),\sum_j(x_2-j-2,j_2),...,x_i}$

$$=\sum_{j_1,j_2,...=0}\frac{n!}{x_0!(x_1-j_1-1)!j_1!(x_2-j_2-1)!j_2!...!x_i!}$$

Donde $n$ es el número de la extinta bombillas=$x_0+x_1+...x_n$.

Explicación:

Por ejemplo, un conjunto particular de $x_0,x_1-j_1,j_1,x_2-j_2,j_2,...x_i$ e n extinto bulbls, las permutaciones de estos elementos solo observa el orden de la elección de cualquiera de estos contiguos sub-listas, el acto de elegir una sublista se imaginaron que hacer clic en el edgemost interruptor de alineado que son todos apaga, ¿por qué $x_j-j-1$ ? porque un juego completo de $x_j$ engloba la que se organiza con la lista diferente, por lo que la eliminación de 1 de opuestos subconjuntos como la reserva de una "tierra de nadie" de longitud=1 en el medio, se corrige el problema de la duplicación de decisiones.

---

Edit: Después de un poco de pensar me di cuenta de que una coincidencia de la elección de la no-cruz de línea fija entre opuestos subconjuntos antes de $j$ o $x-j-1$ elementos deben ser excluidos, por lo tanto dividido.

$S=\sum_{j_1,j_2,...=0}\frac{n!}{x_0!(x_1-j_1-1)!j_1!(j_1-1)(x_1-j_1-2)(x_2-j_2-1)!j_2!(j_2-1)(x_2-j_2-2)...!x_i!}$=$$\sum_{j_1,j_2,...=0}\frac{n!}{x_0!(x_1-j_1-1)!j_1!(x_2-j_2-1)!j_2!...!x_i!*(j_1-1)(x_1-j_1-2)(j_2-1)(x_2-j_2-2)...}$$