Aufgabe k-Tupel von Teilmengen

25.10.2007, 19:46

gothino

Auf diesen Beitrag antworten »

Aufgabe k-Tupel von Teilmengen

Hallo zusammen,

ich verstehe folgende Aufgabe nicht:

Sei $\begin{eqnarray*} S \end{eqnarray*}$ eine Menge mit $\begin{eqnarray*} \mid S \mid = n \end{eqnarray*}$ . Wieviele k-Tupel von Teilmengen von $\begin{eqnarray*} S \end{eqnarray*}$ gibt es, sodass
$\begin{eqnarray*} T_{1} \subseteq T_{2} \subseteq ... \subseteq T_{k} \end{eqnarray*}$ ?

Letzte Bedingung kann ich nicht interpretieren da ich nicht weiß wann ein Teiltupel als Teilmenge eines anderen Teiltuppels gilt. Ist (2,1) z.Bsp. ein Teiltuppel von (2,1,3)?
Dann ist mir auch nicht klar was hier als "Teilmengen von S" vorgegeben wird?
Danke im voraus für eure Anregungen
gothino

25.10.2007, 19:51

therisen

Auf diesen Beitrag antworten »

Mit k-Tupel ist $\begin{eqnarray*} (T_1,\dots,T_k) \end{eqnarray*}$ gemeint, wobei $\begin{eqnarray*} T_1\subseteq T_2\subseteq \dots\subseteq T_k \end{eqnarray*}$ gilt.

25.10.2007, 19:54

AD

Auf diesen Beitrag antworten »

Vielleicht mal ein Beispiel:

$\begin{eqnarray*} n=4 \end{eqnarray*}$ mit $\begin{eqnarray*} S=\{1,2,3,4\} \end{eqnarray*}$ sowie k=4. Dann ist etwa

$\begin{eqnarray*} T_1 = \emptyset,\quad T_2=\{2,4\},\quad T_3=\{1,2,4\},\quad T_4=\{1,2,4\} \end{eqnarray*}$

ein solches 4-Tupel $\begin{eqnarray*} (T_1,T_2,T_3,T_4) \end{eqnarray*}$ .

Gesucht ist nun die Anzahl aller solcher Tupel in Abhängigkeit von $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ . Ein ganz nettes kombinatorischen Problem. Augenzwinkern

Augenzwinkern

25.10.2007, 20:17

gothino

Auf diesen Beitrag antworten »

ok, danke inzwischen, dann werd ich mal überlegen verwirrt

verwirrt

smile

25.10.2007, 20:51

AD

Auf diesen Beitrag antworten »

Übrigens wäre die Aufgabe - zumindest die Ergebnisangabe - wesentlich komplizierter, wenn statt $\begin{eqnarray*} T_1 \subseteq T_2 \subseteq \ldots \subseteq T_k \end{eqnarray*}$ etwas stärker $\begin{eqnarray*} T_1 \subsetneq T_2 \subsetneq \ldots \subsetneq T_k \end{eqnarray*}$ , also echte Teilmengen, gefordert würde. Augenzwinkern

Augenzwinkern

02.05.2013, 15:40

Hexenjaeger

Auf diesen Beitrag antworten »

Ich sitze jetzt 6 Jahre nach dem letzten Post an der selben Aufgabe und hab überhaup keine Idee, wie ich da ran gehen soll...

Kann mir jemand eine kleine Starthilfe geben?

Anzeige

02.05.2013, 16:03

HAL 9000

Auf diesen Beitrag antworten »

Betrachte die $\begin{eqnarray*} (k+1) \end{eqnarray*}$ Mengen

$\begin{eqnarray*} T_1, \; T_2\setminus T_1, \; T_3\setminus T_2,\; \ldots, T_k\setminus T_{k-1}, S\setminus T_k \end{eqnarray*}$ .

Irgendeine Idee, was die auszeichnet und was das mit der Aufgabenlösung zu tun haben könnte?

