Combinatoria - ¿Cuántas cadenas de bits de longitud 8 con exactamente dos 0's hay para las que los 0's no son adyacentes?

Question

¿Cuántas cadenas de bits de longitud 8 con exactamente dos 0's hay para las que los 0's no son adyacentes?

Estoy teniendo muchos problemas con este problema aparentemente sencillo.

Intento hacerlo con estrellas y barras. ¿Estoy en lo correcto o en el camino correcto al menos?

Primero, pongo dos barras para mis dos 0, y luego pongo un 1 entre ellas para asegurarme de que los 0 no son adyacentes.

|x|

Esto me deja con 5 1's más para colocar en la cadena de bits. ejemplo: x|xx|xxx sería una distribución de los 5 1's restantes.

Entonces, esto me da c(3+5-1,3-1), o c(7,2)=21 formas.

La única otra forma que se me ocurre para hacer este problema sería obtener el número total de formas de tener una cadena de bits de longitud 8 con exactamente dos 0's, y restar el número total de formas de que los 0's sean adyacentes.

Así que, c(8,2) para el número total de fue tener exactamente dos 0's, y restar el número total de formas en que puedo tener exactamente dos 0's en una cadena de bits donde los 0's son adyacentes que es 7.

Esto me da c(8,2)=28 y 28-7=21. Esto confirma mi respuesta (si cualquiera de estos métodos es correcto).

Gracias.

Answer 1

Ambos enfoques son correctos. Tal vez le resulte más fácil el siguiente enfoque.

Deja nuestro $6$ de este modo: $$1\qquad 1\qquad 1\qquad 1\qquad 1\qquad 1$$ Hay $7$ lugares donde $0$ 's podría ir, el $5$ lagunas entre $1$ y el $2$ termina. Debemos elija $2$ de estos lugares, por lo que la respuesta es $\binom{7}{2}$ .

Esto se generaliza inmediatamente para decir que una cadena de bits de longitud $16$ con $5$ $0$ no hay dos que puedan ser adyacentes.

Answer 2

Su segundo método me parece más fácil. Es correcto.

Answer 3

He aquí un enfoque. Toma 5 1s y 2 0s y organízalos como quieras; puedes hacerlo en $7\choose2$ maneras. Entonces sólo inserta un 1 extra entre los 0s.