¿Cuántos pares de subconjuntos disjuntos hay en un conjunto de $n$ elementos?

Question

-¿Cuántos pares de subconjuntos disjuntos hay en un conjunto de $n$ elementos?

He hecho otros trabajos sobre pares de subconjuntos donde uno es un subconjunto del segundo, utilizando funciones similares a funciones características. Pero no tengo idea sobre este.

Answer 1

Suponiendo que te refieres a pares ordenados:

Paso 1: Elige un subconjunto.

Paso 2: Elige un subconjunto de los elementos restantes (no elegidos).

Si restringimos nuestra atención a la situación en la que el primer subconjunto tiene tamaño $m$, hay $\binom{n}{m}$ formas de elegir el primer subconjunto, y $2^{n-m}$ formas de elegir el segundo dado el primero. (Esto asume que el conjunto vacío es válido). Entonces, el número que deseas sería $$ \sum_{m=0}^{n}\binom{n}{m}2^{n-m}. $$ ¿Cómo podemos simplificar esto? Bueno, podemos escribir $$ \sum_{m=0}^{n}\binom{n}{m}2^{n-m}=2^n\sum_{m=0}^{n}\binom{n}{m}\left(\frac{1}{2}\right)^m=2^n\left(1+\frac{1}{2}\right)^n=3^n. $$

Eso puede parecer sorprendente; pero hay otra forma en que podríamos haberlo obtenido. A cada uno de tus $n$ elementos, asígnale una etiqueta $0$, $1`o $2$. Los que tienen $0$ se dejan fuera; los que tienen $1`ocurren en el primer subconjunto; y los etiquetados con $2`ocurren en el segundo subconjunto. Esta es una biyección que muestra que hay tantos arreglos como funciones de $n`objetos a $\{0,1,2\}$, que también es precisamente $3^n$.

Answer 2

Para cada subconjunto $A$ con $k$ elementos en el conjunto $X$ con $n$ elementos, un subconjunto emparejado es cualquier subconjunto $B\subset \mathcal P(X-A)$, que tiene $2^{n-k}$ elementos. Por lo tanto, el número de pares de subconjuntos disjuntos de $X$, teniendo en cuenta el orden, es: $$\sum_{k=0}^n\binom nk 2^{n-k}=\sum_{k=0}^n\binom nk 2^k=3^n.$$ Si no se tiene en cuenta el orden, ya que cada par se obtiene dos veces, este número se convierte en $\;\dfrac{3^n}2$.