02.05.2013, 17:55

Hexenjaeger

Auf diesen Beitrag antworten »

Danke für die Antwort.

Also vielleicht steh ich wirklich einfach total auf dem Schlauch, aber mir fällt da jetzt nix ein, was diese Mengen auszeichnet. Deren Kardinalität sollte von $\begin{eqnarray*} 1...k \end{eqnarray*}$ monoton steigen. Geht das in die richtige Richtung?

Hilft es mir, dass ich für die erste Menge $\begin{eqnarray*} 2^n \end{eqnarray*}$ Möglichkeiten habe?

Ich checks grad echt nicht...

02.05.2013, 18:14

HAL 9000

Auf diesen Beitrag antworten »

Ok, etwas deutlicher: Bezeichnen wir

$\begin{eqnarray*} A_1 &=& T_1\\ A_j &=& T_j\setminus T_{j-1} \;\mbox{für}\; j=2,\ldots,k\\ A_{k+1} &=& S\setminus T_k \end{eqnarray*}$ ,

so sind diese $\begin{eqnarray*} A_j \end{eqnarray*}$ paarweise disjunkte Mengen, deren Vereinigung gleich $\begin{eqnarray*} S \end{eqnarray*}$ ist. Man kann es auch so ausdrücken: Jedes Element von $\begin{eqnarray*} S \end{eqnarray*}$ gehört zu genau einem $\begin{eqnarray*} A_j \end{eqnarray*}$ .

Darüber hinaus gibt es zwischen $\begin{eqnarray*} (k+1) \end{eqnarray*}$ -Tupeln $\begin{eqnarray*} (A_1,\ldots,A_{k+1}) \end{eqnarray*}$ mit dieser eben genannten Eigenschaft und den $\begin{eqnarray*} k \end{eqnarray*}$ -Tupeln $\begin{eqnarray*} (T_1,\ldots,T_k) \end{eqnarray*}$ der Aufgabenstellung eine eineindeutige Zuordnung, d.h., deren Anzahl ist gleich.

Wie bestimmt man nun die Anzahl der $\begin{eqnarray*} (k+1) \end{eqnarray*}$ -Tupel $\begin{eqnarray*} (A_1,\ldots,A_{k+1}) \end{eqnarray*}$ ? Ich sage nur: Variationen mit Wiederholung - jedes der $\begin{eqnarray*} n \end{eqnarray*}$ Elemente von $\begin{eqnarray*} S \end{eqnarray*}$ kann sich seinen "Besitzer" $\begin{eqnarray*} A_j \end{eqnarray*}$ aussuchen...

Das sollte jetzt aber mehr als genug Information sein.

Zitat:

Original von Hexenjaeger
Hilft es mir, dass ich für die erste Menge $\begin{eqnarray*} 2^n \end{eqnarray*}$ Möglichkeiten habe?

Es bringt dir zumindest die Information, dass im Fall $\begin{eqnarray*} k=1 \end{eqnarray*}$ die gesuchte Anzahl $\begin{eqnarray*} 2^n \end{eqnarray*}$ ist - viel mehr aber nicht. Augenzwinkern

Augenzwinkern

02.05.2013, 18:36

Hexenjaeger

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Hexenjaeger
Hilft es mir, dass ich für die erste Menge $\begin{eqnarray*} 2^n \end{eqnarray*}$ Möglichkeiten habe?

Es bringt dir zumindest die Information, dass im Fall $\begin{eqnarray*} k=1 \end{eqnarray*}$ die gesuchte Anzahl $\begin{eqnarray*} 2^n \end{eqnarray*}$ ist - viel mehr aber nicht. Augenzwinkern

Augenzwinkern

Ok, dann war ich da wohl auf dem falschen Dampfer...

Auf den ersten Blick wirds mir jetzt schon klarer, aber wie genau ich das aufschreiben würde, seh ich noch nicht ganz... ich fahr da jetzt erstma ne Runde mit dem Fahrrad... vll. bekomm ich dabei den Lichtblick.

