Summe der El. von Teilmengen

Neue Frage »

17.01.2007, 18:34	Kafka	Auf diesen Beitrag antworten »
Summe der El. von Teilmengen Hallo, folgende Aufgabe: Sei M eine 6-elementige Menge aus pos.ganzen Zahlen $\begin{eqnarray} \leq 14 \end{eqnarray}$ . Betrachten wir alle nichtleere Teilmengen A von M. Für jede von diesen Teilmengen berechnen wir die Summe $\begin{eqnarray} s_A \end{eqnarray}$ der Elemente von A. Zu Zeigen ist, dass die Summen $\begin{eqnarray} s_A \end{eqnarray}$ 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 ( $\begin{eqnarray} \binom{15}{6} \end{eqnarray}$ ). 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 $\begin{eqnarray} M \end{eqnarray}$ der Mächtigkeit $\begin{eqnarray} \|M\|=n \end{eqnarray}$ genau $\begin{eqnarray} 2^n-1 \end{eqnarray}$ nichtleere Teilmengen. In deinem Fall hier ist $\begin{eqnarray} n=6 \end{eqnarray}$ , also gibt es genau 63 nichtleere Teilmengen $\begin{eqnarray} A \end{eqnarray}$ von $\begin{eqnarray} M \end{eqnarray}$ . Tipp zum Schubfachprinzip: Betrachte mal nicht alle nichtleeren Teilmengen $\begin{eqnarray} A \end{eqnarray}$ von $\begin{eqnarray} M \end{eqnarray}$ , 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: $\begin{eqnarray} b_n = \sum_{k=1}^{n}S(n,k) \end{eqnarray}$ 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 $\begin{eqnarray} 1\leq s_A \leq 54 \end{eqnarray}$ 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 $\begin{eqnarray} 1\leq s_A \leq 54 \end{eqnarray}$ ? Ich komme da nur auf $\begin{eqnarray} 0\leq s_A \leq 14+13+12+11+10+9 = 69 \end{eqnarray}$ 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 $\begin{eqnarray} \emptyset \neq A \subset M \end{eqnarray}$
18.01.2007, 18:06	AD	Auf diesen Beitrag antworten »
Hmm, und $\begin{eqnarray} \subset \end{eqnarray}$ heißt bei dir echte Teilmenge, das sehen manche auch anders und schreiben da explizit $\begin{eqnarray} \varsubsetneq \end{eqnarray}$ . Und bitte beachten, nunmehr sind es nur noch 62 nichtleere echte Teilmengen. Na egal, auch bei echten Teilmengen folgt dann nur $\begin{eqnarray} 0\leq s_A \leq 14+13+12+11+10 = 60 \end{eqnarray}$ . 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 $\begin{eqnarray} \leq 15 \end{eqnarray}$ . Allerdings muss man dann das Schubfachprinzip geschickter anwenden, nämlich nur auf alle Teilmengen mit maximal 4 Elementen.

Neue Frage »

Antworten »

Summe der El. von Teilmengen

Verwandte Themen