Inklusions-Exklusion-Prinzip

Aufrufe: 95     Aktiv: 17.05.2022 um 19:50

1
Guten Tag,

der Umgang mit dem Summenzeichen ist mir eigentlich bekannt, allerdings stoße ich auf folgende Verständnisprobleme mit der Schreibweise für das Inklusions-Exklusion-Prinzip.

\( \left\lvert \bigcup_{ k:=1 }^{ n }{ A_{ k } } \right\rvert = \sum_{ k:=1 }^{ n }{ ((-1)^{ k+1 } * \sum_{ 1\leq i_{ 1 } <...<i_{ k }\leq n}{  }{ \:\left\lvert \bigcap_{1\leq j\leq k}{  }{ A_{ i_{ j } } } \right\rvert }) } \)
____________________________________________________________________________________________
1. Ich kenne nur die Schreibweise für die Laufvariable k = 1, hier wird k := 1 geschrieben. Gibt es da Unterschiede?
\( \left\lvert \bigcup_{ k:=1 }^{ n }{ A_{ k } } \right\rvert\)
____________________________________________________________________________________________
2. Hier weis ich nicht wie ich die "innere" Summe lesen soll. Z.B. im ersten Durchlauf bei n = 3, wäre k = 1. Somit ergibt sich aus :
\( \sum_{ 1\leq i_{ 1 } <...< i_{ k }\leq n}{  }\)

folgender Ausdruck:
\( \sum_{ 1\leq i_{ 1 } <...< i_{ 1 }\leq 3}{  }\)

Allerdings verstehe ich nicht so ganz wie ich jetzt die Summe darauf basierend bilden soll oder anders gesagt, wie sieht jetzt die Laufvariable aus?
____________________________________________________________________________________________
3. Hier hab ich zuerst das gleiche Problem, wie bei 2. (Laufvariable) und zudem noch, dass mir die Indizierung der Menge A nicht bekannt ist. Bei dem Beispiel von 2. wo n = 3 entsteht anschließend aus:
\( \bigcap_{1\leq j\leq k}{  }{ A_{ i_{ j }}} \)

folgender Ausdruck:
\( \bigcap_{1\leq j\leq 1}{  }{ A_{ i_{ j }}} \)

Hier bin ich ratlos. Woher beziehe ich die Laufvariable i und der Laufvariable j?
____________________________________________________________________________________________
Bei dem Problem 2. und 3. sind beim Summen- und Schnittzeichen keine Endwerte angeben, wie kann man damit umgehen?


Ich bedanke mit schonmal für euere Antworten.
Diese Frage melden
gefragt

Student, Punkte: 19

 
Kommentar schreiben
1 Antwort
1
Die Schreibweise mit dem Doppelpunkt ist wohl eher unüblich. Habe ich so jedenfalls noch nicht gesehen. 

Das, was da sonst unter der Summe steht, bedeutet, dass du über alle Indizes summierst, die die angegebene Bedingung erfüllen. Daher ist kein Endwert notwendig. Wenn also $1 \leq i<j \leq 5 $ unter der Summe steht, summierst du über die Indizes $(i, j)$ mit $(1,2), (1,3), (1,4), (1,5), (2,3),(2,4)$ usw. bis $(4,5)$.

Die $i_j$ sind jeweils neue Laufvariablen, wovon es dann immer $k$ Stück gibt. Versuch am besten mal, das für kleines $n$ Schritt für Schritt aufzuschreiben.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 23.05K

 

Irgendwie komme ich nicht weiter. Ich versuche mal meinen Gedankengang aufzuschreiben, da ich anscheinend falsch darüber nachdenke :).

geg,; n = 3

Bei k = 1, ergibt sich für mich:
\( \sum_{ 1\leq i_{ 1} < i_{ 3 } \leq 3 }{ }{ } \left\lvert \bigcap_{ 1 \leq j \leq 1}{ }{ A_{ i_{ j } }}\right\rvert \)

Die Laufvariablen Tupel wäre dann \( (i_{1} | i_{2}),(i_{1} | i_{3}),(i_{2} | i_{3})\), ich verstehe nicht ganz wie ich jetzt weitermachen. Es fehlt ja \( j \).

Ich glaube, dass ich mich irgendwie verrannt habe.
  ─   hn12344 17.05.2022 um 12:41

Wenn $n=3$ ist, gibt es ja die Mengen $A_1$, $A_2$ und $A_3$. Damit fängt man dann an. Die Vereinigung aller dieser Mengen sieht dann wie aus? Schreibe alles Schritt für Schritt auf.

Warum fehlt dir denn $j$? Das ist doch wiederum eine Laufvariable im Schnitt der $A_{i_j}$.
  ─   cauchy 17.05.2022 um 13:28

Ich meine es verstanden zu haben.
Aus 3 gegebenen Mengen \(A_{i_{1}},A_{i_{2}},A_{i_{3}} => n = 3\) ergibt sich:

Fall k =1 :
\(|A_{i_{1}}| + |A_{i_{2}}|+|A_{i_{3}}|\) Aus der \( \sum_{ 1\leq i_{ 1 } \leq 3 }{ }{ } \) ergeben sich die Tupel \( (i_{1}),(i_{2}),(i_{3}) = (A_{i_{1}}),(A_{i_{2}}),(A_{i_{3}})\). Das \( j \) in der Nachfolgenden Schnittmenge gibt dann die jeweilige Position aus dem Tupel an.

Fall k =2 :
\(|A_{i_{1}} \cap A_{i_{2}} | + |A_{i_{1}} \cap A_{i_{3}}|+|A_{i_{2}} \cap A_{i_{3}}|\) Aus der \( \sum_{ 1\leq i_{ 1 } \leq i_{2} \leq 3 }{ }{ } \) ergeben sich die Tupel \((i_{1},i_{2}),(i_{1},i_{3}),(i_{2},i_{3}) = (A_{i_{1}}, A_{i_{2}}),(A_{i_{1}}, A_{i_{3}}),(A_{i_{2}}, A_{i_{3}}) \).

Fall k =3 :
\(|A_{i_{1}} \cap A_{i_{2}} \cap A_{i_{3}} |\) Aus der \( \sum_{ 1\leq i_{ 1 } \leq i_{2} \leq i_{3} \leq 3 }{ }{ } \) ergibt sich das Tupel \( (i_{1},i_{2},i_{3}) = (A_{i_{1}}, A_{i_{2}}, A_{i_{3}})\).

Mit Berücksichtigung der ersten Summe \( \sum_{k=1}^{n}(-1)^{ k+1 }\) ergibt sich dann:

\(|A_{i_{1}}| + |A_{i_{2}}|+|A_{i_{3}}| - ( |A_{i_{1}} \cap A_{i_{2}} | + |A_{i_{1}} \cap A_{i_{3}}| + |A_{i_{2}} \cap A_{i_{3}}|)
+ |A_{i_{1}} \cap A_{i_{2}} \cap A_{i_{3}} |\)

Das sollte korrekt sein ?
  ─   hn12344 17.05.2022 um 16:45

Deine Mengen sind $A_1$, $A_2$ und $A_3$, nicht $A_{i_1}$ etc. Aber vom Prinzip her passt das.   ─   cauchy 17.05.2022 um 19:50

Kommentar schreiben