Elementares Abzählen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei S eine Menge mit |S|=n. Wieviele k-Tupel [mm] (T_{1},T_{2},...,T_{k}) [/mm] von Teilmengen von S gibt es, sodass [mm] T_{1} \subseteq T_{2} \subseteq...\subseteq T_{k} [/mm] ? |
Ich weiß das es genau [mm] n^{k} [/mm] verschiedene k-Tupel aus einer n-elementigen Menge gibt. Aber wie kann ich diese Anzahl reduzieren, damit sie die Bedingung erfüllt?
|
|
| |
|
moin, (ja, es ist schon Sonntag Morgen *g*)
Zu aller erst muss ich dich leider enttäuschen, [mm] $n^k$ [/mm] stimmt nicht ganz...
Bei einem "normalen" Tupel stimmt das, also bei einem Tupel in dem an jeder Stelle nur ein Element steht.
Dies ist hier aber nicht der Fall, gefragt ist nämlich nach Tupeln aus Teilmengen.
Als Beispiel: nehmen wir die Menge M = {1,2,3,4} und suchen uns 3-Tupel daraus.
Die "normalen" Tupel, von denen es [mm] $n^k$ [/mm] gibt, wären zB (1,3,4) oder (1,2,4).
Die Teilmengentupel, nach denen hier gefragt ist, können allerdings auch so aussehen:
(1,{2,3},{1,2,4}).
Nehmen wir die Bedingung, dass jedes Element des Tupels Teilmenge des nachfolgenden Elements sein muss so wäre ein der Aufgabenstellung entsprechendes 3-Tupel aus M zum Beispiel:
(1,1,{1,2})
Das macht die ganze Sache natürlich etwas komplizierter als ein einfaches [mm] $n^k$.
[/mm]
Ich würde bei dieser Aufgabe von der Mächtigkeit des letzten Elements im Tupel ausgehen.
Hat es die Mächtigkeit 1 haben wir den einfachsten Fall, dann müssen nämlich alle Zahlen im Tupel (um die Bedingung zu erfüllen) gleich sein (n Möglichkeiten).
Hat das letzte Element die Mächtigkeit 2 so können wiederrum alle Elemente gleich sein (n*(n-1) Möglichkeiten) oder aber an irgend einer Stelle auf dem Weg von hinten nach vorne reduziert sich das ganze auf ein Element (stellt sich natürlich die Frage an welcher Stelle und welches der beiden Elemente wegfällt).
Das ganze für 3,4,5,...k von Hand auszurechnen ist natürlich mühseelig bis unmöglich.
Also würde ich dir empfehlen für das Verfahren, das ich hier angedeutet habe (oder wenn du willst auch ein anderes, soll mich nicht stören *g*) eine Formel oder Funktion aufzustellen.
Sollte diese Aufgabe nur 1-2 Punkte wert sein und für 5 Minuten geplant frage lieber nochmal nach, ob die Aufgabenstellung wirklich so gemeint war.
Denn wenn die Aufgabe so gemeint ist wie ich sie verstanden habe wirst du wohl noch etwas länger daran sitzen...
Ich hoffe ich konnte dir helfen, wenn noch was absolut unklar ist immer her damit. ;)
MfG
Schadowmaster
|
|
|
| |
|
Also ich denke, dass dieses Beispiel in max. 15 min zu lösen sein müsste. Aber ich habe eine andere Frage zu dem Beispiel. Es muss doch auch die Bedingung erfüllt sein, dass n>k, weil dann könnte man die Anzahl der k-Tupel doch folgendermaßen hinschreiben:
[mm] \produkt_{i=1}^{k}(n-i+1)
[/mm]
|
|
|
| |
|
n>k gilt an sich nur wenn das echte Teilmengen sein sollen (was die ganze Aufgabe dann auch wieder ne Nummer leichter macht^^).
Wenn die Teilmengen auch gleich sein dürfen (also T1 = T2) könnte das Tupel an sich auch unendlich lang sein...
Also: Ist mit T1 [mm] $\subseteq$ [/mm] T2 vielleicht eine echte Teilmenge gemeint, also ins besondere |T2| > |T1| ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Di 02.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
