Anzahl von Teilmengen berechnen

30.06.2008, 00:09

Mr.B.

Anzahl von Teilmengen berechnen

Hi,

während meiner Ferien-Lektüre bin ich über eine Aufgabe gestoßen, die lautet:
"Es seien die Mengen $\begin{eqnarray*} A=\{m, m+1, ..., n\} \end{eqnarray*}$ und $\begin{eqnarray*} B=\{k, k+1, ..., p\} \end{eqnarray*}$ gegeben, wobei $\begin{eqnarray*} m, n, k, p \in\mathbb{N} \end{eqnarray*}$ gilt.
Berechnen Sie die Anzahl der Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B \end{eqnarray*}$ , die die Bedingung $\begin{eqnarray*} C\cap A\neq\varnothing\ \end{eqnarray*}$ erfüllen."

Meine Überlegungen bisher waren, dass die Mengen A und B als geschlossene Intervalle [m; n] und [k; p] auf dem natürlichen Zahlenstrahl gesehen werden können.

Eine Teilmenge C muss also einerseits $\begin{eqnarray*} C=\left\{ x|x\in B\right\} \end{eqnarray*}$ erfüllen und andererseits darf die Schnittmenge von C mit A nicht die leere Menge sein (s. Aufgabenstellung).

Das bedeutet allerdings dass die größte gesuchte Teilmenge genau die Schnittmenge von A und B ist und die Anzahl der möglichen Teilmengen, die laut Aufgabe gesucht sind, sich aus den beliebig langen Kombinationen aus der größt möglichen Teilmenge (bzw. $\begin{eqnarray*} A\cap B \end{eqnarray*}$ ) ergibt.

Damit es überhaupt eine Schnittmenge $\begin{eqnarray*} A\cap B \end{eqnarray*}$ gibt, müssen sich die o.e. Intervalle überlappen. Die Wertigkeit der Schnittmenge ergibt sich dann aus $\begin{eqnarray*} n-k \end{eqnarray*}$ bzw. $\begin{eqnarray*} p-m \end{eqnarray*}$ je nach dem, von welcher Seite sich die Intervalle überlappen.

Angenommen die Wertigkeit ist 1, also die Schnittmenge besteht aus einem Element, so ist die Anzahl der möglichen Teilmengen 1
Angenommen die Wertigkeit ist 2, so ist die Anzahl der möglichen Teilmengen 3: {a}, {a+1}, {a;a+1}
Angenommen die Wertigkeit ist 3, so ist die Anzahl der möglichen Teilmengen 7: {a}, {a+1}, {a+2}, {a; a+1}, {a; a+2}, {a+1; a+2}, {a; a+1; a+2}

Einerseits müsste das Ergebnis ja die Summe aller Binomialkoeffizienten für 1 Element, 2 Elementen, ... aus der Schnittmenge, bis die Wertigkeit derselben erreicht ist (damit die beliebige Länge der möglichen Kombinationen berücksichtigt wird).

Andererseits vermute ich, dass die Anzahl der möglichen Teilmengen genau $\begin{eqnarray*} 2^{n-k}-1 \end{eqnarray*}$ bzw. $\begin{eqnarray*} 2^{p-m}-1 \end{eqnarray*}$ beträgt, weil sich bei den "Rechnungen von Hand" für die Anzahl der möglichen Teilmengen die Zahlenfolge 1, 3, 7, 15, 31, ... ergibt.

Mir fehlt allerdings die Erklärung, WARUM gerade die Zweierpotenz in diesem Zusammenhang. Im Exponent steht die Wertigkeit der Schnittmenge. Führt der Ansatz über die Summe der Binomialkoeffizienten auf das gleiche Ergebnis? Das konnte ich bisher nicht verfolgen.

Habe so das Gefühl, die Lösung der Aufgabe liegt kurz vor meiner Nase, sehe nur den Wald vor lauter Bäumen nicht ^^. Vielleicht wäre jemand von Euch so nett und könnte etwas Licht ins Dunkel bringen? Vielleicht ist in meinem Argumentationsgang auch ein Fehler verwirrt

