Teilmengen einer Menge > 2 Elementen

19.03.2010, 16:16

caringandkilling

Teilmengen einer Menge > 2 Elementen

Folgende Aufgabenstellung bearbeite ich gerade:

Sei N = {1, .., 10}

Wieviele Teilmengen mit mehr als zwei Elementen besitzt N?

Mein Vorschlag:

P(N) - |N x N| - |N|

Ich subtrahiere also vom Betrag der Potenzmenge von N die Beträge aller 1- (|N| selbst) und 2 - elementigen (|N x N|) Teilmengen von N.

Hört sich für mich ganz schlüssig an, jedoch zweifle ich etwas an meinen mathematischen Fähigkeiten .... deshalb die immer wiederkehrende Frage nach Korrektheit ...

19.03.2010, 16:25

papahuhn

Auf diesen Beitrag antworten »

RE: Teilmengen einer Menge > 2 Elementen
Zweielementige Mengen sind keine Zweitupel. Was ist z.b. mit x vs. (x, x). Was ist mit (x, y) vs. (y, x).

19.03.2010, 16:34

tmo

Auf diesen Beitrag antworten »

Ich gebe dir mal eine Gleichung, die dich zum Nachdenken anregen sollte.

M habe n Elemente.

$\begin{eqnarray*} |P(M)|=\sum_{k=0}^n \binom{n}{k} \end{eqnarray*}$

19.03.2010, 16:48

caringandkilling

Auf diesen Beitrag antworten »

Re:
Ich tappe gerade ziemlich im Dunklen ...
mein Gedanke war von der Mächtigkeit der Potenzmenge von N die Mächtigkeit aller 2- und 1- Elementigen Teilmengen abzuziehen. Ist dieser Ansatz grundsätzlich richtig?

19.03.2010, 16:49

tmo

Auf diesen Beitrag antworten »

Natürlich ist dieser Ansatz richtig. Darauf wollte ich mit meiner Gleichung hinaus.

19.03.2010, 16:59

caringandkilling

Auf diesen Beitrag antworten »

Re:
Die Potenzmenge der Menge N lässt sich, abgesehen von der durch dich angegeben Summenformel doch auch so berechnen:

$\begin{eqnarray*} |P(N)| = 2^{|N|} = 1024 \end{eqnarray*}$ .

Entschuldigt meinen Dilletantismus, aber mir kam gerade der Gedanke N x N in meiner Rechnung nochmal durch zwei zu teilen, um Duplikate wie z.B. {1,1} {2,2} aus dem kartesischen Produkt von N herauszufiltern:

$\begin{eqnarray*} |P(N)| - \frac{|N x N|}{2} - |N| \end{eqnarray*}$

... ist das besser?

19.03.2010, 17:24

tmo

Auf diesen Beitrag antworten »

Was du mit dem Teilen durch 2 erreicht ist, dass du die Reihenfolge nicht mehr beachtest. Denn es ist bekanntlich $\begin{eqnarray*} \{1,2\}=\{2,1\} \end{eqnarray*}$ , aber $\begin{eqnarray*} (1,2) \neq (2,1) \end{eqnarray*}$ .

Wenn du $\begin{eqnarray*} (1,1), (2,2) \end{eqnarray*}$ etc. rausfiltern willst, musst du $\begin{eqnarray*} |N| \end{eqnarray*}$ abziehen.

Man kommt also für die 2-elementigen Teilmengen auf die Anzahl $\begin{eqnarray*} \frac{|N \times N|-|N|}{2} \end{eqnarray*}$ . Und wenn man mal genau hinschaut ist das nichts anderes als $\begin{eqnarray*} \binom{|N|}{2} \end{eqnarray*}$ ...

19.03.2010, 18:00

caringandkilling

Auf diesen Beitrag antworten »

Re:
Okay, dann versuche ich es mal zuende zu bringen:

Sei x die Menge der Teilmengen von N mit mehr als zwei Elementen, dann ist also

$\begin{eqnarray*} x = |P(N)| - \frac{|N|\times|N| - |N|}{2} - |N| \end{eqnarray*}$ .

Folglich ist

$\begin{eqnarray*} x = 1024 - \frac{10 * 10 - 10}{2} - 10 = 969 \end{eqnarray*}$

... eine schwere Geburt.

Ich danke allen Beteiligten!

19.03.2010, 19:30

tmo

Auf diesen Beitrag antworten »

Hast du denn mittlerweile auch begriffen, wie man auf diese Gleichung kommt und wie das die Aufgabe sofort erschlagen hätte?

Zitat:

Original von tmo
M habe n Elemente.

$\begin{eqnarray*} |P(M)|=\sum_{k=0}^n \binom{n}{k} \end{eqnarray*}$

19.03.2010, 19:43

caringandkilling

Auf diesen Beitrag antworten »

Re:
Wenn ich ganz ehrlich bin nicht.

Aber ich werde mir es im Laufe des Abends nochmal genauer anschauen. Bin gerade mit einigen mathematischen Disziplinen beschäftigt ...
Ist bestimmt nicht mein letzter Post hier.

Ich schreibe am Montag eine Klausur in Diskreter Mathematik.

Trotzdem danke nochmal.

19.03.2010, 20:27

caringandkilling

Auf diesen Beitrag antworten »

Re:
Eine Frage noch, bezogen auf dieselbe Ausgangsmenge.
Angenommen ich würde nun die Mächtigkeit aller mehr als 3-Elementigen Teilmengen von N berechnen wollen, sollte das, analog zur vorhergehenden Lösung so funktionieren:

$\begin{eqnarray*} P(X) - \frac{|N\times N\times N| - |N|}{2} - \frac{|N\times N|-|N|}{2} - |N| \end{eqnarray*}$

Topp oder Flopp?

19.03.2010, 20:29

kiste

Auf diesen Beitrag antworten »

Warum erfindest du hier irgendwelche Formeln und nimmst nicht endlich den Tipp mit dem Binomialkoeffizienten an?

19.03.2010, 20:38

caringandkilling

Auf diesen Beitrag antworten »

Re:
Nichts liegt mir ferner als irgendwelche Formeln zu erfinden.

Ich habe in meinem vorherigen Post bereits erwähnt dass ich seinen Hinweis mit den Binomialkoeffizienten nicht durchblickt habe.

Ich habe nur versucht die vorherige Formel zu erweitern...

Wenn du mir den Hinweis mit den Binomialkoeffizienten erläutern möchtest, nur zu.

Ungeduld seitens des Mentors führt im Übrigen eher zu Verunsicherung meinerseits,
ich will hier niemanden mit meinen Fragen nerven.

Besten Gruß.

19.03.2010, 20:40

kiste

Auf diesen Beitrag antworten »

$\begin{eqnarray*} {n\choose k} \end{eqnarray*}$ ist die Anzahl der k-elementigen Teilmengen!
In dem Fall also musst du das für k=0,1,2,3 abziehen!

Neue Frage »

Antworten »

Teilmengen einer Menge > 2 Elementen

Verwandte Themen