Pares de la no-vacío conjuntos disjuntos

Question

Pregunta: Deje $S=\{1,2, \cdots, 10 \}$. A continuación, el número de pares de $(A, B)$ donde $A$ y $B$ son no vacía de subconjuntos disjuntos de a $S$ es?

[Yo podría resolver la cuestión como se muestra a continuación, pero que implica el cálculo de un tedioso suma de los productos, que tomar un montón de tiempo. Típicamente, se espera resolver en un par de minutos, así que me preguntaba si había una manera más rápida de hacer esto.]

Mi planteamiento: Deje que el conjunto de $A$ consta de $x$ elementos. Hay ${10 \choose x}$ formas de hacer esa selección.

Ahora estamos a la izquierda con $10-x$ elementos.

Deje que el conjunto de $B$ consta de $y$ elementos. Esta selección se puede hacer por ${10-x \choose y}$ maneras.

El número total de maneras en que se puede encontrar por sumar más el producto de los dos anteriores como $\sum_{x=1}^{9} \sum_{y=1}^{10-x} {10 \choose x}{10-x \choose y} $, lo que viene a ser $57002$

Answer 1

Supongamos que hemos creado $A$, $B$ y $S=\{1,2,...10\}$. Así, para cada $x\in S$ usted puede poner en exactamente uno de estos conjuntos: $A$ o en $B$ o $(A\cup B)'$. Así, para cada $x$ tienes 3 opciones y así usted puede optar $A,B$ $3^{10}$ maneras.

Ahora tenemos que restar todas las parejas donde uno de los conjuntos es vacía. Si $A$ está vacía, $B$ podría ser cualquier subconjunto aparte de $A$. Así que tenemos $2^{10}$ opciones. Lo mismo es cierto si $B$ está vacía. Así que tenemos $2^{11}$ tal par de conjuntos. Pero tenemos par $(\emptyset,\emptyset )$ contado dos veces, tenemos que restar $2^{11}-1$ mala pares de conjuntos.

Así que el finaly resultado es $3^{10}-2^{11}+1$

Answer 2

También es interesante notar que la suma de obtener se puede simplificar de la siguiente manera, utilizando el teorema del binomio: \begin{align} \sum_{x=1}^{9}\sum_{y=1}^{10-x}{ 10 \choose x}{ 10-x \choose y} &= \sum_{x=1}^{9}{ 10 \choose x}\left(\sum_{y=0}^{10-x}{ 10-x \choose y} -1 \right)\\ &=\sum_{x=1}^{9}{ 10 \choose x} (2^{10-x} -1) \\ &= \sum_{x=0}^{10}{ 10 \choose x}2^{10-x} -2^{10}-1 - \sum_{x=0}^{10}{ 10 \choose x}+1+1 \\ &= 3^{10}-2^{10}-1-2^{10}+1+1 \\ &= 3^{10}-2^{11}+1 \end{align} Y conseguir así una bastante interesante de identidad.