Inklusions-Exklusionsprinzip < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:55 Mo 04.02.2019 | | Autor: | magics |
| Aufgabe | Die Allgemeine Inklusions-Exklusions-Formel lautet:
Gegeben sind die endlichen Teilmengen [mm] $A_1, [/mm] ..., [mm] A_l$ [/mm] der Menge M
[mm] $|\bigcup_{i=1}^{l}A_i| [/mm] = [mm] \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} A_i|$
[/mm]
Die Summation erstreckt sich dabei über alle nichtleeren Teilmengen I der Indexmenge (1,2,...,l). |
Hallo,
ich habe eine Frage zum Beweis mittels Induktion. Hier kurz ein Abriss der bisherigen Vorgehensweise (Induktionsanfang und Induktionsvoraussetzung spare ich mir mal). Der Induktionsschritt ist $l [mm] \mapsto [/mm] l+1$. Wir definieren [mm] $A:=\bigcup_{i=1}^{l}A_i$ [/mm] und [mm] $B:=A_{l+1}$. [/mm] Wir führen auf den Fall $l=2$ zurück und erhalten
[mm] $|\bigcup_{i=1}^{l+1}A_i| [/mm] = |A [mm] \cup [/mm] B| = |A|+|B|-|A [mm] \cap [/mm] B|$
Nach Induktionsvoraussetzung ist $|A| = [mm] \bigcup_{i=1}^{l}A_i [/mm] = [mm] \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} A_i|$
[/mm]
Mit Hilfe des Distributivgesetzes können wir auch [mm] $|A\cap [/mm] B|$ umformen, sodass
[mm] $|A\cap [/mm] B| = [mm] \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} (A_i \cap [/mm] B)|$
Durch Einsetzen erhalten wir schließlich
[mm]|A \cup B| = \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}\ *|\bigcap_{i \in I}^{} A_i| \red{ + |B|} - \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} \red{(A_i\cap B)} |[/mm]
Daraus wird im nächsten Schritt (unter Verwendung von [mm] $B:=A_{l+1}$):
[/mm]
[mm]
|A \cup B| = \summe_{ \red{J:J\subseteq {1,...,l+1}, J \not= \emptyset, l+1 \not\in J} }^{} (-1)^{1+|J|}
*|\bigcap_{i \in J}^{} A_i| - \summe_{ \red{ J:J\subseteq {1,...,l+1} , J \not= \emptyset}}^{} (-1)^{1+|J|} *|\bigcap_{i \in J}^{} (A_i)|
[/mm]
Ich verstehe die Umformung im letzten Schritt nicht. Dass [mm] $\red{(A_i\cap B)}$ [/mm] entsprechend in die rechte Summe umgeformt werden kann, verstehe ich noch.
Doch wie [mm] $\red{ + |B|}$ [/mm] in die linke Summe wandern soll/darf, ist mir ein Rätsel. Es wäre irgendwie klarer, wenn das [mm] $(-1)^{1+|J|}$ [/mm] nicht da wäre. Doch mit dem alternierenden Vorzeichen erscheint mir das Zusammenfassen des Ausdrucks als nicht sicher.
Grüße
Thomas
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:57 Mi 06.02.2019 | | Autor: | Marc |
Hallo Thomas!
> Die Allgemeine Inklusions-Exklusions-Formel lautet:
>
> Gegeben sind die endlichen Teilmengen [mm]A_1, ..., A_l[/mm] der
> Menge M
>
> [mm]|\bigcup_{i=1}^{l}A_i| = \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} A_i|[/mm]
>
> Die Summation erstreckt sich dabei über alle nichtleeren
> Teilmengen I der Indexmenge (1,2,...,l).
>
>
> Hallo,
>
> ich habe eine Frage zum Beweis mittels Induktion. Hier kurz
> ein Abriss der bisherigen Vorgehensweise (Induktionsanfang
> und Induktionsvoraussetzung spare ich mir mal). Der
> Induktionsschritt ist [mm]l \mapsto l+1[/mm]. Wir definieren
> [mm]A:=\bigcup_{i=1}^{l}A_i[/mm] und [mm]B:=A_{l+1}[/mm]. Wir führen auf den
> Fall [mm]l=2[/mm] zurück und erhalten
>
> [mm]|\bigcup_{i=1}^{l+1}A_i| = |A \cup B| = |A|+|B|-|A \cap B|[/mm]
>
> Nach Induktionsvoraussetzung ist [mm]|A| = \bigcup_{i=1}^{l}A_i = \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} A_i|[/mm]
>
> Mit Hilfe des Distributivgesetzes können wir auch [mm]|A\cap B|[/mm]
> umformen, sodass
>
> [mm]|A\cap B| = \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} (A_i \cap B)|[/mm]
>
> Durch Einsetzen erhalten wir schließlich
>
> [mm]|A \cup B| = \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}\ *|\bigcap_{i \in I}^{} A_i| \red{ + |B|} - \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} \red{(A_i\cap B)} |[/mm]
=> Formel (1)
> Daraus wird im nächsten Schritt (unter Verwendung von
> [mm]B:=A_{l+1}[/mm]):
>
> [mm]
|A \cup B| = \summe_{ \red{J:J\subseteq {1,...,l+1}, J \not= \emptyset, l+1 \not\in J} }^{} (-1)^{1+|J|}
*|\bigcap_{i \in J}^{} A_i| - \summe_{ \red{ J:J\subseteq {1,...,l+1} , J \not= \emptyset}}^{} (-1)^{1+|J|} *|\bigcap_{i \in J}^{} (A_i)|
[/mm]
=> Formel (2)
Steht bei (2) wirklich ein - zwischen den Summen und nicht ein +?
Und in der zweiten Summation nicht noch die Forderung [mm] $\ell+1\in [/mm] J$?
Die jeweils ersten Summationen aus (1) und (2) sind doch gleich, denn
[mm] $I\subseteq\{1,\ldots,\ell\},I\not=\emptyset$ $\gdw$ $I\subseteq\{1,\ldots,\ell,\ell+1\},I\not=\emptyset,\ell+1\not\in [/mm] I$
Und für die zweite Summation aus (2) (mit meiner Korrektur [mm] $\summe_{ J:J\subseteq \{1,\ldots,\ell+1\} , J \not= \emptyset,\ell+1\in J}(-1)^{1+|J|} *|\bigcap_{i \in J} (A_i)|$) [/mm] gilt:
Es wird hier nur über Teilmengen summiert, die [mm] $\ell+1$ [/mm] enthalten, die also von der Form [mm] $J=I\cup\{\ell+1\}$ [/mm] mit [mm] $\ell+1\not\in [/mm] I$ sind (und damit auch $|J|=|I|+1$).
Für [mm] $J=\{\ell+1\}$ [/mm] ist dann aber in der Zerlegung [mm] $I=\emptyset$. [/mm] Das ergibt in der Summation dann das $+|B|$.
Viele Grüße
Marc
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:57 Do 07.02.2019 | | Autor: | magics |
Hallo Marc
> > [mm]|A \cup B| = \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}\ *|\bigcap_{i \in I}^{} A_i| \red{ + |B|} - \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}*|\bigcap_{i \in I}^{} \red{(A_i\cap B)} |[/mm]
>
> => Formel (1)
>
> > Daraus wird im nächsten Schritt (unter Verwendung von
> > [mm]B:=A_{l+1}[/mm]):
> >
> > [mm]
|A \cup B| = \summe_{ \red{J:J\subseteq {1,...,l+1}, J \not= \emptyset, l+1 \not\in J} }^{} (-1)^{1+|J|}
*|\bigcap_{i \in J}^{} A_i| + \summe_{ \red{ J:J\subseteq {1,...,l+1} , J \not= \emptyset, \ell+1\in J}}^{} (-1)^{1+|J|} *|\bigcap_{i \in J}^{} (A_i)|
[/mm]
>
> => Formel (2)
>
> Steht bei (2) wirklich ein - zwischen den Summen und nicht
> ein +?
> Und in der zweiten Summation nicht noch die Forderung
> [mm]\ell+1\in J[/mm]?
Ja, du hast recht!
> Die jeweils ersten Summationen aus (1) und (2) sind doch
> gleich, denn
> [mm]I\subseteq\{1,\ldots,\ell\},I\not=\emptyset[/mm] [mm]\gdw[/mm]
> [mm]I\subseteq\{1,\ldots,\ell,\ell+1\},I\not=\emptyset,\ell+1\not\in I[/mm]
>
> Und für die zweite Summation aus (2) (mit meiner Korrektur
> [mm]\summe_{ J:J\subseteq \{1,\ldots,\ell+1\} , J \not= \emptyset,\ell+1\in J}(-1)^{1+|J|} *|\bigcap_{i \in J} (A_i)|[/mm])
> gilt:
>
> Es wird hier nur über Teilmengen summiert, die [mm]\ell+1[/mm]
> enthalten, die also von der Form [mm]J=I\cup\{\ell+1\}[/mm] mit
> [mm]\ell+1\not\in I[/mm] sind (und damit auch [mm]|J|=|I|+1[/mm]).
> Für [mm]J=\{\ell+1\}[/mm] ist dann aber in der Zerlegung
> [mm]I=\emptyset[/mm]. Das ergibt in der Summation dann das [mm]+|B|[/mm].
Ok, das habe ich verstanden.
Wieso darf man das Vorzeichen vor der rechten Summation von Minus nach Plus ändern?
Grüße
Thomas
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:18 Do 07.02.2019 | | Autor: | Marc |
Hallo Thomas!
> > Steht bei (2) wirklich ein - zwischen den Summen und nicht
> > ein +?
> > Und in der zweiten Summation nicht noch die Forderung
> > [mm]\ell+1\in J[/mm]?
>
> Ja, du hast recht!
![[ok]](/images/smileys/ok.gif "[ok]")
> [...]
> Wieso darf man das Vorzeichen vor der rechten Summation von
> Minus nach Plus ändern?
Es war ja [mm] $J=I\stackrel{\cdot}{\cup}\{\ell+1\}$, [/mm] d.h. $|J|=|I|+1$
Und damit ist auch [mm] $-(-1)^{1+|I|}=(-1)^1\cdot (-1)^{1+|I|}=+(-1)^{1+|I|+1}=+(-1)^{1+|J|}$.
[/mm]
Viele Grüße
Marc
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:51 Do 07.02.2019 | | Autor: | magics |
Hallo Marco,
es tut mir leid, aber ich muss nochmal nachhaken. Ich habe große Schwierigkeiten, das nachzuvollziehen.
> > Wieso darf man das Vorzeichen vor der rechten Summation von
> > Minus nach Plus ändern?
>
> Es war ja [mm]J=I\stackrel{\cdot}{\cup}\{\ell+1\}[/mm], d.h.
> [mm]|J|=|I|+1[/mm]
>
> Und damit ist auch [mm]-(-1)^{1+|I|}=(-1)^1\cdot (-1)^{1+|I|}=+(-1)^{1+|I|+1}=+(-1)^{1+|J|}[/mm].
Betrachten wir nur folgenden Teil:
$ +|B| - [mm] \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}\cdot{}|\bigcap_{i \in I}^{} (A_i\cap [/mm] B) | $
Sobald ich hier unter dem Sigma das $I$ durch $J$ austausche und $J = I [mm] \cup \{A_{\ell + 1}\}$ [/mm] definiere, muss ich doch sogleich auch den Exponenten über der $(-1)$ austauschen, sodass dort eigentlich sofort [mm] $(-1)^{1+|J|}$ [/mm] steht.
So wie du den Weg beschrieben hast, sieht es so aus, als würde man $I$ unter dem Sigma durch $J$ ersetzen, hätte aber anschließend immer noch $I$ im Rest der Formel stehen und würde dann einen Weg suchen, es umzuformen zu $J$.
Aber das kann doch bei einer Substitution nicht sein!
Grüße
Thomas
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:00 Do 07.02.2019 | | Autor: | Marc |
Hallo Thomas!
> es tut mir leid, aber ich muss nochmal nachhaken. Ich habe
> große Schwierigkeiten, das nachzuvollziehen.
>
> > > Wieso darf man das Vorzeichen vor der rechten Summation von
> > > Minus nach Plus ändern?
> >
> > Es war ja [mm]J=I\stackrel{\cdot}{\cup}\{\ell+1\}[/mm], d.h.
> > [mm]|J|=|I|+1[/mm]
> >
> > Und damit ist auch [mm]-(-1)^{1+|I|}=(-1)^1\cdot (-1)^{1+|I|}=+(-1)^{1+|I|+1}=+(-1)^{1+|J|}[/mm].
>
> Betrachten wir nur folgenden Teil:
>
> [mm]+|B| - \summe_{I:I\subseteq {1,...,l}, I \not= \emptyset}^{} (-1)^{1+|I|}\cdot{}|\bigcap_{i \in I}^{} (A_i\cap B) |[/mm]
>
> Sobald ich hier unter dem Sigma das [mm]I[/mm] durch [mm]J[/mm] austausche
> und [mm]J = I \cup \{A_{\ell + 1}\}[/mm] definiere, muss ich doch
> sogleich auch den Exponenten über der [mm](-1)[/mm] austauschen,
> sodass dort eigentlich sofort [mm](-1)^{1+|J|}[/mm] steht.
Es stand doch [mm] $(-1)^{1+|I|}$ [/mm] in deinem oben zitierten Formelteil. Nun ist $|J|=|I|+1$. Wenn du substituierst wird doch dann [mm] $(-1)^{|J|}$ [/mm] daraus und nicht [mm] $(-1)^{1+|J|}$?
[/mm]
>
> So wie du den Weg beschrieben hast, sieht es so aus, als
> würde man [mm]I[/mm] unter dem Sigma durch [mm]J[/mm] ersetzen, hätte aber
> anschließend immer noch [mm]I[/mm] im Rest der Formel stehen und
> würde dann einen Weg suchen, es umzuformen zu [mm]J[/mm].
>
> Aber das kann doch bei einer Substitution nicht sein!
Das verstehe ich nicht, ich habe es dir doch oben vorgerechnet? Es passieren zwei Dinge: Einmal wird eine (-1) (das "Minuszeichen") in die Potenz aufgenommen und einmal wird $|I|+1$ ersetzt durch $|J|$.
Viele Grüße
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:09 Do 07.02.2019 | | Autor: | magics |
Hallo Marc
Oh man!
[mm]\red{-}(-1)^{1+|I|}=...[/mm]
Das rote Minus kommt von vor der Summation, weil es ja erstmal reingezogen werden darf... da bleibt nur eine Frage: Tomaten, Brett oder Baum.
Ich danke dir!
Grüße
Thomas
|
|
|
|
