Verallgemeinerung Inklusion/Exklusion von Mengen

[BeRsErKeR]

Hallo ich bastel gerade an einer Art Formel für die Mächtigkeit einer Gesamtmenge aus n vereinigten Teilmengen. Dabei kann man ja das Prinzip der Inklusion und Exklusion nutzen (Link).

Der resultierende Satz ist schlüssig aber noch recht abstrakt. Mir ist auch bewusst, dass man das ganze nicht allgemeingültig in eine einfache Formel gießen kann. Mit einfache Formel meine ich hierbei eine Formel, wo ich nicht auf Mengenindizes angewiesen bin, sondern nur konkrete Werte aus der Menge in meiner Formel enthalten sind.

Nun stellt sich mir aber die Frage, ob solche Formeln möglich sind, wenn man die Mengen näher spezifiziert. Genauer gesagt sind die Mächtigkeiten der Schnitte durch Brüche definiert.

Die Mengen sind so geordnet, dass |Mx+1| < |Mx| und |Mx ^ My| = 1/(x*y) gilt. Wobei das ^ hierbei ein Schnitt sein soll. Ferner gilt dadurch auch |Mx ^ My ^ Mz| = 1/(x*y*z) usw.

Der Mengenindex beginnt bei 2. Ich möchte die Vereinigung von allen Mi haben, mit i=2...n. Dabei kann also nicht so etwas wie |M3 u M6| auftreten, sondern die Mengenvereinigungen sollen nur für aufeinanderfolgende Mengen mit M2 als erster Menge möglich sein.


Einfachstes Beispiel wäre nun die Vereinigung von M2 und M3:

|M2 u M3| = |M2| + |M3| - |M2 ^ M3| = x + y - 1/6

Dabei sind x und y bekannt aber in diesem Zusammenhang nicht entscheidend.

Für die Vereinigung bis M4 erhalte ich:

|M2 u M3 u M4| = |M2| + |M3| + |M4| - |M2 ^ M3| - |M2 ^ M4| - |M3 ^ M4| + |M2 ^ M3 ^ M4| = x + y + z - 1/6 - 1/8 - 1/12 + 1/24


Nun meine eigentliche Frage. Gibt es Möglichkeiten, für ein gegebenes n (also der letzte Mengenindex), die Bestandteile außer x, y und z automatisch berechnen zu lassen? Also Formeln die z.B. folgendes vereinfachen:

1/(a*b) + 1/(a*c) + 1/(b*c) = ?/(a*b*c)

oder

1/(x*(x+1)) + 1/(x*(x+2)) + 1/((x+1)*(x+2))



Ich weiß immer folgendes, wenn ein n gegeben ist.

1. Es gibt (n-1) Verknüpfungsebenen: |Mi|, |Mi ^ Mj|, |Mi ^ Mj ^ Mk|, usw.
2. Das Ergebnis ohne x, y, z, ... ist ein Vielfaches von (1/n!).
3. Das Vorzeichen für eine Verknüpfungsebene (siehe 1.) ist stets: (-1) hoch i, wobei i der Index der Verknüpfungsebene (beginnend bei 0) ist.
4. Pro Verknüpfungsebene befinden sich (n i+1) Faktoren im Nenner, wobei hiermit "n über k" gemeint ist, also (n!)/((i+1)! * (n-i-1)!).


Mich interessiert also eine allgemeingültge Formel um (2.) zu berechnen. Dabei würde ich am liebsten nur das n als Parameter übergeben müssen.

Also etwas in der Art f(x) = (?/x!).

Ich wäre auch schon für Lösungsansätze dankbar oder Hinweise auf bestimmte Vereinfachungsmöglichkeiten etc.

[BeRsErKeR]

Was ich schon erkannt habe ist, dass z.B. folgendes gilt:


1/2 + 1/3 + 1/4 - 1/6 - 1/8 - 1/12 + 1/24 = (12 + 8 + 6 - 4 - 3 - 2 + 1) / 24

was so viel bedeutet wie:

1/x + 1/y + 1/z - 1/(x*y) - 1(x*z) - 1/(y*z) + 1/(x*y*z) = (y*z + x*z + x*y - z - y - x + 1) / (z!)

wobei hier natürlich gelten muss: y = x+1 und z = y+1 = x+2.

Die Nenner kann man also mit umgedrehtem Vorzeichen in den Zähler schreiben (das letzte Glied durch 1 ersetzen) und dann alles durch die Fakultät von n teilen. Ist ja quasi nicht viel mehr als den Hauptnenner zu bilden, aber vielleicht kommt man so eher auf eine Lösung. Zumal man hier nicht unbedingt mit Brüchen rechnen muss, sondern sich auf den Zähler konzentrieren kann.

Was mir Schwierigkeiten bereitet, ist etwas allgemeines zu finden um alle Kombinationen der Index-Multiplikationen zu erfassen und das auf (n-1) Verknüpfungsebenen. Das Prinzip von Inklusion und Exklusion arbeitet hier ja mit einem Index, der ein Element einer Indexmenge ist, aber halt ohne konkrete Indexwerte.


Außerdem enthält das Ergebnis jeder Verknüpfungsebene als größten Term: (-1)^i * (n i+1) * 2^(i+1), wobei hier wieder "n über i+1" gemeint ist.

[Brainsmith]

Mir stellt sich gerade die Frage, wie die Mächtigkeit einer Menge ein Bruch sein kann. Mächtigkeit ist im Allgemeinen ein Ausdruck für die Anzahl der Elemente in einer Menge, also ganzzahlig.
Wenn ich das richtig verstehe, ist der Bruch eine Angabe für den prozentualen Anteil einer Gesamtmenge. Ist das so richtig?

Naja, man kann die Werte ziemlich leicht berechnen. Das macht man auch mit der Inklusions-Exklusionsformel.

Angenommen, du hast M1, M2, M3 mit |M1|=x, |M2|=y, |M3|=z

Dann ist |M1 vereinigt M2 vereinigt M3|= |M1| + |M2| + |M3|- ( |M1| geschnitten |M2| + |M1| geschnitten |M3| + |M2| geschnitten |M3| ) + ( |M1| geschnitten |M2| geschnitten |M2| )

Für die Schnitte hast du ja schon eine Formel, wenn ich dich richtig verstanden habe.

Hört sich alles ziemlich statistisch an.

Also versuche ich mal den Ansatz zu erläutern: Du hast immer aufeinanderfolgende Mächtigkeiten. Dann sieht das für mich so aus (obwohl ich der Meinung bin, dass du trotzdem Schnitte bilden musst, die aus Mengen bestehen, die nicht zwingen nacheinander kommen):

Sei n der größte Index des Schnittes und m der kleinste Indes des Schnittes. Dann gilt nach deinen Angaben für die Mächtigkeit
(n-1)! / (m!)

Ich hab irgendwie die Angwohnheit alte Threads zu trollen, äh... auszugraben... Egal, Problem sollte jetzt gelöst sein. Hope, this helps

LG


Brainsmith

PS: Bei mathematischen Fragen (am liebsten nicht numerischer Natur) stehe ich auch über PM zur Verfügung


€dit:

Bei der Inklusions-Exklusionsformel musst du pro Iteration immer alle möglichen Schnitte bilden. Wie bei einer Swingerparty: Jeder mit jedem.