Zeigen Sie, dass für jede (k, l)-Blume gilt … (Mengen/Mengenfamilie)

Question

Aufgabe Kreativität:

Eine Mengenfamilie $\mathcal{F}=\left\{A_{1}, \ldots, A_{n}\right\}$ heißt $(k, \ell)$-Blume (für $\left.k \geq 1, \ell \geq 0\right)$, wenn alle Durchschnitte von Auswahlen von $k$ Mengen aus $\mathcal{F}$ gleich ein und derselben $\ell$-elementigen Menge sind, d.h., falls eine Menge $B$ mit $\|B\|=\ell$ existiert, sodass $B=\bigcap_{i \in K} A_{i}$ für alle $K \subseteq\{1, \ldots, n\}$ mit $\|K\|=k$ gilt.

Zeigen Sie, dass für jede $(k, \ell)$-Blume $\mathcal{F}=\left\{A_{1}, \ldots, A_{n}\right\}$ gilt:

$\left\|\bigcup \limits_{i=1}^{n} A_{i}\right\|=\sum \limits_{\emptyset \neq K \subseteq\{1, \ldots, n\} \atop\|K\|<k}(-1)^{1+\|K\|}\left\|\bigcap_{i \in K} A_{i}\right\|-(-1)^{k} \cdot\left(\begin{array}{c} n-1 \\ k-1 \end{array}\right) \cdot \ell$

Answer 1

Zunächst überleg was k+1 Elementige TEILMengen für ein Kardinalität haben und beweis es, der Kosub will Beweise sehen.

Dann betrachtest du nur die Siebsumme und endest NICHT wie dort bei k. Alles was ab k steht und die Subtraktion zum Schluss sind gleich(warum????). Jetzt gehst du zum Aufgabenblatt 2 und findest dort (n über k)=n*(n-1 über k-1). Fertig.

Die Zwischenschritte musst selbst lösen.

 

Information Engineering

Konstanz

Comments

was ist eine Siebsumme? Nichtmal Google spuckt was aus...

---

@Anonym: Der Begriff Sieb könnte inspiriert sein vom Primzahlsieb und bezieht sich vermutlich auf die Schnittmenge der A_i , wenn auf eurem Aufgabenblatt resp. in eurem Kurs nichts anderes steht.