Quante coppie non ordinate di file $\{A,B\}$ di sottoinsiemi sono possibili a determinate condizioni?

Aug 24 2020

Permettere $S=\{1,2,\ldots,n\}$. Trova il numero di coppie non ordinate$\{A,B\}$ di sottoinsiemi di $S$ usch quello $A$ e $B$ sono disgiunti, dove $A$ e $B$ o entrambi possono essere vuoti.

Questa domanda qui [1] risolve un tipo di problema simile ma non prende in considerazione insiemi vuoti.

Il mio approccio:

Selezioniamo un sottoinsieme $A$ primo che significherebbe che la selezione del sottoinsieme $B$ dipende da $A$.

Permettere $n(A)$ denota il numero di elementi nel sottoinsieme $A$. Supponiamo$n(A)=k$, quindi il sottoinsieme $B$ ha il controllo sulla selezione dei rimanenti $(n-k)$ elementi che significa che il numero di tali coppie possibili $=\binom{n}{k}2^{n-k}$

$$\therefore \text {Total unordered pairs} =\sum_{k=0}^{n}\binom{n}{k}2^{n-k}=\sum_{k=0}^{n}\binom{n}{n-k}2^{n-k}$$ $$=(1+2)^n=3^n$$

Voglio solo verificare la mia soluzione. Quindi per favore controlla eventuali errori nella mia soluzione e offri suggerimenti.

GRAZIE

Correzione : questo è il numero totale di coppie ORDINATE includendo entrambi i set di casi vuoti. Come affermato da Phicar nella risposta, per mantenere entrambi i set vuoti anche nelle coppie non ordinate, può essere escluso prima e può essere aggiunto in seguito, dando quindi il numero totale di coppie non ordinate da$\dfrac{3^n-1}{2}+1$.

Risposte

2 Phicar Aug 24 2020 at 18:06

Fai attenzione, stai prendendo un ordine dicendo "Selezioniamo un sottoinsieme $A$".

Ad esempio, se$n=1$ stai contando $3.$ Principalmente: $(\{1\},\emptyset),(\emptyset,\{1\}),(\emptyset,\emptyset).$Quindi dovrai ritirare l'ordine. Nota che non puoi semplicemente dividere per$2$perché uno dei casi è il set vuoto due volte. Quindi tiralo fuori, dividi per$2$ e aggiungilo più tardi: $$\frac{3^n-1}{2}+1.$$

1 GeoffreyTrang Aug 24 2020 at 18:22

Per ogni $x \in S$, abbiamo tre possibilità:

  • $x \in A$, ma $x \not\in B$
  • $x \in B$, ma $x \not\in A$
  • $x \not\in A$ e $x \not\in B$

Questo da $3^n$ coppie ordinate di sottoinsiemi disgiunti di$S$. Per ottenere coppie non ordinate, dobbiamo trattare il caso in cui$A=B=\emptyset$ diversamente dal caso in cui $A \neq B$.

Il numero risultante di coppie non ordinate è quindi $\frac{3^n-1}{2}+1$.