Abzählen

05.12.2012, 20:56

Kombibori

Anzahl/Kombinationen/Abzählen

Folgende Aufgabe:

Es gibt ein Mengensystem X, welches aus 4-elementigen Teilmengen von der Menge A = {1, ...., 8} besteht. Dabei gilt, dass jede ganze Zahl zwischen 1 und 8 in genau drei Elementen der Menge M enthalten ist. Wie viele Elemente beinhaltet das Mengensystem X?

Lösung: 3*8 = 4*n -> n = 6. (Prinzip des doppelten Abzählens)

Kann mir das jemand erläutern?

Ich verstehe es so..
X = { {n1,n2,n3,n4}, ..., {n4,n5,n6,n7}, ...}, sprich, dass es eben um Mengen der Mächtigkeit |4| geht.
[Das hätte ich interpretiert als "Aus 8 Elementen müssen 4 ausgewählt werden". Also 4 aus 8.
Ergibt 70 mögliche Kombinationen von 4 Elementen.]

Dabei darf aber jedes n nur genau 3 mal auftauchen.

Also wie ich hier das Prinzip des doppelten Abzählens anwende ist mir leider mehr als unklar. traurig

05.12.2012, 21:06

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Kombibori
[Das hätte ich interpretiert als "Aus 8 Elementen müssen 4 ausgewählt werden". Also 4 aus 8.
Ergibt 70 mögliche Kombinationen von 4 Elementen.]

Das ist die Anzahl aller möglichen solchen 4er-Teilmengen, ja.

Das genannte Mengensystem $\begin{eqnarray*} X \end{eqnarray*}$ enthält aber gar nicht alle diese 70 Teilmengen, sondern nur einen gewissen Teil davon, sagen wir $\begin{eqnarray*} n \end{eqnarray*}$ solche Teilmengen mit zunächst unbekanntem $\begin{eqnarray*} n \end{eqnarray*}$ .

a) Diese $\begin{eqnarray*} n \end{eqnarray*}$ Teilmengen mit je $\begin{eqnarray*} 4 \end{eqnarray*}$ Elementen enthalten also insgesamt $\begin{eqnarray*} 4\cdot n \end{eqnarray*}$ Zahlen, wobei mehrfach vorkommende Zahlen entsprechend auch mehrfach gezählt werden.

b) Andererseits hast du aber auch noch die Information, dass eben diese "Mehrfachzählerei" ergeben soll, dass jeder der Zahlen 1,...,8 genau dreimal auftauchen muss, dass sind also von der Warte aus $\begin{eqnarray*} 3\cdot 8 = 24 \end{eqnarray*}$ Zahlen.

Da es um dieselbe Situation geht, müssen die Anzahlen aus a) und b) übereinstimmen, was sich dann in der Gleichung $\begin{eqnarray*} 4\cdot n = 3\cdot 8 \end{eqnarray*}$ äußert.

05.12.2012, 21:20

Kombibori

Auf diesen Beitrag antworten »

Danke wie immer!
Muss ich mir wohl noch etwas auf der Zunge zergehen lassen ;-)

Eine Frage zum Abzählprinzip.

In der Vorlesung war da die Rede von Relationen und Summierungen.

Was ich meine ist ein wie ich glaube sehr bekanntes typisches Beispiel mit der Stundentinnen-zahl.
"Es gibt 32 männliche Studierende. Jeder davon ist mit 5 Studentinnen befreundet. Jede Stundentin wiederum mit 8 Studenten. Wie viele Studentinnen besuchen die Vorlesung?".

Als Lösung wird angegeben, dass die Menge aller männlichen Studenten A sei, die Menge aller Studentinnen B.
Dann wird die Eigenschaft "befreundet mit" als Relation angesehen, Relation R.

Folgendes wird angegeben

$\begin{eqnarray*} 32*5= \sum_{i=1}^{32} r_i(R) = \sum_{j=1}^n c_j(R) = n*8 \end{eqnarray*}$

Was bedeutet das denn?

05.12.2012, 21:55

HAL 9000

Auf diesen Beitrag antworten »

Genau dasselbe wie im ersten Beispiel: Man zählt die Relationsmenge

$\begin{eqnarray*} R = \{ (m,f) \bigm| \mbox{Student $m$ ist mit Studentin $f$ befreundet} \} \end{eqnarray*}$

doppelt ab. Im ersten Beispiel war es entsprechend

$\begin{eqnarray*} R = \{ (z,n) \bigm| \mbox{Zahl $z$ ist in Teilmenge Nr. $n$ enthalten} \} \end{eqnarray*}$ ,

ich weiß jetzt nicht, wo du den prinzipiellen Unterschied siehst. Vielleicht lässt du dich auch nur durch die Symbolik mit den $\begin{eqnarray*} r_i(R) \end{eqnarray*}$ und $\begin{eqnarray*} c_j(R) \end{eqnarray*}$ verwirren, wenn du die verstehen willst, musst du dich eben mit deren Definition befassen.

Neue Frage »

Antworten »

Anzahl/Kombinationen/Abzählen

Verwandte Themen