Wenn A={x1,x2,x3,…,xn}A={x1,x2,x3,…,xn}A= \{ x_1 , x_2 , x_3 , \ldots , x_n \}. Wie viele Teilmengen gibt es?

Ich bin nicht einverstanden. Beispielsweise ist die Anzahl der Teilmengen der Größe 2

Ist eine bekannte Tatsache, dass die Antwort ist$2^n$. Beweis durch Induktion:

• $A_1 = \{x_1\}$hat zwei Teilmengen:$\emptyset,A_1$.
• Angenommen, wahr bis zu$n$. Die Teilmengen von$A_{n+1} = \{x_1,\dots,x_{n+1}\}$sind die Teilmengen von$A_n = \{x_1,\dots,x_n\}$plus die Teilmengen von$A_n$Union$\{x_{n+1}\}$.

Warum denkst du wird es geben$n-(k-1)$Teilmengen der Größe$k$?

Nehmen wir an, Sie haben eine Reihe von$25$Elemente,$\{1,2,3,....., 25\}$und Sie wollen sehen, wer viele Teilmengen der Größe ist$2$es gibt.

Du kannst haben$\{1,2\}, \{1,3\}......, \{2, 25\}$. Das ist$24 = n- 1$. Aber das sind alle mit dem Element$1$. Was ist mit Teilmengen ohne das Element$1$.

$\{2,3\}...... , \{2,25\}$Ist$23$Und$\{3,4\}...\{3,25\}$Ist$23$. und so weiter bis hin zu$\{24,25\}$Sein$1$.

Also addieren wir die, die wir haben$24 + 23 + 22 + ... + 1 = 300$.

Aber was ist mit Teilmengen der Größe?$3$.$\{1,2,3\} ... \{1,2,25\}$Ist$23$Und$\{1,3,4\}$Zu$\{1,3,25\}$Ist$22$Und$\{1,2,3\}...\{1,24,25\}$Ist$23 + 22 + ... + 1 = 276$Und$\{2,3,4\}...\{2,24,25\}$Ist$22 + .... + 1 = 253$. und so weiter, also alle Teilmengen der Größe$3$= \sum_{m=1}^{23} \sum_{i=1}^mi = \sum_{m=1}^{23} \frac {m(m+1)}2$.

Und dann Teilmengen der Größe zu machen$4$Wir bekommen .... na ja, Kopfschmerzen.

Ein bisschen Nachdenken ist diese Auswahl$k$Elemente aus$25$(oder$n$) ist buchstäblich wählen$k$Elemente aus$25$(oder$n$). Also die Anzahl der Teilmengen der Größe$k$Ist${n \choose k}$. Buchstäblich.

[Dies würde das implizieren${n \choose 3} = \sum_{i=1}^{n-2}\frac {i(i+1)}2$. Macht es?]

Die Anzahl der richtigen Teilmengen wäre also jedenfalls:$\sum_{i=1}^{n-1} {n\choose i}$.

Aber... kann man das vereinfachen. Sie sollten ungefähr 14 Stunden damit spielen.

$n =2\implies \sum{n\choose i} = 2$

$n = 3\implies \sum{n\choose i} = {3\choose 1 } + {3\choose 2} = 6$.

$n = 4 \implies \sum{n\choose i} = {4\choose 1} + {4\choose 2} + {4\choose 3} = 4 + 6 + 4 = 14$.

Fällt dir etwas auf?

Nun, hier ist ein Vorschlag. Versuchen Sie, die Anzahl aller Teilmengen einschließlich der beiden falschen Teilmengen zu berechnen,$\emptyset$Und$A$.

Dann ist die Lösung$\sum_{i=0}^n{n\choose i}$.

Dann ist die Anzahl aller Teilmengen

$n = 2; \sum {n\choose i} = {2 \choose 0} + {2\choose 1} + {2\choose 2} = 1+2+1 = 4$.

$n =3; \sum {n\choose i} = {3\choose 0}+ {3 \choose 1} + {3\choose 2} + {3\choose 3} = 1 + 3 + 3 + 1 = 8$.

Und$n= 4; \sum {n\choose i} = {4\choose 0} + {4\choose 1} + {4\choose 2} + {4 \choose 3} + {4\choose 4} = 1 + 4 +6+ 4 + 1 = 16$.

Beachten Sie nichts.

Es scheint, dass die Anzahl aller Teilmengen ist$2^n$.

Warum sollte das sein? Wir könnten es wahrscheinlich beweisen$\sum_{i=0}^n{n\choose i} = 2^n$durch Induktion .... Aber was bedeutet das ?

Nun, betrachten Sie diesen einen Satz:

Für einen der$n$Elemente von$A$, entweder ist das Element in einer bestimmten Teilmenge von oder nicht$A$.

Denk darüber nach. Hätten wir das von Anfang an bedacht, hätte das Ganze wahrscheinlich einfacher sein können.

Es gibt