Besten Gruß,
Mr. B.

30.06.2008, 10:05

Auf diesen Beitrag antworten »

Ich hoffe, du verzeihst mir, wenn ich deinen langen Ausführungen nicht ganz folge, aber die Problemlösung liegt für mich klar auf der Hand:

Die gesuchte Anzahl ist einfach die Anzahl aller Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B \end{eqnarray*}$ (das sind $\begin{eqnarray*} 2^{|B|} \end{eqnarray*}$ ) abzüglich aller Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B\setminus A \end{eqnarray*}$ (das sind $\begin{eqnarray*} 2^{|B\setminus A|} \end{eqnarray*}$ ), denn genau die letzteren Teilmengen verletzen die Bedingung $\begin{eqnarray*} C\cap A\neq \emptyset \end{eqnarray*}$ . Wie man nun die Anzahl

$\begin{eqnarray*} 2^{|B|}-2^{|B\setminus A|} \end{eqnarray*}$

mit $\begin{eqnarray*} m,n,k,p \end{eqnarray*}$ ausdrückt, bleibt dir überlassen und läuft auf diverse Fälle hinaus, wie sich diese Intervalle überlappen.

Zitat:

Original von Mr.B.
Mir fehlt allerdings die Erklärung, WARUM gerade die Zweierpotenz in diesem Zusammenhang. Im Exponent steht die Wertigkeit der Schnittmenge. Führt der Ansatz über die Summe der Binomialkoeffizienten auf das gleiche Ergebnis?

So ist es.

30.06.2008, 12:46

Mr.B.

Auf diesen Beitrag antworten »

Danke für die Antwort,

die "Abkürzung" meiner Argumentation, die du genannt hast, ist für mich sehr nachvollziehbar, im Grunde war mein Weg darauf zu kommen ja nur etwas länger.

Für mich bleibt aber trotzdem eine Frage, und zwar schreibst du

Zitat:

Die gesuchte Anzahl ist einfach die Anzahl aller Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B \end{eqnarray*}$ (das sind $\begin{eqnarray*} 2^{|B|} \end{eqnarray*}$ )

Dabei setzt du voraus, dass die Anzahl aller Teilmengen von $\begin{eqnarray*} B \end{eqnarray*}$ genau $\begin{eqnarray*} 2^{|B|} \end{eqnarray*}$ ist. Ich hatte ja dieselbe Vermutung, nur fehlt mir dafür "der Beweis" bzw. die Erklärung. Ich denke das ist ja eine allgemeine Aussage, es gilt für jede beliebige Menge, ob es nun die von mir angeführte Schnittmenge $\begin{eqnarray*} A \cap B \end{eqnarray*}$ , wo ja auch alle Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B \setminus A \end{eqnarray*}$ herausgefiltert sind.

Die Aufgabe ist trivial, wenn man weiß, dass die Anzahl aller Teilmengen einer beliebigen Menge $\begin{eqnarray*} B \end{eqnarray*}$ genau $\begin{eqnarray*} 2^{\mid B\mid} \end{eqnarray*}$ ist.

Warum ist das so?

30.06.2008, 12:55

Auf diesen Beitrag antworten »

Zitat:

Original von Mr.B.
Die Aufgabe ist trivial, wenn man weiß, dass die Anzahl aller Teilmengen einer beliebigen Menge $\begin{eqnarray*} B \end{eqnarray*}$ genau $\begin{eqnarray*} 2^{\mid B\mid} \end{eqnarray*}$ ist.

Man kann sich das so überlegen: Für jedes Element von $\begin{eqnarray*} B \end{eqnarray*}$ kannst du entscheiden, ob es in der Teilmenge sein soll oder nicht - also 2 Möglichkeiten für jedes Element. Diese Entscheidung kann für alle $\begin{eqnarray*} |B| \end{eqnarray*}$ Elemente getroffen werden, also gibt es $\begin{eqnarray*} 2^{|B|} \end{eqnarray*}$ Möglichkeiten, eine Teilmenge zu bilden.

