Anzahl der Möglichkeiten Punkte verbinden

29.02.2024, 10:27	Susanne04	Auf diesen Beitrag antworten »
Anzahl der Möglichkeiten Punkte verbinden Meine Frage: Gegeben seien zwei Türme mit jeweils $\begin{eqnarray} n \end{eqnarray}$ Punkten (z.B für $\begin{eqnarray} n=2 \end{eqnarray}$ sieht die Anordnung aus wie die 4 auf einem Würfel, für $\begin{eqnarray} n=3 \end{eqnarray}$ wie die 6 auf dem Würfel). Wie viele Möglichkeiten gibt es, die Punkte der Türme unter folgenden Bedingungen zu verbinden: 1. Eine Verbindungsstrecke beginnt immer in einem Punkt des 1. Turms und endet in einem Punkt des 2. Turms 2. Je zwei Verbindungsstrecken sind disjunkt, insbesondere können keine zwei Verbindungen im selben Punkt enden. Meine Ideen: Für $\begin{eqnarray} n=2 \end{eqnarray}$ existieren z.B $\begin{eqnarray} 6 \end{eqnarray}$ Möglichkeiten (auch keine Strecken einzuzeichnen zählt als eine Möglichkeit). Für allgemeines n komme ich aber nicht weiter Als Hinweis ist gegeben die Aufgabe mit den Wegen von $\begin{eqnarray} (0,0) \end{eqnarray}$ nach $\begin{eqnarray} (n,n) \end{eqnarray}$ in Verbindung zu bringen
29.02.2024, 11:41	HAL 9000	Auf diesen Beitrag antworten »
Betrachten wir mal nur die Konfigurationen mit genau $\begin{eqnarray} k \end{eqnarray}$ Strecken: Dann haben wir links $\begin{eqnarray} k \end{eqnarray}$ Startpunkte, die wir aus $\begin{eqnarray} n \end{eqnarray}$ auswählen können, und rechts ebenfalls $\begin{eqnarray} k \end{eqnarray}$ Endpunkte, die wir auch wieder aus $\begin{eqnarray} n \end{eqnarray}$ auswählen können. Jede solche Auswahl liefert nun genau eine (!) solche Verbindungskonfiguration, schlicht wegen der geforderten Kreuzungsfreiheit der Verbindungsstrecken (man verbindet immer die beiden obersten noch übrig gebliebenen Punkte beider Spalten, und das insgesamt $\begin{eqnarray} k \end{eqnarray}$ -mal). Die Gesamtanzahl ist demnach $\begin{eqnarray} \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} \end{eqnarray}$ . Für den Nachweis dieser letzteren Formel kann der gegebene Hinweis nützlich sein. Man kann die Formel aber auch dadurch gewinnen, dass man $\begin{eqnarray} (1+x)^{2n} = (1+x)^n\cdot (1+x)^n \end{eqnarray}$ links wie rechts gemäß Binomischen Satz entwickelt und dann einen Koeffizientenvergleich für Potenz $\begin{eqnarray} x^n \end{eqnarray}$ durchführt. EDIT (5.3.24): Entweder eingeschlafen, oder von der Fraktion "Rückmeldung überflüssig". Naja, kann man nichts machen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »