Contar subconjuntos.

Question

Sé que podemos utilizar la inducción para demostrar afirmaciones sobre el recuento de varios tipos de subconjuntos de un conjunto y que tenemos que aplicar la misma idea para contar el número de pares de subconjuntos disjuntos de un conjunto.

Me han dado las siguientes definiciones:

• $(S_{n})$ : Dejemos que $n∈N$ . Definimos el conjunto $S_{n} = \{0, 1, . . . , n−1\}$ (con $S_{0}$ obviamente $= ∅$ ). Tenga en cuenta que $|S_{n}| = n$ .
• $(DP_{n})$ : Dejemos que $n∈N$ . Definimos el conjunto de pares de subconjuntos disjuntos de $S_{n}$ como: $$ DP_{n}=\{(A, B) \ | \ A, B ⊆ S_{n} \ \text{and} \ A ∩ B = ∅\} $$

De esto he deducido para $n = 0$ , $S_{n} = ∅$ y $DP_{n} = \{(∅, ∅)\}$ . Para $n = 3$ , $S_{n}= \{0, 1, 2\}$ Algunos elementos de $DP_{3}$ son $(\{1\}, \{0, 2\})$ y $(\{0, 1, 2\}, ∅)$ y esa orden asuntos en tuplas para que el par $(\{0, 2\}, \{1\})$ en $DP_{3}$ y se considera diferente de $(\{1\}, \{0, 2\})$ . Por favor, corregidme si alguna de estas suposiciones es errónea.

(a) ¿Qué son $DP_{1}$ y $DP_{2}$ explícitamente en notación de conjunto?

(b) Encuentre una fórmula para el tamaño de $DP_{n}$ (en términos de $n$ ), y luego demuestre que su fórmula es correcta para todos los valores de $n$ ( $\forall n \in \mathbb{N}$ ).

Answer 1

De esto he deducido para $n = 0$ , $S_{n} = ∅$ y $DP_{n} = \{(∅, > ∅)\}$ . Para $n = 3$ , $S_{n}= \{0, 1, 2\}$ Algunos elementos de $DP_{3}$ son $(\{1\}, \{0, 2\})$ y $(\{0, 1, 2\}, ∅)$ y esa orden asuntos en tuplas para que el par $(\{0, 2\}, \{1\})$ en $DP_{3}$ y se considera diferente de $(\{1\}, \{0, 2\})$ .

Sí, esto es correcto.

(a) Empezar desde $S_0=\{\}$ , $DP_0 = \{(\emptyset, \emptyset)\}$

Añade los pares debidos al nuevo elemento $0$ en $S_1=\{0\}$ : $$ DP_1 = DP_0 \cup \{(\emptyset,0), (0,\emptyset) \} $$

Del mismo modo, los pares debidos al nuevo elemento $1$ en $S_2=\{0,1\}$ : $$ DP_2 = DP_1\cup \{(0,1),(1,0),(1,\emptyset),...,(\{0,1 \},\emptyset) \} $$

Obsérvese que la estructura recursiva de $DP_n$ . Esto es clave para una prueba inductiva; cuando lo intentes, lo verás: $|DP_n|=|DP_{n-1}|+2\cdot 3^{n-1}$

(b) Se trata de la misma fórmula prevista en el pregunta enlazada por Ross Millikan aunque aquí explicaré un poco más.

Puedes elegir cualquier $m$ elementos fuera de $n$ para formar un subconjunto $A$ (el número de formas de hacerlo viene dado por el cofifiente binomial ); luego para formar el otro subconjunto disjunto $B$ puede elegir cualquier combinación de los restantes $n-m$ elementos. Hay $2^{n-m}$ posibilidades.( ¿Por qué? )

Para concluir, para cada subconjunto $A$ de tamaño $m$ (de los cuales hay $\binom{n}{m}$ ), hay $2^{n-m}$ subconjuntos disjuntos ( $B$ ); y $m$ puede variar de cero (cuando $A$ es el conjunto vacío) hasta $n$ (cuando $B$ es el conjunto vacío). Así nos da:

$$ \sum_{m=0}^{n}\binom{n}{m}2^{n-m} = \sum_{m=0}^{n}\binom{n}{m}2^{n-m}\cdot 1^m = 3^n $$ La última igualdad se deduce del teorema del binomio: $$ (a+b)^n =\sum_{m=0}^n a^{n-m}\cdot b^m $$

Lo anterior es una prueba suficiente, pero por la forma en que está formulada la pregunta parece que te pide que demuestres rigurosamente que ese $DP_n$ tiene $3^n$ elementos mediante el uso de la inducción en $n$ .

Una pista: Supongamos que $DP_n$ tiene $3^n$ elementos y contar el número de pares de subconjuntos en $DP_{n+1}$ que contienen el nuevo elemento $n$ de $S_{n+1}=\{0,1,2...n\}$ . (Como en (a) (arriba).

Lea la prueba combinatoria de La identidad de Pascal para inspirarse si es necesario.

Pista #2: El número de subconjuntos $A$ de tamaño $k$ que contiene el nuevo elemento $n$ de $S_{n+1}=\{0,1,2...n\}$ es $\binom{n-1}{k-1}$ (ya que $n$ ya está en $A$ , sólo $k-1$ se pueden recoger más); y $k$ puede variar de $1$ a $n$ . Además, para cada uno de estos $A$ puede elegir cualquier combinación de elementos de los restantes $n-k$ elementos para obtener $B$ . Además, para cada $(A,B)$ también tienes $(B,A)$ ; acuérdate de tenerlo en cuenta.

Answer 2

Esto es lo que hice para (b):

Dejemos que $n \in \mathbb{N}$ . Entonces, para el caso base, $n=0$ : \begin {align*} L.H.S.=|DP_0|=1 \\ R.H.S.=3^0=1 \end {align*} Así que $P(0)$ se mantiene.

Suponiendo que $P(k)$ se mantiene para $n=k$ tenemos $|DP_k|=3^k$ Y tenemos que demostrar $|DP_{k+1}|=3^{k+1}$ para $n=k+1$ .

Ahora, \begin {align*} |DP_{k+1}| &=|DP_k| \cup \text {los pares de elementos del conjunto $S_k$ } \}| \\ &=3^k +2,3^k && \text {(El $2$ es para dar cuenta de los pares que se producen} \\ &= 3^k(1+2) && \text {en el conjunto posterior que se añade desde el orden} \\ &= 3^k.3 && \text {importa en las tuplas.)} \\ &= 3^{k+1} \end {align*} que es lo que queríamos mostrar.

$\therefore P(k+1)$ se mantiene.