30.06.2008, 13:34

Mr.B.

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Das Leben kann ja so einfach sein Hammer

Danke dir - Aufgabe abgehakt!

30.06.2008, 18:59

mathe760

Auf diesen Beitrag antworten »

@Mr.B. : Es wäre schön wenn du hier kurz noch deine Lösung vorstellst, damit auch andere etwas davon haben. smile

Bis denn mathe760 Wink

30.06.2008, 22:24

Mr.B.

Auf diesen Beitrag antworten »

RE: Anzahl von Teilmengen berechnen
Ja kann ich machen, zusammenfassend klaube ich mal alles aus den vorigen Beiträgen zusammen:

"Es seien die Mengen $\begin{eqnarray*} A=\{m, m+1, ..., n\} \end{eqnarray*}$ und $\begin{eqnarray*} B=\{k, k+1, ..., p\} \end{eqnarray*}$ gegeben, wobei $\begin{eqnarray*} m, n, k, p \in\mathbb{N} \end{eqnarray*}$ gilt.
Berechnen Sie die Anzahl der Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B \end{eqnarray*}$ , die die Bedingung $\begin{eqnarray*} C\cap A\neq\varnothing\ \end{eqnarray*}$ erfüllen."

Gesucht ist die Anzahl aller Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B \end{eqnarray*}$ . Abzüglich aller Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B\setminus A \end{eqnarray*}$ .

1) Die Anzahl aller Teilmengen ist die Wertigkeit der Potenzmenge: $\begin{eqnarray*} \mid P(B)\mid \end{eqnarray*}$ . Die ist, nach der Erklärung von Arthur Dent und Bestätigung in der Formelsammlung $\begin{eqnarray*} \mid P(B)\mid=2^{\mid B\mid} \end{eqnarray*}$ .
2) Da $\begin{eqnarray*} B \end{eqnarray*}$ eine endliche Menge von aufeinanderfolgenden natürlichen Zahlen sind, stellt sie das Intervall [k; p] dar. Das bedeutet $\begin{eqnarray*} \mid B \mid = p-k \end{eqnarray*}$

3) Aus 1) und 2) folgt: Die Anzahl aller Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} B \end{eqnarray*}$ ist: $\begin{eqnarray*} 2^{p-k} \end{eqnarray*}$ .

4) Aus 1), 2) und 3) folgt o.B.d.A., dass die Anzahl der Teilmengen C von $\begin{eqnarray*} B \setminus A \end{eqnarray*}$ genau
$\begin{eqnarray*} 2^{n-k} \end{eqnarray*}$ bzw. $\begin{eqnarray*} 2^{p-m} \end{eqnarray*}$ beträgt, je nach dem, ob die beiden Mengen sich von links oder rechts auf dem Zahlenstrahl überlappen. (Vorausgesetzt sie überlappen sich. Ist das nicht der Fall, ist das Ergebnis trivial: 0)

5) Aus 3) und 4) folgt, dass die gesuchte Anzahl a folgende Differenz ist:

$\begin{eqnarray*} a=2^{p-k}-2^{n-k}-1 \end{eqnarray*}$ bzw. für den anderen Fall
$\begin{eqnarray*} a=2^{p-k}-2^{p-m}-1 \end{eqnarray*}$

Die 1 wird abgezogen, weil die leere Menge nicht mitzählen darf laut Aufgabenstellung.

Ich hoffe so ist es richtig alles.

Beste Grüße,
Mr.B.

30.06.2008, 22:37

Auf diesen Beitrag antworten »

Zitat:

Original von Mr.B.
Da $\begin{eqnarray*} B \end{eqnarray*}$ eine endliche Menge von aufeinanderfolgenden natürlichen Zahlen sind, stellt sie das Intervall [k; p] dar. Das bedeutet $\begin{eqnarray*} \mid B \mid = p-k \end{eqnarray*}$

