Wie viele 4-elementige Teilmengen gibt es von der Menge {1,2,...,7}, die eine 6 oder 7 enthalten?

Question

Aufgabe:

Wie viele 4-elementige Teilmengen gibt es von der Menge {1,2,...,7}, die eine 6 oder 7 enthalten?

Spoiler: Die Lösung ist 2*(6 über 3) - (5 über 2) 

Problem/Ansatz:

Ich weiß, dass gilt:

ohne Wiederholen (in einer Menge kommen keine Zahlen doppelt vor) und

ohne Reihenfolge (denn z.B. {1,2,6,7} = {6, 7, 1, 2})

Die Anzahl der 4-elementigen Teilmengen ist (7 über 4), das hilft mir hier aber nicht wirklich weiter.

Die 2*(6 über 3) aus der Lösung stelle ich mir so vor, dass hier der Fall abgedeckt ist, dass man entweder eine 6 in der Menge hat und dann noch 3 andere Zahlen aus den übrigen 6 Zahlen auswählen kann und analog mit der 7 (deshalb *2).

(5 über 2) verstehe ich so, dass man eine 6 und eine 7 in der Menge hat und dann noch aus den 5 übrigen Zahlen 2 Stück auswählt, um auf die 4-elementige Teilmenge zu kommen.

Mein Problem ist aber das minus... Warum zieht man (5 über 2) ab? Das "oder" haben wir in der Vorlesung eigentlich als inklusives-oder definiert, d.h. dass sowohl eine Teilmenge wie {1,2,6,5} als auch {1,2,6,7} erlaubt ist. Müsste dann nicht eigentlich

2*(6 über 3) + (5 über 2)

die Lösung sein oder woran liegt es, dass man die Anzahl mit beiden Zahlen in der Teilmenge abzieht?

Aus Interesse: Was wäre die Lösung, wenn die Frage lautet: Wie viele 4-elementige Teilmengen gibt es von der Menge {1,2,...,7}, die eine 6 und 7 enthalten? Wäre das (6über 3) * (5 über 2) ??

Comments

Die 2*(6 über 3) aus der Lösung stelle ich mir so vor, dass hier der Fall abgedeckt ist, dass man entweder eine 6 in der Menge hat und dann noch 3 andere Zahlen aus den übrigen 6 Zahlen auswählen kann und analog mit der 7 (deshalb *2).

Jetzt hast du also eine 6 in der Menge und wählst aus den übrigen noch 1,2 und 7 aus

Dann später für den zweiten Binomialkoeffizienten betrachtest du: Du hast eine 7 in der Menge und wählst aus den übrigen noch 1,2 und 6 aus.

Das heißt du zählst die Mengen in denen 6 und 7 vorkommen doppelt. Dieser Fehler wird durch die Subtraktion wieder ausgeglichen.

---

Du könntest analog auch

2*(5 über 3) + (5 über 2)

rechnen.

Da schließt du im ersten Summanden aus, dass 6 und 7 gleichzeitig in der Menge sein können (indem du für die 3 übrigen Zahlen in den Mengen erst einmal nur die 5 Zahlen 1, __, 5 betrachtest) und musst die Anzahl der Mengen mit 6 und 7 deshalb später addieren.

---

Was wäre die Lösung, wenn die Frage lautet: Wie viele 4-elementige Teilmengen gibt es von der Menge {1,2,...,7}, die eine 6 und 7 enthalten? Wäre das (6über 3) * (5 über 2) ??

Da hättest du ja in jeder Menge genau 2 Stellen frei, die du mit den

Elementen aus {1,2,...,5} belegen kannst, das wäre also einfach (5 über 2).

Answer 1

Aus der Menge {1,2,3,4,5,6,7} wird die 7 entfernt:

    {1,2,3,4,5,6}

Dann werden alle dreielementigen Teilmengen gebildet. Derer gibt es \(6\choose 3\). Zu jeder dieser Teilmengen wird die 7 hinzugefügt.

(I) Es gibt also \(6\choose 3\) vierlementige Teilmengen von {1,2,3,4,5,6,7}, die die 7 enthalten.

(II) Ebenso gibt es \(6\choose 3\) vierlementige Teilmengen von {1,2,3,4,5,6,7}, die die 6 enthalten.

Allerdings gibt es auch \(5\choose 2\) vierlementige Teilmengen von {1,2,3,4,5,6,7}, die sowohl die 6, als auch die 7 enthalten. Diese Teilmengen zählen sowohl zu (I), als auch zu (II). Sie wurden also doppelt gezählt, müssen also ein mal abgezogen werden um nur ein mal gezählt worden zu sein.

Answer 2

Ich verstehe es so:

(6 über 3) ist die Anzahl der 3-elementigen Teilmengen von {1,2,...,5,7}.

Jede davon kann mit einer 6 zu einer 4-elementigen gemacht werden, die

jedenfalls die 6 enthält.

und ebenso die Anzahl der 3-elementigen Teilmengen von {1,2,...,6}.

Hier kann man bei jeder eine 7 dazu tun.

Das sind also insgesamt 2(6 über 3) Stück.

Jetzt hat man allerdings einige doppelt gezählt, denn z.B. {1,2,6,7}

kann bei den ersten aus {1,2,7}∪{6} und bei den zweiten

aus   {1,2,6}∪{7}.

Die Anzahl dieser doppelt gezählten ist (5 über 2), denn die enthalten ja

alle außer 6 und 7 nur eine 2-el. Teilmenge von {1,...,5}. Also passt:

2*(6 über 3) - (5 über 2)