Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis Siebformel

Beweis Siebformel

Universität / Fachhochschule

Inklusion-Exklusion

Tags: Inklusion-Exklusion

dummtrottel aktiv_icon

16:19 Uhr, 30.12.2009

Hallo zusammen!

Ich verstehe den Beweis der Siebformel nicht. Hoffentlich vertippe ich mich nicht:

| A_{1} ⋃ A_{2} ⋃ ... ⋃ A_{n + 1} | = | (A_{1} ⋃ A_{2} ⋃ ... A_{n}) ⋃ A_{n + 1} |

= (| ⋃_{k = 1}^{n} A_{k} |) + | A_{n + 1} | - | (⋃_{k = 1}^{n} A_{k}) ⋂ A_{n + 1} |

= \sum_{j = 1}^{n} {(- 1)}^{j + 1} \sum_{1 \leq i_{1} < ... < i_{j} \leq n} | ⋂_{k = 1}^{j} A_{i_{k}} | + | A_{n + 1} | - | ⋃_{k = 1}^{n} (A_{k} ⋂ A_{n + 1} |

= \sum_{j = 1}^{n} {(- 1)}^{j + 1} \sum_{1 \leq i_{1} < ... < i_{j} \leq n} | ⋂_{k = 1}^{j} A_{i_{k}} | + | A_{n + 1} | - \sum_{l = 1}^{n} {(- 1)}^{l + 1} \sum_{1 \leq r_{1} < ... < r_{l} \leq n} | ⋂_{s = 1}^{l} (A_{r_{s}} ⋂ A_{n + 1}) |

= \sum_{j = 1}^{n + 1} {(- 1)}^{n + 1} \sum_{1 \leq i_{1} < ... < i_{j} \leq n + 1} | ⋂_{s = 1}^{j} A_{i_{s}} |

Bis zur vorletzten Zeile kann ich mit Ach und Krach folgen. Den letzten Schritt verstehe ich weder vorwärts noch rückwärts. Auch der Tipp

l = j - 1

hilft mir nicht. Kann mir das jemand von euch verständlich machen?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

hagman aktiv_icon

16:28 Uhr, 30.12.2009

Die erste Summe enthält alle Durchschnitte von 1 bis

n

der Mengen, wobei jedoch nie

A_{n + 1}

auftritt; jeder Summand wird mit (-1)^

{

Anzahl Mengen

+ 1}

gewichtet.
Die zweite Summe enthält alle Durchschnitte von 1 bis

n

der Mengen nochmals geschnitten mit

A_{n + 1},

also alle Durchschnitte von 2 bis

n + 1

Mengen, unter denen gewiss

A_{n + 1}

auftritt; dank dem Minuszeichen wird jeder solche Durchschnitt wieder mit (-1)^

{

Anzahl Mengen

+ 1}

gewichtet.
Zusammen mit dem Spezialfall

| A_{n + 1} |

wird also über alle Durchschnitte überhaupt summiert, egal wie viele und egal ob

A_{n + 1}

dabei ist; das Gewicht ist jeweils einheitlich (-1)^(Anzahl Mengen

+ 1)

dummtrottel aktiv_icon

16:35 Uhr, 30.12.2009

Ich bedanke mich mal auf Verdacht und hoffe, daß es später noch klick macht ;-)

Gibt es irgendwelche Zwischenschritte zwischen den beiden letzten Zeilen, die die Umwandlung verdeutlichen würden, die dort vorgenommen wird?

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

701242

701236

	Status: nicht eingeloggt	Noch nicht registriert?