¿Cuántas combinaciones existen cuando tenemos K subconjuntos en los que cada subconjunto es un subconjunto del subconjunto siguiente?

Question

Sea el universo S los números naturales entre 1 y N. Y digamos que tenemos K subconjuntos consecutivos $A_1 \subseteq A_2 \subseteq \ldots \subseteq A_K \subseteq S $ donde todos los subconjuntos $$A_i$$ debe ser un subconjunto de $$A_i+1$$ y subconjunto $$A_K$$ debe ser un subconjunto del universo S.

Note : no es necesario que los subconjuntos sean subconjuntos propios.

Si nos dan N y K, ¿cuántas cadenas de subconjuntos diferentes hay?

Ejemplo 1: N = 2, K = 1

Hay 4 formas de hacer 1 cadena de subconjuntos válida.

{} (seleccionando el conjunto vacío)

{1}

{2}

{1,2}

Ejemplo 2: N = 1, K = 2

Hay 3 formas de hacer 2 cadenas de subconjuntos válidas.

{},{}

{},{1}

{1},{1}

Ejemplo 3: N = 2, K = 2

{},{}

{},{1}

{},{2}

{},{1, 2}

{1},{1}

{1},{1,2}

{2}, {1,2}

{2}, {2}

{1,2},{1,2}

Answer 1

Una solución $A_1 \subseteq A_2 \subseteq \ldots \subseteq A_K \subseteq S $ corresponde a una partición de $S$ en $K+1$ subconjuntos disjuntos $A_1, A_2 \backslash A_1, \ldots, A_K \backslash A_{K-1}, S \backslash A_K$ . El número de estos se ve fácilmente que es $(K+1)^N$ ya que cada miembro de $S$ puede entrar en cualquiera de los $K+1$ subconjuntos.