¿Cuántas cifras #8 puedes construir?

Question

¿Cuántos números diferentes de 8 cifras se pueden formar utilizando dos 1, dos 2, dos 3 y dos 4 de forma que no haya dos dígitos adyacentes sean iguales?

Así que tenemos $0 -> 9 = 10$ opciones para los dígitos, pero con las limitaciones tenemos algo diferente.

Casos:

$1$ _ _

$2$ _ _

$3$ _ _

$4$ _ _

Podemos hacer la recursión de la forma $A(N), B(N),.. D(N)$ en cuanto al número de secuencias que pueden construirse a partir del $1, 2, .. 4$ para $N$ cartas.

Tenemos $T(n) = A(N-1) + B(N-1) + C(N-1) + D(N-1)$

Estamos tras $T(8)$ . Tenemos que por ejemplo $A(n-1) = B(n-2) + C(n-2) + D(n-2) = [A(n-3) + C(N-3) + D(n-3)] + [A(n-3) + B(n-3) + D(n-3)] + [A(n-3) + B(n-3) + C(n-3)] = 3A(n-3) + 2B(n-3) + 2C(n-3) + 2D(n-3)$ . Pero esto se alarga rápido.

Answer 1

Utilice inclusión/exclusión principio:

• Incluir el número total de secuencias, que es $\frac{8!}{2!2!2!2!}$
• Excluir el número de secuencias que contienen $11$ que es $\frac{7!}{1!2!2!2!}$
• Excluir el número de secuencias que contienen $22$ que es $\frac{7!}{1!2!2!2!}$
• Excluir el número de secuencias que contienen $33$ que es $\frac{7!}{1!2!2!2!}$
• Excluir el número de secuencias que contienen $44$ que es $\frac{7!}{1!2!2!2!}$
• Incluir el número de secuencias que contienen $11$ y $22$ que es $\frac{6!}{1!1!2!2!}$
• Incluir el número de secuencias que contienen $11$ y $33$ que es $\frac{6!}{1!1!2!2!}$
• Incluir el número de secuencias que contienen $11$ y $44$ que es $\frac{6!}{1!1!2!2!}$
• Incluir el número de secuencias que contienen $22$ y $33$ que es $\frac{6!}{1!1!2!2!}$
• Incluir el número de secuencias que contienen $22$ y $44$ que es $\frac{6!}{1!1!2!2!}$
• Incluir el número de secuencias que contienen $33$ y $44$ que es $\frac{6!}{1!1!2!2!}$
• Excluir el número de secuencias que contienen $11$ y $22$ y $33$ que es $\frac{5!}{1!1!1!2!}$
• Excluir el número de secuencias que contienen $11$ y $22$ y $44$ que es $\frac{5!}{1!1!1!2!}$
• Excluir el número de secuencias que contienen $11$ y $33$ y $44$ que es $\frac{5!}{1!1!1!2!}$
• Excluir el número de secuencias que contienen $22$ y $33$ y $44$ que es $\frac{5!}{1!1!1!2!}$
• Incluir el número de secuencias que contienen $11$ y $22$ y $33$ y $44$ que es $\frac{4!}{1!1!1!1!}$

---

Por lo tanto, el número de estas secuencias es $\sum\limits_{n=0}^{4}(-1)^n\cdot\binom4n\cdot\frac{(8-n)!}{(1!)^n(2!)^{4-n}}=864$ .

Answer 2

Utilice Principio de inclusión-exclusión .

Existen $\frac{8!}{2^4}$ Números de 8 cifras que pueden formarse con dos 1, dos 2, dos 3 y dos 4.

i) ¿Cuántos de estos números de 8 cifras tienen dos 1 adyacentes? Hay $7\cdot \frac{6!}{2^3}$ esos números.

ii) ¿Cuántos de estos números de 8 cifras tienen dos 1 adyacentes y dos 2 adyacentes en este orden? Hay $15\cdot \frac{4!}{2^2}$ esos números.

iii) ¿Cuántos de estos números de 8 cifras tienen dos 1 adyacentes, dos 2 adyacentes y dos 3 adyacentes en este orden? Hay $10\cdot \frac{2!}{2^1}$ esos números.

iv) ¿Cuántos de estos números de 8 cifras tienen dos 1 adyacentes, dos 2 adyacentes, dos 3 adyacentes y dos 4 adyacentes en este orden? Sólo hay $1$ ese número.

De ahí que el resultado final sea (¿por qué?): $$\frac{8!}{2^4}-4\cdot7\cdot \frac{6!}{2^3} +(4\cdot 3)\cdot 15\cdot \frac{4!}{2^2} -(4\cdot 3\cdot 2)\cdot 10\cdot \frac{2!}{2^1} +(4!)\cdot 1\cdot \frac{0!}{2^0}=864.$$