Inklusion-Exklusion Menge/Mächtigkeit

Question

Moin,

ich kommen mit der folgenden Aufgabe gar nicht zurecht

Von \( n \geq 2 \) Mengen \( A_{i}(i=1, \ldots, n) \) der Mächtigkeit \( n-1 \) sei bekannt, dass \( k(2 \leq k \leq n) \) beliebig ausgewählte Mengen stets genau \( n-k \) gemeinsame Elemente haben. Wie viele Elemente enthält \( \cup_{i=1}^{n} A_{i} \) ? Vereinfachen Sie das Ergebnis soweit, dass es kein Summenzeichen mehr enthält.

Wäre nett, wenn mir jemand helfen könnte !

vielen Dank :)

Comments

Du könntest doch schonmal Eure Version des Inklusions-Exklusions-Satzes hierhin schreiben, dann hätten wir die Äußerlichkeiten schonmal geklärt.

Dann könntest Du darin in offensichtlicher Weise die Information aus der Aufgabenstellung einsetzen und dann wird Dir ganz schnell jemand weiterhelfen.

Gruß Mathhilf

---

Moin,

(Prinzip von Inklusion und Exklusion). Seien A1, . . . , An endliche
Mengen. Dann gilt:

\( \begin{aligned}\left|A_{1} \cup \cdots \cup A_{n}\right|=& \sum \limits_{i=1}^{n}\left|A_{i}\right|-\sum \limits_{1 \leq i<j \leq n}\left|A_{i} \cap A_{j}\right|+\cdots+\\ &(-1)^{k-1} \sum \limits_{1 \leq i_{1}<\cdots<i_{k} \leq n}\left|A_{i_{1}} \cap \cdots \cap A_{i_{k}}\right| \pm \cdots+(-1)^{n-1}\left|A_{1} \cap \cdots \cap A_{n}\right| \end{aligned} \)

Ich weiß:

 \( \left|A_{i}\right| \)= n - 1

\( \left|A_{i} \cap A_{j}\right| \) = n - 2

\( \left|A_{1} \cap \cdots \cap A_{n}\right| \) = n - k

Answer 1

Ok,

dann hätten wir für die erste Summe: n(n-1).

Für die weiteren Summen gilt: Die Anzahl der Elemente in den Durchschnitten hängt nur von k ab, nicht von den konkreten \(i_j\). Daher müssen wir nur wissen, wieviele solche \(i_1< \cdots < i_k\) es gibt und das sind gerade \({ n \choose k}\). Also haben wir

$$n(n-1)+\sum_{k=2}^n (-1)^{k-1}(n-k) {n \choose k}$$

Jetzt müssen wir noch den allgemeinen Summanden umformen. Schreib dazu mal die Definition des Binomialkoeffizienten hin und versuche den Faktor (n-k) zu kürzen ....

Gruß Mathhilf

Comments

\( \sum \limits_{k=2}^{n}(-1)^{k-1}(n-k) \cdot \frac{n !}{k ! \cdot(n-k) !} \)

Ich habe mit dem Kürzen allerdings Probleme ...

---

Wie wäre es mit

$$\frac{n-k}{(n-k)!}=\frac{1}{(n-1-k)!}$$

Wenn Du im Zähler noch ein n ausklammerst hast Du den Binomialkoeffizienten \({n-1 \choose k}\).

Dann wollen wir den allgemeinen binomischen Lehrsatz verwenden. Dazu musst Du mal schauen, was Du mit den Termen mit k=0,1,n machen kannst ....

Gruß Mathhilf