Inklusion-Exklusion, Kardinalität, Mengen

26.11.2021, 16:51	AlexH	Auf diesen Beitrag antworten »
Inklusion-Exklusion, Kardinalität, Mengen Meine Frage: Bestimmen Sie mit Hilfe des Prinzips der ?Inklusion- Exklusion? die Kardinalität der folgenden Mengen. a) Die Anzahl der Personen einer Testgruppe aus 100 Personen, die nicht Englisch, Französisch, oder Russisch sprechen. Bekannt ist dabei folgendes: 48 Personen sprechen Russisch, 45 Personen können Französisch und 67 Personen sprechen Englisch. Genau 13 der Personen beherrschen alle 3 Sprachen. Außerdem können 29 Personen Englisch und Französisch, 27 Personen sprechen Englisch und Russisch und 18 Person sprechen Russisch und Französisch. b) Die Anzahl der natürlichen Zahlen kleiner oder gleich 10000, die durch keine der Zahlen 2, 5, 11, 17 teilbar sind. Meine Ideen: Ich habe das additive Zählprinzip und die Permutationen verwendet, würde mich jedoch freuen, wenn die Lösung vorgestellt und geklärt wird. Danke!
26.11.2021, 17:32	HAL 9000	Auf diesen Beitrag antworten »
Die Inklusions-Exklusions-Formel für eine endliche Indexmenge $\begin{eqnarray} I \end{eqnarray}$ und auch sämtlich endliche $\begin{eqnarray} A_i \end{eqnarray}$ lautet $\begin{eqnarray} \left\|\bigcup_{i\in I} A_i\right\| = \sum_{\emptyset\neq T\subseteq I} (-1)^{\|T\|-1} \left\| \bigcap_{j\in T} A_j\right\| \end{eqnarray}$ . Es seien nun alle Mengen $\begin{eqnarray} A_i \end{eqnarray}$ Teilmengen einer ebenfalls endlichen Obermenge $\begin{eqnarray} \Omega \end{eqnarray}$ , bezüglich der man auch die Komplementoperation versteht, d.h., $\begin{eqnarray} A^c :=\Omega\setminus A \end{eqnarray}$ . Definiert man nun noch den Durchschnitt über eine leere Menge als $\begin{eqnarray} \Omega \end{eqnarray}$ , d.h., $\begin{eqnarray} \bigcap_{j\in \emptyset} A_j := \Omega \end{eqnarray}$ (so wie man das leere Produkt als 1 definiert), dann kann man kurz und knackig schreiben $\begin{eqnarray} \left\|\bigcap_{i\in I} A_i^c\right\| = \left\|\Omega\setminus\left(\bigcup_{i\in I} A_i\right)\right\| = \left\|\Omega\right\| - \left\|\bigcup_{i\in I} A_i\right\| \stackrel{!}{=} \sum_{T\subseteq I} (-1)^{\|T\|} \left\| \bigcap_{j\in T} A_j\right\| \end{eqnarray}$ . ------------------------------------------------- Genau diese letztere Formel wendet man hier auf beide genannten Teilprobleme an: a) Für $\begin{eqnarray} I=\{1,2,3\} \end{eqnarray}$ , die Menge $\begin{eqnarray} \Omega \end{eqnarray}$ aller Personen der Testgruppe sowie $\begin{eqnarray} A_1,A_2 \end{eqnarray}$ bzw. $\begin{eqnarray} A_3 \end{eqnarray}$ die Mengen der Englisch, Französisch bzw. Russisch sprechenden Personen. b) Für $\begin{eqnarray} I=\{2,5,11,17\} \end{eqnarray}$ , die Menge $\begin{eqnarray} \Omega=\{1,2,\ldots,10000\} \end{eqnarray}$ sowie $\begin{eqnarray} A_i \end{eqnarray}$ die Menge der Zahlen aus $\begin{eqnarray} \Omega \end{eqnarray}$ , die durch $\begin{eqnarray} i \end{eqnarray}$ teilbar sind. Bei a) sind alle nötigen Durchschnittsmengenkardinalitäten im Text angeführt. Bei b) überlegt man sich rasch $\begin{eqnarray} \left\|\bigcap_{j\in T} A_j\right\| = \left\lfloor \frac{10000}{k} \right\rfloor \end{eqnarray}$ , wobei $\begin{eqnarray} k \end{eqnarray}$ das kleinste gemeinsame Vielfache der Werte aus $\begin{eqnarray} T \end{eqnarray}$ ist. Da wir hier nur Primzahlen in $\begin{eqnarray} I \end{eqnarray}$ und damit auch $\begin{eqnarray} T \end{eqnarray}$ vorliegen haben, ist dieses kgV einfach das Produkt der Werte aus $\begin{eqnarray} T \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »