symmetrische Differenz n Mengen ??

[!rr!rr_.]

hallo:

Für die Kardinalität einer Disjunktion von n Mengen A1, ..., An gibt's eine einfache Formel per inclusion-exclusion Prinzip: (Konjunktion schreibe ich hier mal als "*", Disjunktion als "v" )

|A1 v A2 v ... v An| = |A1|+...+|An|-|A1*A2|-...-|A(n-1)*An|+- ... +(-1)^n|A1*A2*...*An|

soweit klar.

ich suche eine ähnliche Formel, aber für die symmetrische Differenz, also die Menge derjenigen Elemente, die genau in ungerade vielen der Mengen gleichzeitig enthalten sind.

Fall n=2: |A1#A2|=|A1|+|A2|-2|A1*A2|

soweit klar.

Aber wie sieht diese Formel für allgemeines n aus ?

|A1#A2#...#An|=??

ich habe zwar eine Vermutung, aber kann um's Verr*ck*en weder in Buch noch im web etwas finden, wo diese Formel steht oder besser noch bewiesen wird.

Ich hab' wirklich alles versucht, finde aber keine Referenz. Kann doch nicht so ungewöhnlich sein

[forentroll]

!rr!rr_. schrieb:

ich habe zwar eine Vermutung

zeig mal.
vielleicht hat jemand lust auf den beweis. mit induktion vielleicht nicht so schwierig. kA.

[Helfer in der Not]

Das hängt wohl nicht nur von den |A_i| ab, sondern auch von den Mengen A_i.

Vermutung: x ist in A1#A2#...#An <=> x ist in einer ungeraden Anzahl der A_i.

[!rr!rr_.]

ich vermute mal:

|A1#...#A2|=|A1|+...+|An|-2|A1A2|-...-2|A(n-1)An|+-...+(-2)^(n-1)|A1A2...An|

also ähnlich wie Formel wie für die |A1 v ... v An|, aber mit den Koeffizienten

(-2)^(k-1)

vor den k-fachen Konjuntionen (statt (-1)^(k-1) bei |A1 v ... v An|)

mir scheint ich kann das jetzt auch per Induktion für beliebige n beweisen, für 2->3 klappt es jedenfalls schon.

bin trotzdem an einer Referenz interessiert, und sei's nur zur Kontrolle

[!rr!rr_.]

die erste Formelzeile soll natürlich beginnen mit:

|A1#...#An| = ...

[Helfer in der Not]

Sag mal, wie deine "Formel" aussehen soll (aus welchen Termen sie gebaut werden soll), und wir helfen dir dann weiter.

[!rr!rr_.]

glaub habs erledigt, Induktion über n scheint zu funktionieren mit:

|A1#A2#...#An| = 
  |A1|+|A2|+...+|An|
  - 2 *          SUM {i1<i2}        |Ai1*Ai2|
  + 4 *          SUM {i1<i2<i3}     |Ai1*Ai2*Ai3|
  -+ ...
  + (-2)^(n-1) * SUM {i1<i2<...<in} |Ai1*Ai2*...*Ain|

wobei

|A| = Mächtigkeit der Menge A
* = Konjunktion von Mengen
i1,...,in = Indizes aus 1...n
# = n-äre symm. Differenz