Nichtleere Menge N; Anzahl Teilmengen mit einer geraden Anzahl Elementen.

Question

N nichtleere endliche Menge.  Nun soll ich zeigen, dass

Anzahl Teilmengen mit geraden Anzahl Elemente = Anz. TM mit ungeraden Anz. Elementen

Und ich soll noch herausfinden wie gross diese Anzahl ist.

Für die Anzahl der Teilmengen mit geraden Anzahl Elemente habe ich mir dies gedacht:

k=Anzahl Elemente bis n SUMME: (Anzahl Elemente über Anzahl Elemente/2)   (Sorry, sollte binominal Faktoren darstellen)

Falls dies stimmt wäre ja die Darstellung für gerade und ungerade Zahlen die selbe!?



Und wie sollte ich von hier (falls es denn einigermassen richtig wäre) auf einen echten Wert für die Anzahl Teilmengen kommen?

mfg

Answer 1

Annahme N hat n Elemente.

Wieviele Teilmengen gibt es total?

Jedes Element kann zur Teilmenge gehören oder nicht. D.h. es gibt 2*2*2...*2=2^n Teilmengen. [2 von denen: die leere Menge und N selbst werden mW bei gewissen Definitionen von Teilmenge ausgenommen. Dann gäbe es 2^n - 2 echte Teilmengen]

Falls n ungerade ist, hat das Komplement K jeder Teilmenge von N mit einer geraden Anzahl Elementen  eine ungerade Anzahl Elemente. Es gibt deshalb gleichviele Teilmengen mit geraden und ungeraden Elementen: Nämlich je 2^n / 2 = 2^{n-1}

Falls n gerade ist, kann man nicht so direkt argumentieren. Da müsstest du nun noch eine andere Erklärung einfallen lassen. Rauskommen sollte auch hier, dass es je 2^{n-1} Teilmengen gibt.

Comments

Hallo Lu

 

 Danke vielmals für deine Antwort, war wiedermal auf dem Holzweg ;)

 

Kann ich der letzte Punkt nicht mit:

2^n-1+x = 2ⁿ ⇒x=2^n-1

begründen?

Und wie nehme ich die Bedingung des Auschlusses der leeren Menge mit ein?

Anz. Teilmengen ist ja dann; 2ⁿ-1

Und somit müsste es dann; (2^n-1-p₁)+(2^n-1-p₂)=2^N-1 ⇒ p₁+p₂=1 ⇒p1=0.5 und p2=0.5 sein?

 

Und wie ich daraus eine "echte Zahl" für die Anzahl der Elemente ist mir nicht klar.

 

Danke nochmals.

---

Wir hatten es so definiert das die Leere Menge als auch die gesamte Menge Teilmenge einer Menge sind. Allerdings unechte Teilmengen. Echte Teilmengen gibt es also wie Lu behauptet hat 2 weniger. Dann hättest du 2^n-2 echte Teilmengen. Da aber davon in der Aufgabenstellung kein Wort verloren ist definier doch einfach das zu deinen Teilmengen die beiden unechten Teilmengen dazugehören. Sehr gut kann man zeigen das die Anzahlen gleich sind am pascalschen Dreieck. Schau dort einfach mal wie sich die Geraden Elemente und die ungeraden durch Summierung ergeben. Dann sollte dir etwas auffallen. Das kann man natürlich auch nehmen um die Gesamtzahl von 2^n zu zeigen. Aber das hat Lu ja schon wirklich sehr schön vorgemacht.