Summe der El. von Teilmengen |
17.01.2007, 18:34 | Kafka | Auf diesen Beitrag antworten » |
Summe der El. von Teilmengen folgende Aufgabe: Sei M eine 6-elementige Menge aus pos.ganzen Zahlen . Betrachten wir alle nichtleere Teilmengen A von M. Für jede von diesen Teilmengen berechnen wir die Summe der Elemente von A. Zu Zeigen ist, dass die Summen nicht alle verschieden sein können. Wie sollte man hier vorgehen? Es gibt also insgesammt 203 solche disjunkte Teilmengen (6-te Bellsche Zahl). Jetzt aus den 15 Zahlen (0 mitgezählt) wählen wir 6 aus, dafür haben wir 5005 Möglichkeiten (). Und jetzt? Ich denke mal es wird bestimmt wieder mal was einfaches mit dem Schubfachprinzip sein, ich komme nur nicht darauf Grüße K. |
||
17.01.2007, 19:06 | AD | Auf diesen Beitrag antworten » |
Bellsche Zahlen kenne ich nicht. Aber bei mir hat eine endliche Menge der Mächtigkeit genau nichtleere Teilmengen. In deinem Fall hier ist , also gibt es genau 63 nichtleere Teilmengen von . Tipp zum Schubfachprinzip: Betrachte mal nicht alle nichtleeren Teilmengen von , sondern nur die mit höchstens 3 Elementen. |
||
17.01.2007, 19:22 | Kafka | Auf diesen Beitrag antworten » |
also die Anzahl der Zerlegungen einer n-elementigen Menge in k disjunkt nichtleere Teilmengen sind ja die Stirling-Zahlen 2.Art S(n,k) und die Summe: sind die Bell-Zahlen (laut Vorlesung ) |
||
17.01.2007, 19:26 | AD | Auf diesen Beitrag antworten » |
Schön. Und was hat das mit der Aufgabe zu tun? Egal, ich hab dir meinen Tipp gegeben, mit dem ist es ein Einzeiler. |
||
18.01.2007, 17:44 | Kafka | Auf diesen Beitrag antworten » |
also haben wir 63 Teilmengen. Die Summe der Elemente ist also da A eine echte Teilmenge von M sein soll. Also müssen wir 54 Summen auf 63 Teilmengen aufteilen? |
||
18.01.2007, 17:53 | AD | Auf diesen Beitrag antworten » |
Ok, du betrachtest also alle 63 Teilmengen. Aber wie kommst du da auf ? Ich komme da nur auf im worst-case. P.S.: Von echten Teilmengen ist oben keine Rede, nur von nichtleeren. |
||
Anzeige | ||
|
||
18.01.2007, 17:57 | Kafka | Auf diesen Beitrag antworten » |
ops, habs vergessen reinzuschreiben, dass |
||
18.01.2007, 18:06 | AD | Auf diesen Beitrag antworten » |
Hmm, und heißt bei dir echte Teilmenge, das sehen manche auch anders und schreiben da explizit . Und bitte beachten, nunmehr sind es nur noch 62 nichtleere echte Teilmengen. Na egal, auch bei echten Teilmengen folgt dann nur . Nun ja, das reicht dann zumindest für's Schubfachprinzip. |
||
18.01.2007, 18:11 | Kafka | Auf diesen Beitrag antworten » |
ok, merk' ich mir Danke. |
||
18.01.2007, 18:22 | AD | Auf diesen Beitrag antworten » |
Es klappt sogar auch mit Zahlen . Allerdings muss man dann das Schubfachprinzip geschickter anwenden, nämlich nur auf alle Teilmengen mit maximal 4 Elementen. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|