Kombinatorische Argumentation?

Question

Ich habe 2 Aufgaben zur kombinatorische Argumente.

a) (n über 2)= (n^2-n)/2

b) (n über k)= (n-2 über k-2)+ 2*(n-2 über k-1)+ (n-2 über k)

Ich stelle mir das meistens mit Personen vor.

Zu a) hab ich den Ansatz:

Links: Anzahl der Möglichkeiten 2 elementige Teilmengen aus einer n- elementigen Menge zu bilden.

Rechts: ( kann man umschreiben als (n(n-1))/2) Anzahl der Möglichkeiten aus n Elementen eines zu markieren und aus den übrigen Element eine beliebige Teilmenge zu wählen.

Beide Seiten führen zum selben Ergebnis.

Ist das richtig oder muss ich was hinzufügen oder ganz anders, hab ich das falsch verstanden ?

Und zu der b) hab ich bisschen recherchiert und bin zum Ergebnis gekommen, dass man das mit Hilfe des Pascalischen -Dreiecks erklären kann. ich versteh aber mich genau den Zusammenhang von dem Dreieck mit der oben gegebenen Formel.

Ich wäre für jede Hilfe sehr dankbar. :-)

Answer 1

Du sollst zeigen das die Gleichungen stimmen?

Dann kannst du das einmal aus kombinatorischer Sicht begründen. Du könntest aber auch die Binomialkoeffizienten als Formelausdruck mit Fakultäten schreiben und dann vereinfachen

(n über k) = (n-2 über k-2) + 2*(n-2 über k-1) + (n-2 über k)

n!/(k!·(n - k)!) = (n - 2)!/((k - 2)!·((n - 2) - (k - 2))!) + 2*(n - 2)!/((k - 1)!·((n - 2) - (k - 1))!) + (n - 2)!/(k!·((n - 2) - k)!)

n!/(k!·(n - k)!) = (n - 2)!/((k - 2)!·(n - k)!) + 2*(n - 2)!/((k - 1)!·(n - k - 1)!) + (n - 2)!/(k!·(n - k - 2)!)

wir multiplizieren mit k!

n!/(n - k)! = (n - 2)!·(k - 1)·k/(n - k)! + 2*(n - 2)!·k/(n - k - 1)! + (n - 2)!/(n - k - 2)!

wir multiplizieren mit (n - k)!

n! = (n - 2)!·(k - 1)·k + 2*(n - 2)!·k·(n - k) + (n - 2)!·(n - k - 1)·(n - k)

n! = (n - 2)!·((k - 1)·k + 2·k·(n - k) + (n - k - 1)·(n - k))

n! = (n - 2)!·(k^2 - k + 2·k·n - 2·k^2 + k^2 - 2·k·n + k + n^2 - n)

n! = (n - 2)!·(n^2 - n)

n! = (n - 2)!·n·(n - 1)

n! = n!

Das ist natürlich etwas umständlicher geht aber auch so.

Comments

Erstmal vielen Dank für Ihre Hilfe.

Also Sie haben das ja mathematisch bewiesen, dass beide Seiten gleich sind. Aber bei der kombinatorische Argumentation muss man erklären, warum beide Seiten gleich sind bzw. man muss für eine Formel / Ein Problem zwei unterschiedliche Seiten erklären und erläutern das beide Seiten gleich sind.

Und gerade da bin ich mir bei beiden Aufgaben unsicher.

---

Das erste war doch richtig

(n über 2) = (n^2 - n)/2

(n über 2) = n * (n - 1) / 2

(n über 2) ist die Anzahl an Möglichkeiten die man hat aus n Elementen genau 2 auszuwählen.

Für das erste Element hat man n Möglichkeiten, für das zweite Element hat man nur noch (n - 1) Möglichkeiten. Da die Reihenfolge keine Rolle spielen soll muss man noch durch die Anzahl der Reihenfolgen bei zwei Elementen teilen. Also durch 2 teilen. Das spiegelt genau die Formel wieder.

---

Das nächste mit dem Pascalschen Dreieck zu berechnen ist auch richtig

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Wie berechnest du jetzt die 6

6 = 3 * 3 = (1 + 2) + (2 + 1) = 1 + 2*2 + 1

Das ist die Formel die Dahintresteckt.

Wenn jetzt die 6 also (n über k) ist. in diesem Fall (4 über 2). Wie berechnest du dann (n über k) mit Binomialkoeffizienten.

(4 über 2) = (3 über 1) + (3 über 2) = (2 über 0) + 2 * (2 über 1) + (2 über 2)

(n über k) = (n-1 über k-1) + (n-1 über k) = (n-2 über k-2) + 2 * (n-2 über k-1) + (n-2 über k)

---

Alles klar, da bin ich aber glücklich :) und für die b) kann ich dann Ihren Weg auch als kombinatorische Argumentation verstehen oder wäre das schon mathematisch Rechenweg bzw. Beweis ?

Weil sonst hätte ich noch gesagt für die b) dass

Links: Anzahl der Möglichkeiten k elementigen Teilmenge aus einer n elementigen Menge zu bilden.

 Rechts: Erklärung mittels Pascalischen Dreieicks. Das k-te Element der Zeile n ist die Summe der beiden schräg darüber stehenden (k-1)-ten und k-ten Elements der (n-1)-ten Zeile. Die aus der Summe aus dem (k-2)-Zen und (k-1)-Zen Elements der (n-2) -ten  Zeile bzw. des (k-1)-ten und k-ten Elements der (n-2)-ten Zeile ist. Also aus der (k-2)-ten und k-ten Element der (n-2)-ten Zeile und dem doppelten des (k-1)-ten Elements der (n-2)-ten Zeile.

Beide Seiten stimmen überein.

Wäre das richtig ?

---

Beide Seiten stimmen überein.
Wäre das richtig ?

Ja. Das ist so richtig.
Ich sehe das nicht als mathematischen Rechenweg, weil man nichts gerechnet hat. Das ist die einfache kombinatorische Herleitung über das Pascalsche Dreieck.

---

Okay vielen Dank :)

Haben Sie vielleicht sonst noch Tipps, wie man sich solche kombinatorischen Argumente gut vorstellen kann oder das gut erklären könnte ? :-)

---

Du solltest dich selber mal mit ähnlichen Aufgaben beschäftigen. Hier auf der Seite sind auch welche. Allerdings weiß ich da nicht genau wie man danach suchen soll.

Aber z.B

Begründe oder Beweise

(n über k) = (n über n-k)