Cuenta las formas de elegir subconjuntos distintos $A_0, A_1, . . . , A_n$ de ${1, 2, . . . , n}$ tal que $A_0 ⊂ A_1 ⊂ . . . ⊂ A_n$

Question

Me hicieron esta pregunta. Cuente las formas de elegir subconjuntos distintos $A_0, A_1, . . . , A_n$ de ${1, 2, . . . , n}$ tal que $A_0 A_1 . . . A_n$

He seguido un ejemplo diferente para resolver esto

Contemos el número de formas de asignar elementos a $A_0; A_1 - A_0; A_2 - A_1, ..... , A_n - A_n-1$ y X. Ahora, sin embargo, no hay restricciones, por lo que cada uno de los n elementos puede elegir cualquiera de los n + 2 conjuntos, lo que da $(n+2)^n$

¿Es correcta mi solución? Me da la sensación de que está inacabada o que podría ser más detallada.

Answer 1

A partir de las inclusiones estrictas podemos obtener el tamaño de cada conjunto en una cadena: $|A_i| \ge |A_{i-1}| + 1$ Así que $|A_n| \ge n + |A_0|$ . Por otra parte, $A_n \subseteq \{1, \dotsc, n\}$ ¡! Esto obliga a $|A_i| = i$ .

En particular, $A_0$ está vacío, hay $n$ opciones para $A_1$ y $n-1$ opciones para $A_2$ dado $A_1$ etc.