Vielen Dank nochmal.

02.05.2013, 18:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hexenjaeger
Auf den ersten Blick wirds mir jetzt schon klarer, aber wie genau ich das aufschreiben würde, seh ich noch nicht ganz

Es würde ja schon mal helfen, wenn du jetzt die gesuchte Anzahlformel nennen könntest.

02.05.2013, 22:55

Hexenjaeger

Auf diesen Beitrag antworten »

Ok, anscheinend hats jetzt (meiner Meinung nach) klick gemacht.

Wenn ichs wirklich kapiert hab, dann sollte man die Anzahl einfach durch $\begin{eqnarray*} (k+1)^n \end{eqnarray*}$ berechnen können. Jedes Element "hat die Wahl" in welche der (k+1)-Mengen es gesteckt werden will... soweit richtig?

Und diese Abzählung führt zum richtigen Ergebniss, weil ich mit der Bildungsvorschrift für die $\begin{eqnarray*} A_j \end{eqnarray*}$ eine Bijektion zwischen den beiden "Problemen" gefunden habe. Und genau das war der Punkt der mir nicht sofort schlüssig war. Ich hab das aber zwischenzeitlich mal an nem kleinen Beispiel ausprobiert und dann wurde es mir klar.

Vielen lieben Dank nochmal...

Übrigens Klasse Forum hier... hab mich registriert. Vll. kann ich ja auch mal jemandem helfen.

02.05.2013, 23:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hexenjaeger
Wenn ichs wirklich kapiert hab, dann sollte man die Anzahl einfach durch $\begin{eqnarray*} (k+1)^n \end{eqnarray*}$ berechnen können. Jedes Element "hat die Wahl" in welche der (k+1)-Mengen es gesteckt werden will... soweit richtig?

Freude

Da verbleibt mir nur noch eins: Gute N8. Wink

Wink

19.10.2013, 21:44

coco1234

Auf diesen Beitrag antworten »

RE: Aufgabe k-Tupel von Teilmengen
guten abend, hab gerade dieselbe aufgabe zu lösen, folgende frage:

wenn gesichert wäre, dass für alle Aj ungleich leere Menge gilt, dann hätte man ja eine Partition und es gäbe tatsächlich für jedes n k+1 Möglichkeiten.
da aber Tj-1 auch gleich Tj sein kann wäre es doch möglich, dass Aj gleich leere Menge und somit für alle n nur n-1 Möglichkeiten bestehen?

liebe grüße coco

19.10.2013, 22:52

HAL 9000

Auf diesen Beitrag antworten »

Was auch immer dein Anliegen ist - in der Formulierung verstehe ich es nicht.

Mit "Partition" würde ich hier vorsichtig sein: Bei Partitionen spielen nur die Zerlegungsmengen an sich eine Rolle, aber nicht deren Reihenfolge - gerade die ist hier aber wichtig!

19.10.2013, 23:53

coco1234

Auf diesen Beitrag antworten »

ok ja das verstehe ich ja, dass die anordnung im tupel wichtig ist!

es geht mir nur darum, dass es doch theoretisch möglich ist, dass für ein Aj (j=1,...,k+1) gilt, dass es gleich leere Menge ist, nämlich genau dann wenn Tj=Tj-1.

20.10.2013, 00:57

HAL 9000

Auf diesen Beitrag antworten »

Ja, es ist möglich, dass ein oder mehrere $\begin{eqnarray*} A_j \end{eqnarray*}$ leer sind, und diese Fälle sind doch in der obigen Berechnung mit drin! Ich deute deine Mutmaßungen im vorletzten Beitrag jetzt so, dass du meinst, dass das nicht dabei ist - da täuschst du dich aber gewaltig. unglücklich

unglücklich

Also bitte nochmal gründlich den obigen Weg durchdenken vor weiteren Schnellschüssen in der Richtung.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »