Kombinatorik

08.05.2006, 10:41	Thomander	Auf diesen Beitrag antworten »
Kombinatorik Hallo zusammen! Ich habe folgendes Problem: Gegeben sei eine endliche Menge P von Personen. Nun sei eine 2er-Freundschaft definiert als 2-elementige Teilmenge {a,b} von P. Jede Person ist mit genau 4 anderen Personen befreundet. Man beweise: Die Anzahl der 2er-Freundschaften ist 2*\|P\| Ich finde keinen Ansatz, wie findet man die Anzahl der Teilmengen? mfg Thomander
08.05.2006, 12:18	AD	Auf diesen Beitrag antworten »
Das ist das simple Prinzip des doppelten Abzählens: Sei die gesuchte Anzahl $\begin{eqnarray} n \end{eqnarray}$ . Dann betrachte man die Menge $\begin{eqnarray} F = \{ (a,b) \bigm\| a,b \;\mbox{sind Freunde} \} \end{eqnarray}$ der geordneten Paare von Freunden. (1) Zu jeder Person $\begin{eqnarray} a \end{eqnarray}$ gehören genau 4 Zweierfreundschaften, macht in der Summe $\begin{eqnarray} \|F\|=4\|P\| \end{eqnarray}$ . (2) Zu jeder Zweierfreundschaft $\begin{eqnarray} \{a,b\} \end{eqnarray}$ gehören genau zwei Paare aus $\begin{eqnarray} F \end{eqnarray}$ , nämlich $\begin{eqnarray} (a,b) \end{eqnarray}$ und $\begin{eqnarray} (b,a) \end{eqnarray}$ , also ist $\begin{eqnarray} \|F\|=2n \end{eqnarray}$ . Es ergibt sich $\begin{eqnarray} 4\|P\|=2n \end{eqnarray}$ , also $\begin{eqnarray} n=2\|P\| \end{eqnarray}$ .
08.05.2006, 12:46	Thomander	Auf diesen Beitrag antworten »
Danke, ist ja echt mal logisch. das ich da nicht drauf gekommen bin...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »