Kardinalität einer Menge

Neue Frage »

14.04.2014, 20:09	lagrange92	Auf diesen Beitrag antworten »
Kardinalität einer Menge Meine Frage: Ich will für $\begin{eqnarray} n \geq 1 \end{eqnarray}$ : $\begin{eqnarray} \| \left\{ (A,B) : A \subseteq B \subseteq \left\{1,...,n\right\}\right\}\|= 3^n \end{eqnarray}$ zeigen. Meine Ideen: Ich habe leider keine Idee, weil ich mir (A,B) nicht vorstellen kann, da wäre ich für Hilfe dankbar.
14.04.2014, 20:20	HAL 9000	Auf diesen Beitrag antworten »
Dann schreib's mal auf z.B. für n=2, das sind 9 Paare (A,B) in der Menge: A={} , B={} A={} , B={1} A={} , B={2} A={} , B={1,2} A={1} , B={1} A={1} , B={1,2} A={2} , B={2} A={2} , B={1,2} A={1,2} , B={1,2} Für n=3 wird's schon etwas länger mit dann 27 Paaren (A,B).
15.04.2014, 16:38	lagrange92	Auf diesen Beitrag antworten »
Danke, ich denk drüber nach und melde mich wieder.
16.04.2014, 11:21	lagrange92	Auf diesen Beitrag antworten »
Ich komme zu folgendem Ausdruck: Man hat erst mal $\begin{eqnarray} 2^n = \sum_{k=0}^n {n \choose k} \end{eqnarray}$ Möglichkeiten die leere Meng mit Teilmengen von B zu kombinieren, wobei B gleich $\begin{eqnarray} \left\{ 1 ,...n\right\} =: \left[n \right] \end{eqnarray}$ zu setzen wäre. Weiter gibt es für A=B genau eine Möglichkeit, das Mengenpaar (A,B) zu bilden. Für die anderen Teilemengen von B, welche ja durch A beschrieben werden, gilt erst mal, dass wir hier die 1 bis (n-1)-elementigen Teilmengen von B betrachten. Für diese gilt folgende Summe bezgl. der Möglichkeiten: $\begin{eqnarray} {n \choose 1}( {{n-1}\choose {n-1}}+ {{n-1}\choose {n-2}}+...+ {{n-1}\choose {0}})+{n \choose 2}({{n-2}\choose {n-2}}+{{n-2}\choose {n-3}}+...+ {{n-2}\choose {0}}) +...+ {n \choose {n-1}}({1 \choose 1}+ {1 \choose 0}) \end{eqnarray}$ . Das dachte ich sei so, weil ich immer betrachtet habe, ich wähle z.B. A={1,2}, dann ist A eine von $\begin{eqnarray} {n \choose 2} \end{eqnarray}$ zweielementige Teilmenge von B. Nun habe ich $\begin{eqnarray} B=\left\{1,2,\underbrace{...}_{n-2 \ Stellen}\right\} \end{eqnarray}$ betrachtet und gesagt, die restlichen Stellen (hier n-2) zu besetzen ist durch $\begin{eqnarray} {{n-2} \choose {n-2}} \end{eqnarray}$ beschrieben. Nimmt man von B eine Stelle weg, sodass nur noch n-3 Stellen zu besetzen sind, so folgt $\begin{eqnarray} { {n-2} \choose {n-3}} \end{eqnarray}$ und so weiter, was zu der Summe führt, die oben steht. Kann ich das so machen, oder ist das zu kompliziert?
16.04.2014, 11:43	weisbrot	Auf diesen Beitrag antworten »
sieht mir irgendwie zu kompliziert aus.. betrachte lieber die teilmengen auf folgende weise: für jedes k von 0 bis n gibt es $\begin{eqnarray} {n\choose k} \end{eqnarray}$ teilmengen B mit genau k elementen. und für jedes dieser B gibt es dann, für jedes l von 0 bis k, genau $\begin{eqnarray} {k\choose l} \end{eqnarray}$ teilmengen A (von B), mit genau l elementen. wenn du das jeweils entsprechend summierst bekommst du einen netten ausdruck, der alle gesuchten paare von mengen zählt. lg
16.04.2014, 12:03	lagrange92	Auf diesen Beitrag antworten »
Ick komme auf die Summe: $\begin{eqnarray} \sum_{k=0}^n {n \choose k} (\sum_{l=0}^k {k \choose l}) \end{eqnarray}$ . Kann ich damit weiterarbeiten?
Anzeige

16.04.2014, 15:01	ollie3	Auf diesen Beitrag antworten »
hallo, @lagrange: habe das hier mitverfolgt, die ansätze sind doch viel zu kompliziert. Man kann das ganze einfach und elegant mit vollständiger induktion beweisen, vor allem wenn man sich überlegt, was passiert, wenn man von n auf n+1 übergeht, welche teilmengen dann hinzukommen und warum sich die anzahl dann verdreifacht... gruss ollie3
16.04.2014, 16:45	lagrange92	Auf diesen Beitrag antworten »
Ich bin mittlerweile ziemlich verwirrt. Wenn ich von n nach n+1 gehe, kommen doch die Mengen hinzu, die die gleichen, wie bei n sind, aber zusätzlich noch n+1 enthalten, oder?
16.04.2014, 17:17	ollie3	Auf diesen Beitrag antworten »
hallo, ja, du bist schon auf dem richtigen weg, also erst die mengen, die schon da waren, das sind ja n, und danach könnte man ja bei B jeweils noch das element n+1 hinzufügen, dann hätte man wieder n, und dann... gruss ollie3
16.04.2014, 17:30	HAL 9000	Auf diesen Beitrag antworten »
Nach so vielen Meinungen geb ich auch noch meinen Senf dazu: Sei $\begin{eqnarray} \Omega := \{1,2,\ldots,n\} \end{eqnarray}$ . Jedem Mengenpaar $\begin{eqnarray} (A,B) \end{eqnarray}$ aus der besagten Menge kann eineindeutig eine Funktion $\begin{eqnarray} f:\;\Omega\to \{1,2,3\} \end{eqnarray}$ zugeordnet werden mit $\begin{eqnarray} f(k) = \begin{cases} 1 &\; \mbox{falls}\, k\in A \\ 2 &\; \mbox{falls}\, k\in B\setminus A \\ 3 &\; \mbox{sonst, d.h.}\,k\in \Omega\setminus B \end{cases} \end{eqnarray}$ P.S.: Ist sozusagen das explizite Gegenstück zu der von ollie3 angesprochenen rekursiven Idee.
16.04.2014, 17:44	weisbrot	Auf diesen Beitrag antworten »
trotz den schon gegebenen (schönen) lösung(sansätz)en gehe ich nochmal auf meinen vorschlag ein: @lagrange92: den wert dieser summe kannst du jetzt einfach durch den binomischen lehrsatz (2 mal anwenden) ausrechnen - du schaffst es lg
16.04.2014, 18:18	lagrange92	Auf diesen Beitrag antworten »
Ich hab's. Ich danke euch allen für eure Hilfe. einen schönen abend noch.

Neue Frage »

Antworten »

Kardinalität einer Menge

Verwandte Themen