Binomialzahlen mit Graphen beweisen

25.05.2019, 19:36	MaPalui	Auf diesen Beitrag antworten »
Binomialzahlen mit Graphen beweisen Hallo ihr Lieben Mir bereitet diese Aufgabe Kopfzerbrechen: [attach]49284[/attach] Meine Ideen: (a) Die linke Seite ist die Möglichkeit, aus n Knoten genau 2 auszuwählen. Das war leicht. Aber was sagt mir die rechte Seite? $\begin{eqnarray} \begin{pmatrix}k \\ 2\end{pmatrix} \end{eqnarray}$ ist die Möglichkeit, 2 Kanten aus k Stück auszuwählen. Das gibt mir ja auch eine gewisse Anzahl an Punkten, jede Kante liefert mir zwei Punkte. Wenn aber nun der Grad eines Punktes >1 ist, würde ich ihn ja mehrfach zählen. Diese Korrektur sehe ich hier leider nicht? Oder bin ich komplett auf dem Holzweg?
25.05.2019, 19:56	HAL 9000	Auf diesen Beitrag antworten »
Teile die Knotenmenge vom Umfang $\begin{eqnarray} n \end{eqnarray}$ in zwei Teilmengen: $\begin{eqnarray} A \end{eqnarray}$ vom Umfang $\begin{eqnarray} k \end{eqnarray}$ sowie $\begin{eqnarray} B \end{eqnarray}$ vom Umfang $\begin{eqnarray} (n-k) \end{eqnarray}$ . Dann gibt es für die Auswahl von zwei Knoten genau drei Fälle: 1) Beide Knoten aus $\begin{eqnarray} A \end{eqnarray}$ ergibt $\begin{eqnarray} \binom{k}{2} \end{eqnarray}$ Möglichkeiten. 2) Beide Knoten aus $\begin{eqnarray} B \end{eqnarray}$ ergibt $\begin{eqnarray} \binom{n-k}{2} \end{eqnarray}$ Möglichkeiten. 3) Jeweils ein Knoten aus $\begin{eqnarray} A \end{eqnarray}$ und $\begin{eqnarray} B \end{eqnarray}$ ergibt $\begin{eqnarray} k\cdot (n-k) \end{eqnarray}$ Möglichkeiten. Mehr steckt nicht dahinter. Im übrigen kann man die genannte Gleichung natürlich auch algebraisch nachweisen. P.S.: Graphentheorie, gar wie du oben sprichst "Grad des Punktes >1" wird hier überhaupt nicht benötigt. Das ist pure Basis-Kombinatorik, mehr nicht.
25.05.2019, 21:08	MaPalui	Auf diesen Beitrag antworten »
Ich Danke dir wieder mal vielmals lieber HAL 9000. Da habe ich mich wieder von vornherein auf eine Möglichkeit versteift. Aber so ist es sehr einsichtig, danke! Die algebraische Lösung wurde extra ausgeschlossen. Um die b) werde ich mich auch noch kümmern, aber für heute mache ich Feierabend. Ich werde aber dazu meine Ideen Posten und würde mich auch dort über ein Feedback freuen!
26.05.2019, 16:51	MaPalui	Auf diesen Beitrag antworten »
Hallo mal wieder, hier meine Ideen zu (b). Betrachten wir einen Graphen $\begin{eqnarray} G=(V,E) \end{eqnarray}$ mit Eckenmenge $\begin{eqnarray} V \end{eqnarray}$ und $\begin{eqnarray} \|V\| = n \end{eqnarray}$ . Teilen wir nun $\begin{eqnarray} V \end{eqnarray}$ auf in $\begin{eqnarray} t \end{eqnarray}$ disjunkte Teilmengen $\begin{eqnarray} V_1,\dots,V_t \end{eqnarray}$ . Dann beschreibt $\begin{eqnarray} \begin{pmatrix}V_i \\ 2\end{pmatrix} \end{eqnarray}$ die Anzahl Möglichkeiten, 2 Knoten aus dieser Teilmenge zu wählen. Die Summe auf der linken Seite entspricht also der Anzahl an Möglichkeiten, aus allen diesen Teilmengen je zwei Knoten auszuwählen. Was nun folgt ist mir an sich klar. Natürlich ist diese Anzahl höchstens so groß wie die Anzahl der Möglichkeiten, aus den gesamten $\begin{eqnarray} n \end{eqnarray}$ Knoten jeweils 2 zu wählen, was ja die rechte Seite ist. Ich tue mir aber gerade sehr schwer damit, das beweisen zu "müssen", da es so trivial erscheint @HAL 9000: Ich habe hier die graphentheoretische Formulierung wieder genutzt, da die Aufgabe es verlangt. Das es sich auch hier um reine Basis-Kombinatorik handelt, ist mir aber bewusst.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »