Número de conjuntos cuádruples ordenados

Question

Estoy tratando de abordar la siguiente cuestión, pero no tengo ni idea de cómo hacerlo (sé que no es muy popular no mostrar ningún esfuerzo, pero esta vez realmente no sé qué hacer).

He visto una solución que utiliza la inclusión-exclusión, pero parece ser incorrecta y no entiendo cómo se relaciona con la inclusión-exclusión.

Halla el número de cuádruples ordenados $(A,B,C,D)$ donde $A,B,C,D$ son conjuntos incluidos en $\{1,2,...,n\}$ tal que $A \cup B \cup C \cup D=\{1,2,...,n\}$

Por favor, explique cualquier razonamiento de solución, ¡gracias!

Answer 1

He aquí una solución que no utiliza la inclusión-exclusión:

Cada elemento $i\in\{1,2,\dots,n\}$ debe estar en al menos uno de los conjuntos $A$ , $B$ , $C$ , $D$ . Así, podemos elegir cualquier subconjunto no vacío de $\{A,B,C,D\}$ para lo cual $i$ es un elemento de los conjuntos elegidos. Hay $15$ formas de hacerlo ya que hay $15$ subconjuntos no vacíos de $\{A,B,C,D\}$ . Como tenemos que hacer esto para $i=1,2,\dots,n$ Hay $15^n$ formas de completar el proceso.

[Por cierto, creo que esto debería ser lo mismo que la solución de inclusión-exclusión de este problema, que creo que es $2^{4n}-{n\choose 1}2^{4(n-1)}+{n\choose2}2^{4(n-2)}-...=(16-1)^n$ por el teorema del binomio].