Der klassische Abzählfehler: Tatsächlich ist

$\begin{eqnarray*} | \{ k,k+1,\ldots,p \} | = p-k+1 \end{eqnarray*}$ .

Zitat:

Original von Mr.B.
Die 1 wird abgezogen, weil die leere Menge nicht mitzählen darf laut Aufgabenstellung.

Auch falsch: Die leere Menge wird in beiden Zweierpotenzanzahlen erfasst - durch die Subtraktion fällt sie also sowieso weg und darf nicht nochmal abgezogen werden. Bitte gründlicher nachdenken!

----------------------------

Und jetzt mal die richtige Anzahl: Ich gehe mal selbstredend von $\begin{eqnarray*} m\leq n \end{eqnarray*}$ und $\begin{eqnarray*} k\leq p \end{eqnarray*}$ aus. Dann ist $\begin{eqnarray*} |B\setminus A| = |B| - |A\cap B| \end{eqnarray*}$ sowie

$\begin{eqnarray*} A\cap B = \{ \max(m,k),\ldots,\min(n,p) \} \end{eqnarray*}$ , sofern $\begin{eqnarray*} \max(m,k) \leq \min(n,p) \end{eqnarray*}$ - ansonsten ist $\begin{eqnarray*} A\cap B \end{eqnarray*}$ leer.

Also kann man schreiben $\begin{eqnarray*} |A\cap B| = \max(\min(n,p)-\max(m,k)+1,0) \end{eqnarray*}$ und für die gesuchte Anzahl dann

$\begin{eqnarray*} 2^{p-k+1} \left( 1 - 2^{-\max(\min(n,p)-\max(m,k)+1,0)} \right) \end{eqnarray*}$

30.06.2008, 23:44

Mr.B.

Auf diesen Beitrag antworten »

Ok, deine Anmerkungen sind akzeptiert und deine Lösung ist formal mit diesen min's und max's natürlich schöner.

Aber ausgenommen der zwei Fehler, die du angemerkt hast, müsste meine Lösung doch vom Kern richtig sein, wenn man noch den dritten Fehler berücksichtigen würde, dass ich bei der zweiten Potenz ( $\begin{eqnarray*} 2^{n-k+1} \end{eqnarray*}$ bzw. $\begin{eqnarray*} 2^{p-m+1} \end{eqnarray*}$ ) die Wertigkeit von $\begin{eqnarray*} A \cap B \end{eqnarray*}$ und nicht von $\begin{eqnarray*} A \setminus B \end{eqnarray*}$ berechnet habe.

Ich muss zugeben ich bin jetzt etwas verwirrt ^^.

Mr.B.

01.07.2008, 08:31

Auf diesen Beitrag antworten »

Es ist nicht allein das "schöner aufschreiben" mit den min und max:

Du hast auch schlicht und einfach einige Fälle nicht berücksichtigt, z.B. $\begin{eqnarray*} k<m<n<p \end{eqnarray*}$ . Dieser Fall wird von

Zitat:

Original von Mr.B.
$\begin{eqnarray*} a=2^{p-k}-2^{n-k}-1 \end{eqnarray*}$ bzw. für den anderen Fall
$\begin{eqnarray*} a=2^{p-k}-2^{p-m}-1 \end{eqnarray*}$

nicht berücksichtigt, selbst wenn man die oben bereits angesprochenen Fehler korrigiert. Insofern kann ich deine Einschätzung des "vom Kern her richtig" in keinster Weise teilen. So viele Fehler beim Übergang von $\begin{eqnarray*} 2^{|B|}-2^{|B\setminus A|} \end{eqnarray*}$ zur endgültigen Formel mit $\begin{eqnarray*} m,n,k,p \end{eqnarray*}$ sind nicht so einfach wegzudrücken.

Neue Frage »

Antworten »

Anzahl von Teilmengen berechnen

Verwandte Themen