Mächtigkeit der Menge aller ungerichteten schleifenlosen Graphen

25.04.2012, 19:51	GlasgowKid	Auf diesen Beitrag antworten »
Mächtigkeit der Menge aller ungerichteten schleifenlosen Graphen Meine Frage: Ich habe folgende Aufgabe: Bestimme die Mächtigkeit der Menge aller ungerichteten Graphen mit n Knoten. Ich stecke dort an einer Stelle fest. Meine Kommilitonen haben folgende Lösung: $\begin{eqnarray} 2^{\frac{n^{2}-n}{2}} \end{eqnarray}$ Meine Ideen: Die Möglichkeiten der Anzahl der Kanten nehmen für jede zusätzliche Kante um 1 ab, d.h. $\begin{eqnarray} k=\sum\limits_{i=1}^{n-1}i \end{eqnarray}$ Die Mächtigkeit der Menge ergibt sich aus der Anzahl der Permutationen mit denen man jede Kante im Graphen anordnen kann: $\begin{eqnarray} \|M\|=\sum\limits_{i=1}^k \begin{pmatrix} k \\ i \end{pmatrix} \end{eqnarray}$ Kann ich das so stehen lassen oder ist das irgendwie eine Doppelsumme? Stimmt der Ansatz? Komme ich jetzt noch irgendwie weiter?
25.04.2012, 20:10	weisbrot	Auf diesen Beitrag antworten »
RE: Mächtigkeit der Menge aller ungerichteten schleifenlosen Graphen für deine formel für die mächtigkeit der meneg kannst du den binom. lehrsatz anwenden, wodurch du auf 2^k kommst. mit deiner 1. formel für k kommst du für k mit der gaußschen summationsformel auf den gegebenen wert von k in abh. von n. lg

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »