Anzahl Teilmengen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wie viele Teilmengen hat {0,1,2,3,4,5,6,7,8,9}? |
Hallo,
Die Definition der Teilmenge ist mir bekannt. Wie aber rechnet man das? Ich komme nicht drauf.
|
|
| |
|
Hallo Andi,
Tipp: Überlege dir doch zunächst wie viele Teilmengen {1, 2, 3} hat.
Schreibe sie ruhig alle auf. Es sind ja nicht so viele.
Nächster Schritt: Wie viele Teilmengen hat {1, 2, 3, 4} ?
Kannst du das jetzt für größere Mengen verallgemeinern?
Grüße
fz
|
|
|
| |
|
Also,
{1,2,3} besitzt folgende Teilmengen:
{1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}, {}.
Macht insg. 8 Teilmengen.
{1,2,3,4} besitzt folgende Teilmengen:
{1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,3}, {1,4}, {2,4}, {1,2,3,4}, {}
Macht insg. 12 Teilmengen.
Die zweite Teilmengenanzahl ist um die Zahl ihres höchsten Gliedes gestiegen, um 4. Wie aber soll ich das in einer Formel formulieren?
|
|
|
| |
|
Hi!
> Also,
>
> {1,2,3} besitzt folgende Teilmengen:
>
> {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}, {}.
>
> Macht insg. 8 Teilmengen.
![[ok]](/images/smileys/ok.gif "[ok]")
>
> {1,2,3,4} besitzt folgende Teilmengen:
>
> {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,3}, {1,4},
> {2,4}, {1,2,3,4}, {}
>
> Macht insg. 12 Teilmengen.
>
![[notok]](/images/smileys/notok.gif "[notok]")
Denke darüber noch einmal nach, ob es nicht noch mehr Teilmengen gibt.
Tipp: Gibt es hier auch dreielementige Teilmengen?
Valerie
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:43 Mi 29.08.2012 | | Autor: | reverend |
@Andi:
kleiner Tipp - ist [mm] $\{1,2,4\}$ [/mm] nicht auch eine Teilmenge von [mm] $\{1,2,3,4\}$?
[/mm]
lg
rev
|
|
|
| |
|
Hallo Andi,
es gibt mehrere Wege zur Lösung.
Auf dem Weg, den Franz zeigt, hast Du eine Zahl von Teilmengen einer kleineren Menge wie eben [mm] $\{1,2,3\}$. [/mm] Wenn jetzt ein viertes Element hinzukommt, die Menge also [mm] $\{1,2,3,4\}$ [/mm] ist, dann sind die bisherigen Teilmengen auch Teilmengen dieser Menge. Die einzigen, die noch nicht erfasst sind, sind die, die die 4 enthalten. Und das müssen noch einmal genauso viele sein.
Jede bisherige Teilmenge gibt es also sozusagen zweimal in der neuen Mengen, nämlich einmal ohne die 4 und einmal mit.
Ein anderer Weg ist dieser (eigentlich gar nicht so anders, aber ein bisschen anders verkleidet).
Wir nehmen Deine Menge [mm] $\{0,1,2,3,4,5,6,7,8,9\}$ [/mm] und betrachten mal eine Teilmenge, z.B. [mm] $\{0,2,3,6,9\}.
[/mm]
Die schreibe ich mir jetzt so auf: erst mal eine 1, weil die 0 enthalten ist, dann eine 0, weil die 1 nicht enthalten ist, dann zwei Einsen für die 2 und 3, zwei Nullen für 4 und 5, eine Eins für die 6, zwei Nullen für 7,8 und schließlich eine 1 für die 9.
Also: 1011001001.
Aus dieser Zeichenfolge kann ich die Teilmenge auch wieder rekonstruieren.
Wieviele solche zehnstelligen Zeichenfolgen gibt es?
Grüße
reverend
|
|
|
| |
|
Gibt es nicht einen einfacheren Weg, als alle Möglichkeiten abzuzählen? Das dauert ja ewig, wenn ich das immer aufschreibe.
|
|
|
| |
|
Hi!
> Gibt es nicht einen einfacheren Weg, als alle
> Möglichkeiten abzuzählen? Das dauert ja ewig, wenn ich
> das immer aufschreibe.
>
>
Na klar, aber wieviele Teilmengen hat den nun deine vierelementige Menge?
Valerie
|
|
|
| |
|
Die dreier Paarungen hatte ich vergessen: {1,2,3}, {2,3,4}, {1,3,4}, {1,2,4}.
Nun hat meine Menge {1,2,3,4} 16 Teilmengen.
|
|
|
| |
|
> Die dreier Paarungen hatte ich vergessen: {1,2,3}, {2,3,4},
> {1,3,4}, {1,2,4}.
>
> Nun hat meine Menge {1,2,3,4} 16 Teilmengen.
Die Anzahl der Teilmengen einer Menge mit x Elementen beträgt allgemein :
[mm] $2^x$
[/mm]
In deinen beiden Fällen also [mm] $2^3=8$ [/mm] und [mm] $2^4=16$
[/mm]
Sieh dir dazu auch einmal das Thema "Potenzmenge" an.
Was ist nun also die Lösung deiner Ausgangsaufgabenstellung?
Valerie
|
|
|
| |
|
Doch so einfach, dann lautet die Antwort:
Die Menge {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} hat 1024 Teilmengen.
x=10 (10 Elemente)
[mm] 2^{10}=1024
[/mm]
Ich war auf dem völlig falschen Dampfer, ich dachte das hat etwas mit Binomialkoeffizienten zu tun. Ich werde mir das Thema noch mal anschauen. Danke!
|
|
|
| |
|
Hallo Andi,
> Doch so einfach, dann lautet die Antwort:
>
> Die Menge {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} hat 1024
> Teilmengen.
>
> x=10 (10 Elemente)
>
> [mm]2^{10}=1024[/mm]
Ja, richtig.
> Ich war auf dem völlig falschen Dampfer, ich dachte das
> hat etwas mit Binomialkoeffizienten zu tun. Ich werde mir
> das Thema noch mal anschauen. Danke!
Hat es auch.
Eine n-elementige Menge hat genau [mm] \vektor{n\\k} [/mm] Teilmengen, die k-elementig sind.
Und außerdem ist [mm] \summe_{k=0}^{n}\vektor{n\\k}=2^n
[/mm]
Lies nochmal meinen ersten Beitrag, dann solltest Du jetzt leicht verstehen, wieso sich die Zahl der Teilmengen mit wachsendem n immer verdoppelt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:43 Mi 29.08.2012 | | Autor: | Marcel |
Hallo Reverend,
> Hallo Andi,
>
> > Doch so einfach, dann lautet die Antwort:
> >
> > Die Menge {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} hat 1024
> > Teilmengen.
> >
> > x=10 (10 Elemente)
> >
> > [mm]2^{10}=1024[/mm]
>
> Ja, richtig.
>
> > Ich war auf dem völlig falschen Dampfer, ich dachte das
> > hat etwas mit Binomialkoeffizienten zu tun. Ich werde mir
> > das Thema noch mal anschauen. Danke!
>
> Hat es auch.
> Eine n-elementige Menge hat genau [mm]\vektor{n\\k}[/mm]
> Teilmengen, die k-elementig sind.
>
> Und außerdem ist [mm]\summe_{k=0}^{n}\vektor{n\\k}=2^n[/mm]
Beweis: [mm] $2^n=(1+1)^n=\sum_{k=0}^n [/mm] {n [mm] \choose k}1^k *1^{n-k}=\sum_{k=0}^n [/mm] {n [mm] \choose k}\,.$
[/mm]
> Lies nochmal meinen ersten Beitrag, dann solltest Du jetzt
> leicht verstehen, wieso sich die Zahl der Teilmengen mit
> wachsendem n immer verdoppelt.
Ich fand' eigentlich Deine "Zeichenkettenidee" [mm] ($n\,$ [/mm] Stellen), wo man bei einer Teilmenge der Ausgangsmenge jedem Element eine [mm] $1\,$ [/mm] zuordnet,
wenn es in der Menge liegt, und andernfalls eine [mm] $0\,,$
[/mm]
hier irgendwie die schönste. Die Bijektivität der so konstruierten Abbildung
wäre nachzuweisen, aber das geht elementar (man könnte natürlich
auch mit der Elementzahl argumentieren, aber das wollen wir ja gerade
nicht).
Gruß,
Marcel
|
|
|
| |
|
Was ich bei der Formel für den Binomialkoeffizienten noch nicht ganz verstehe:
Was ist eigentlich das k? n ist die Anzahl der Elemente der Menge. Bei meinem Beispiel waren das 10 (inklusive der 0).
Aber was ist k?
k ist die Anzahl der ausgewählten Elemente. Aber ich stelle mir dann immer Kugeln vor, die man zieht oder so etwas in der Richtung. Bei meinem Beispiel wähle ich ja nichts aus in diesem Sinne. Also k-elementige Teilmengen sind mit k gemeint. Also die Anzahl der Teilmengen? Die weiß ich ja aber nicht vorher.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:55 Mi 29.08.2012 | | Autor: | Marcel |
Hallo,
> Was ich bei der Formel für den Binomialkoeffizienten noch
> nicht ganz verstehe:
>
> Was ist eigentlich das k? n ist die Anzahl der Elemente der
> Menge. Bei meinem Beispiel waren das 10 (inklusive der 0).
>
> Aber was ist k?
>
> k ist die Anzahl der ausgewählten Elemente. Aber ich
> stelle mir dann immer Kugeln vor, die man zieht oder so
> etwas in der Richtung. Bei meinem Beispiel wähle ich ja
> nichts aus in diesem Sinne. Also k-elementige Teilmengen
> sind mit k gemeint. Also die Anzahl der Teilmengen? Die
> weiß ich ja aber nicht vorher.
nein, [mm] $k\,$ [/mm] ist die Anzahl der Elemente, die eine betrachtete Teilmenge
der [mm] $n\,$-elementigen [/mm] Ausgangsmenge haben soll. Machen wir ein
einfaches Beispiel:
Sei [mm] $M:=\{a,b,c\}$ [/mm] 3-elementig. Wieviele 2-elementige Teilmengen von
[mm] $M\,$ [/mm] gibt es?
Wir schreiben (weil das hier ja alles relativ übersichtlich ist) einfach mal
[mm] $\text{Pot}(M)$ [/mm] hin, und ich markiere Dir dann alle 2-elementigen
Teilmengen von [mm] $M\,$ [/mm] in blau, alle anderen in rot:
[mm] $$\text{Pot}(M)=\{\red{\emptyset},\,\red{\{a\}},\,\red{\{b\}},\,\red{\{c\}},\,\blue{\{a,\,b\}},\,\blue{\{a,\,c\}},\,\blue{\{b,\,c\}},\,\red{\{a,\,b,\,c\}},\}$$
[/mm]
Siehst Du: Nur die blauen Elemente in der Potenzmenge sind selber
Mengen, die genau 2 Elemente beinhalten.
Deswegen hatte Reverend ja auch geschrieben, wie man die Anzahl der
Elemente der Potenzmenge einer [mm] $n\,$-elementigen [/mm] Menge bestimmen
kann:
Sei [mm] $n\,$ [/mm] fest und [mm] $M\,$ [/mm] dann [mm] $n\,$-elementig. [/mm] Die Potenzmenge [mm] $\text{Pot}(M)$
[/mm]
läßt sich dann schreiben als disjunkte Vereinigung über
alle 0-elementigen Teilmengen von [mm] $M\,$
[/mm]
vereint mit
allen 1-elementigen Teilmengen von [mm] $M\,$
[/mm]
vereint mit
allen 2-elementigen Teilmengen von [mm] $M\,$
[/mm]
.
.
.
vereint mit
allen [mm] $k\,$-elementigen [/mm] (mit $0 [mm] \le [/mm] k [mm] \le [/mm] n$ und $k [mm] \in \IN_0$) [/mm] Teilmengen von [mm] $M\,$
[/mm]
.
.
.
vereint mit
allen n-elementigen Teilmengen von [mm] $M\,\,.$
[/mm]
P.S.
1.) Gib' mir zur Übung nun mal bitte alle 3-elementigen Teilmengen von [mm] $\{1,\;1+i,\;1-i,\;-i\}$ [/mm] an. [mm] ($i\,$ [/mm] ist die imaginäre Einheit - das ist für Dich
hier aber uninteressant, außer vielleicht, dass $i [mm] \notin \IR$ [/mm] und damit
insbesondere etwa [mm] $i\not=-1$ [/mm] ist!)
Wieiviele Mengen solltest Du erhalten?
(Letztere Frage dient zur Kontrolle für Dich selbst, ob Du nicht Mengen
vergessen - "oder aber aus Versehen doppelt aufgeführt" - hast).
2.) Beschreibe mal: Was hat die Anzahl der 6-elementigen Teilmengen einer
49-elementigen Menge mit der Gewinnwahrscheinlichkeit beim (normalen)
Lotto zu tun?
3.) Hat die Reihenfolge der Elemente einer [mm] $k\,$-elementigen [/mm] Teilmenge
einer n-elementigen Ausgangsmenge einen Einfluß auf die Anzahl der
[mm] $k\,$-elementigen [/mm] Teilmengen? (D.h., beispielhaft gefragt: Zählt man bei
etwa Mengen wie [mm] $\{a,b\}$ [/mm] und [mm] $\{b,a\}\,$ [/mm] diese nun genau einmal mit,
oder mehrfach?)
Gruß,
Marcel
|
|
|
| |
|
Das heißt für meine Aufgabe:
Wie viele Teilmengen hat {0, 1, 2, ....8, 9}?
Ich muss für jeden Wert k (0 bis 9) die Formel anstrengen? Das geht damit nicht so einfach wie mit [mm] 2^{10}=1024, [/mm] oder?
Bei deinen Beispielen habe ich folgendes raus:
1)
Es gibt 4 Möglichkeiten:
{1, 1+i, 1-i}, {1+i, 1-i, -i}, {1, 1+i, -i} und {1, 1-i, -i}.
[mm] \vektor{4\\ 3}= \bruch{4!}{3!*(4-3)!}=4
[/mm]
2)
Die Gewinnwahrscheinlichkeit errechnet sich wie folgt:
[mm] \vektor{49\\ 6}= \bruch{49!}{6!*(49-6)!}=13983816
[/mm]
3)
Man zählt sie nur einmal, weil jedes Element nur einmal in der Menge vorkommen darf. Richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:42 Mi 29.08.2012 | | Autor: | Marcel |
Hallo,
> Das heißt für meine Aufgabe:
>
> Wie viele Teilmengen hat {0, 1, 2, ....8, 9}?
>
> Ich muss für jeden Wert k (0 bis 9) die Formel anstrengen?
0 bis [mm] $\mathbf{\blue{10}}$ [/mm] - Deine Menge oben hat 10 Elemente!!
> Das geht damit nicht so einfach wie mit [mm]2^{10}=1024,[/mm] oder?
Doch. Es kann ja auch nicht sein, dass man über verschiedene richtige
Wege zu ungleichen Ergebnissen kommt, oder? Wenn Du das so machst, wie Du es angedeutet hast (also das Verfahren, was Reverend angedeutet
und ich ein wenig ausführlicher erläutert habe), dann würde man rechnen
$${10 [mm] \choose [/mm] 0}+{10 [mm] \choose 1}+\ldots+{10 \choose 10}=\sum_{k=0}^{10}{10 \choose k}\,.$$
[/mm]
(Beachte, dass für disjunkte endliche Mengen [mm] $R,S\,$ [/mm] gilt $|R [mm] \cup S|=|R|+|S|\,.$ [/mm] Allgemein gilt ja für endliche Mengen [mm] $R,S\,$ [/mm] die Formel
$|R [mm] \cup [/mm] S|=|R|+|S|-|R [mm] \cap S|\,.$)
[/mm]
Reverend hatte schonmal geschrieben
[mm] $$\sum_{k=0}^n [/mm] {n [mm] \choose k}=2^n\,,$$
[/mm]
und ich habe einen (Mini-)Beweis dafür hingeschrieben.
Natürlich könntest Du das auch induktiv nachrechnen, dann brauchst
Du aber eine Eigenschaft des Binomialkoeffizienten.
(Beachte übrigens: Die Menge [mm] $\{0,\ldots,n-1\}$ [/mm] hat [mm] $n\,$ [/mm] Elemente.
Deswegen wird oben bei der Potenzmenge auch [mm] $2^{10}$ [/mm] und nicht
[mm] $2^9$ [/mm] gerechnet, um die Anzahl der Elemente der Potenzmenge
herauszubekommen!)
> Bei deinen Beispielen habe ich folgendes raus:
>
> 1)
>
> Es gibt 4 Möglichkeiten:
Also 4 Mengen wie gefordert!
>
> {1, 1+i, 1-i}, {1+i, 1-i, -i}, {1, 1+i, -i} und {1, 1-i,
> -i}.
Genau, denn es ist ${4 [mm] \choose 3}=4\,.$ [/mm] Und wenn ich's richtig sehe,
hast Du die korrekt aufgeschrieben!
> [mm]\vektor{4\\ 3}= \bruch{4!}{3!*(4-3)!}=4[/mm]
Genau!
> 2)
>
> Die Gewinnwahrscheinlichkeit errechnet sich wie folgt:
>
> [mm]\vektor{49\\ 6}= \bruch{49!}{6!*(49-6)!}=13983816[/mm]
Das ist die Anzahl der Möglichkeiten, 6 aus 49 zu ziehen. Was ist nun hier
die Wahrscheinlichkeit, 6 richtige zu haben?
> 3)
>
> Man zählt sie nur einmal, weil jedes Element nur einmal in
> der Menge vorkommen darf. Richtig?
Die Antwort ist richtig, aber die Begründung: Da weiß ich nicht, ob Du das
richtige meinst. Du hast zwar insofern recht, dass man "doppelte
Elemente" in einer Menge nicht "erkennt" (diese werden nur einmal gezählt). Und wenn Du das so meinst, wie ich es mal (wieder an einem
Beispiel) "skizziere", dann stimmt's:
Sei [mm] $M=\{a,b,c\}\,$ [/mm] 3-elementig. Wir setzen
[mm] $$M_k:=\{L \subseteq M: \;\;|M|=k\}$$
[/mm]
für [mm] $k=1,2,3\,.$
[/mm]
Dann ist [mm] $|M_2|$ [/mm] die Anzahl aller 2-elementigen Teilmengen von [mm] $M\,.$ [/mm]
Dann ist
[mm] $$M_2=\{\{a,b\},\{a,c\},\{b,c\}\}\,.$$
[/mm]
Und damit [mm] $|M_2|=3\,.$ [/mm] Natürlich wird [mm] $\{b,a\}$ [/mm] hier nicht nochmal
gezählt, denn es ist [mm] $\{b,a\}=\{a,b\} \in M_2$ [/mm] bereits erkannt worden!
Gruß,
Marcel
|
|
|
| |
|
>
> Das ist die Anzahl der Möglichkeiten, 6 aus 49 zu ziehen.
> Was ist nun hier
> die Wahrscheinlichkeit, 6 richtige zu haben?
>
Es ist der Kehrwert des Ergebnisses, also [mm] \bruch{1}{13983816}. [/mm] Ist es generell immer der Kehrwert?
Und noch eine kleine Frage:
Unter dem Summenzeichen steht k=0. Warum steht da nicht k=1 oder 1 für das erste Element mit dem man beginnt?
Sonst top Antwort, hat mir sehr geholfen!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:38 Mi 29.08.2012 | | Autor: | Marcel |
Hallo,
> >
> > Das ist die Anzahl der Möglichkeiten, 6 aus 49 zu ziehen.
> > Was ist nun hier
> > die Wahrscheinlichkeit, 6 richtige zu haben?
> >
>
> Es ist der Kehrwert des Ergebnisses, also
> [mm]\bruch{1}{13983816}.[/mm] Ist es generell immer der Kehrwert?
nein, generell ist es die Anzahl der günstigen durch die Anzahl aller
möglichen Fälle!
> Und noch eine kleine Frage:
>
> Unter dem Summenzeichen steht k=0. Warum steht da nicht k=1
> oder 1 für das erste Element mit dem man beginnt?
Es gibt auch Nullelementige Teilmengen, wenn auch nicht viele!!
> Sonst top Antwort, hat mir sehr geholfen!
Gerne! 
Gruß,
Marcel
|
|
|
| |
|
Hallo Andi,
> > Das ist die Anzahl der Möglichkeiten, 6 aus 49 zu ziehen.
> > Was ist nun hier
> > die Wahrscheinlichkeit, 6 richtige zu haben?
> >
>
> Es ist der Kehrwert des Ergebnisses, also
> [mm]\bruch{1}{13983816}.[/mm] Ist es generell immer der Kehrwert?
Es ist immer die Zahl der günstigen Ereignisse geteilt durch die Zahl der möglichen Ereignisse. Wenn die Zahl der günstigen Ereignisse 1 ist (wie hier), dann ist die Wahrscheinlichkeit eben der Kehrwert der Zahl der möglichen Ereignisse.
> Und noch eine kleine Frage:
>
> Unter dem Summenzeichen steht k=0. Warum steht da nicht k=1
> oder 1 für das erste Element mit dem man beginnt?
Weil eben die leere Menge auch eine Teilmenge ist. Und die hat null Elemente.
> Sonst top Antwort, hat mir sehr geholfen!
Nette Rückmeldung, auch wenn sie gar nicht an mich war. 
Marcel arbeitet immer sehr gründlich und ausführlich. Das sind oft Antworten, die man eigentlich immer wieder zitieren kann.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:44 Mi 29.08.2012 | | Autor: | Marcel |
Hallo,
> Hallo Andi,
>
> > > Das ist die Anzahl der Möglichkeiten, 6 aus 49 zu ziehen.
> > > Was ist nun hier
> > > die Wahrscheinlichkeit, 6 richtige zu haben?
> > >
> >
> > Es ist der Kehrwert des Ergebnisses, also
> > [mm]\bruch{1}{13983816}.[/mm] Ist es generell immer der Kehrwert?
>
> Es ist immer die Zahl der günstigen Ereignisse geteilt
> durch die Zahl der möglichen Ereignisse. Wenn die Zahl der
> günstigen Ereignisse 1 ist (wie hier), dann ist die
> Wahrscheinlichkeit eben der Kehrwert der Zahl der
> möglichen Ereignisse.
>
> > Und noch eine kleine Frage:
> >
> > Unter dem Summenzeichen steht k=0. Warum steht da nicht k=1
> > oder 1 für das erste Element mit dem man beginnt?
>
> Weil eben die leere Menge auch eine Teilmenge ist. Und die
> hat null Elemente.
>
> > Sonst top Antwort, hat mir sehr geholfen!
>
> Nette Rückmeldung, auch wenn sie gar nicht an mich war.
>
sehe ich nicht so eng: Außerdem denke ich, dass diese Rückmeldung
nicht alleine mir galt. ( Andernfalls teile ich sie gerne mit Euch. )
Gruß,
Marcel
|
|
|
|
