Condicionalmente la combinación de vainilla y las cucharadas de helado de chocolate

Question

Supongamos que tengo una placa que se ajusta a $n$ número de Porcionador de helado. Puedo elegir entre sabores chocolate y vainilla. La única condición es que no puedo sacar para chocolate dos veces en una fila, por ejemplo si $n=5$ entonces {$v,c,c,v,c$} no es permitido - una combinación imposible - pero {$c,v,c,v,c$} o {$v,v,v,v,c$} es permitido.

¿Cuántas combinaciones posibles existen? Sé que tengo que realizar la operación $${n \choose 2} - \text{impossible combinations}

Pero, ¿cómo figura el número de combinaciones imposibles?

Answer 1

Desea secuencias binarias que no contengan dos consecutivas.

Deje $f(n)$ el número de secuencias de longitud $n$.

luego tenemos a $f(1)=2,f(2)=3$.

Después de esto hacemos uso de la recursividad $f(n)=f(n-1)+f(n-2)$.

Por qué? separar las cadenas de lentgh $n$ en dos tipos, los que terminan en $1$, y los que terminan en $0$.

Cuántos final en $0$? $f(n-1)$, ya que después de eliminar el último dígito debe tener una secuencia válida de longitud $n-1$.

Cuántos final en $1$? $f(n-2)$ desde el segundo al último dígito debe ser $0$, y luego la primera a la $n-2$ debe formar una secuencia válida.

Así, la secuencia se va, $1,2,3,5,8,13\dots$ Y así sucesivamente, lo que es una cola de la secuencia de Fibonacci.

Answer 2

Hay $2^{5}$ combinaciones posibles. Queremos una recurrencia para que nos ayuden. Así que vamos a $T(1)$ ser nuestro recurrencia que indica el número de combinaciones permitidas para una cadena de longitud $n$. Por lo $T(1) = 2$. Del mismo modo, $T(2) = 2^{2} - 1 = 3$, dándonos $vv, vc, cv$. Ahora para $T(3)$, no podemos tener a $ccv, vcc, ccc$. Así que hay $2^{3} = 8$ combinaciones posibles y excluimos a los tres, dejando a $T(3) = 5 = T(2) + T(1)$.

De manera más general, $T(n) = T(n-1) + T(n-2)$ con condiciones iniciales $T(1) = 2$, $T(2) = 3$. Tenemos el polinomio característico y resolver:

$\lambda^{2} - \lambda - 1 = 0$, lo que nos da autovalores $\lambda = \frac{ 1 \pm \sqrt{5}}{2}$.

La forma general de la ecuación es: $T(n) = A \cdot (\frac{1 + \sqrt{5}}{2})^{n} + B \cdot (\frac{1 - \sqrt{5}}{2})^{n}$.

Ahora conecte en sus condiciones iniciales y resolver.

El número de imposible combinaciones de es $2^{n} - T(n)$.

Edit: Probando T(n) tiene por inducción. La base de los casos se dan en mi análisis anterior para $T(1), T(2)$. Así que asumir cierto al $n-1$ y considerar el caso de $n$.

Ahora mira a $T(n)$ y eliminar el último sabor añadido. Si era de vainilla, hay $T(n-1)$ formas de construcción de dicha secuencia. Por la hipótesis inductiva, $T(n-1)$ correctamente cuenta el número válido de $n-1$ configuraciones. Así que añadir la vainilla es válido.

Si el último sabor en lugar de chocolate, se nota que el sabor antes de la última es de vainilla (de lo contrario, la configuración sería válido). Así que hay $T(n-2)$ cadenas de este tipo, de modo que el $n-1$ sabor a vainilla. Y, a continuación, el $n$th sabor a chocolate. Por lo tanto, $T(n) = T(n-1) + T(n-2)$, agotando todas válido posibilidades.

Así que por el principio de inducción matemática, $T(n)$ correctamente los recuentos de las configuraciones válidas para su problema.

Answer 3

Razonamos por casos. Supongamos que colocamos abajo $k$ cucharadas de vainilla en primer lugar. Esto deja boquetes de $k + 1$, cada uno de los cuales tampoco contendrá exactamente exactamente cucharadas de #% de los $0$ chocolate %#% o $1$ (ya que no podemos tener más de $n - k$ chocolate cucharada en la misma brecha). Esto puede hacerse de maneras de $1$. Resumen sobre cada posible valor de $\binom{k+1}{n-k}$ (es decir, de $k$ $k = 2$), obtenemos: $$\binom{3}{3} + \binom{4}{2} + \binom{5}{1} + \binom{6}{0} = 1 + 6 + 5 + 1 = 13$$