Kombinatorischer Beweis

Erste Frage Aufrufe: 537     Aktiv: 17.08.2020 um 15:46
1

Um von dem dritten auf den zweiten Term zu kommen, kannst du die Summe rückwärts betrachten. \( \binom{n}{2} \) gibt genau die anzahl derjenigen tripel an, die 2 aus den ersten n Elementen und das n+1'te Element enthalten. Analog gibt  \( \binom{j}{2} \) die anzahl derjenigen tripel an, die 2 aus den ersten j Elementen und das j+1'te Element enthalten. Somit gilt gleichheit. Um von dem zweiten auf den ersten term zu kommen, betrachte den ausdruck \( i\cdot(n-i) = i \cdot ((n+1) - (i+1)) \) als die anzahl derjenigen tripel, die \(i+1\) enthalten und ein element das kleiner als \(i+1\) ist und ein element das größer als \(i+1\) ist. somit gilt da auch gleichheit zum dritten term

Diese Antwort melden
geantwortet

Student, Punkte: 2.33K

 

Vielen Dank für die Antwort. Kannst du vielleicht Literatur zur abzählenden Kombinatorik empfehlen? (Gerne mit vielen Übungsaufgaben) Es fällt mir nämlich leider noch reicht schwer, weswegen ich mich gerne mehr damit befassen würde   ─   ReSa 17.08.2020 um 15:30

Eventuell das buch von cameron über kombinatorik. Oder Diestel über graphentheorie.
Ersteres findest du eventuell kostenlos im internet, letzteres aber auf jeden fall.
Falls die dir nicht gefallen sollten - oft hilft es auch schon ungemein, alle aufgaben ein zweites oder drittes mal zu machen und dadurch die ideen zu verinnerlich (hier zum beispiel abzählen der tripel durch festlegung von einem element, einmal das größte und einmal das mittelgroße)
  ─   b_schaub 17.08.2020 um 15:46

Kommentar schreiben