Mit doppeltem Abzählen beweisen: (n tief k)*(k tief l) = (n tief l)*((n-l) tief (k-l)

Question

Durch doppeltes Abzählen beweisen:

Für alle n,k,l aus N mit n>=k>=l gilt:

$$\begin{pmatrix} n\\k \end{pmatrix}\begin{pmatrix} k\\l \end{pmatrix} = \begin{pmatrix} n\\l \end{pmatrix}\begin{pmatrix} n-l\\k-l\end{pmatrix}$$

Wie muss ich da vorgehen?

Zweiter Teil der Frage:

b) b) ∀n ∈ N mit n ≥ 3 gilt: ∑i=1(i − 1)(n − i) = (n ueber 3)

Comments

Vom Duplikat:

Titel: zeigen durch doppeltes abzählen

Stichworte: beweis

Aufgabe:

Zeigen Sie durch doppeltes Abzählen die folgenden Aussagen:

a) ∀n, k, l∈ N mit n ≥ k ≥ l gilt : (n ueber k) (k ueber l) = (n ueber l) (n-l ueber k-l)

b) ∀n ∈ N mit n ≥ 3 gilt: ∑i=1(i − 1)(n − i) = (n ueber 3)

kann jemand bitte helfen

---

@lorans: b) bitte separat einstellen, falls du bei den ähnlcihen Fragen nichts findest, das passt und auch Mathe-newbie nicht helfen kann.

---

Da inzwischen in den Kommentaren eine Antwort für b) vorhanden ist, habe ich b) in die Frage von Mathe_newbie20 integriert.

---

b) rein formal und nicht mit doppeltem Abzählen wohl hier https://www.mathelounge.de/580148/summenformeln-binomialkoeffizienten-kubikzahlen-quadratzahlen

---

wohl hier

Dazu müsstest du dann ja nur noch eben mal schnell erklären, warum Σ [k = 2 bis n-1] (k über 2)  das Gleiche ist wie  Σ [k = 2 bis n-1] (k-1)*(n-k) .

---

Coole Feststellung. Danke.

Answer 1

Schreib die Binomialkoeffizienten als Brüche mit Fakultäten.

Auf der linken Seite kürzt du k!, auf der rechten Seite (n-l)!

Auf beiden Seiten steht dann der gleiche Term.

Comments

Hmmh! ... das ist korrekt, aber hat IMHO nichts mit 'doppeltem Abzählen' zu tun. Was ist die Menge \(S\), von der hier die Rede ist?

Prinzip des doppelten Abzählens: Angenommen wir haben zwei endliche Mengen \( R \) und \(C\) gegeben und eine Teilmenge \( S \) des Kreuzprodukts \( R \times C . \) Wann immer \( (p, q) \in S \) ist, dann sagen wir, dass \( p \) und \( q \) inzident sind. Wenn wir mit \( r_{p} \) die Anzahl der Elemente bezeichnen, die zu \( p \in R \) inzident sind, und \( c_{q} \) die Anzahl der Elemente, die zu \( q \in C \) inzident sind, so gilt \[ \sum \limits_{p \in R} r_{p}=|S|=\sum \limits_{q \in C} c_{q} \]

---

Hallo Werner,

meine Antwort ist auch nur als Notlösung gedacht, da ich "doppeltes Abzählen" noch nicht gehört hatte. Hast du denn eine Lösungsidee?

---

Hast du denn eine Lösungsidee?

Das Dokument hinter dem Link ist recht verständlich. Ich habe auch schon eine 'unscharfe' Idee, das auf dieses Problem zu übertragen. Leider habe ich erst morgen Abend mehr Zeit für sowas ...

---

Die Lösung für Teil a. habe ich hier vor einiger Zeit mal geschrieben.

Für die Lösung zu Teil b. kann man sich leicht ein Szenario ausdenken, nach welcher Vorgehensweise 3 Leute aus n Leuten so ausgewählt werden können, dass die Anzahl der möglichen Auswahlen mit der Summe auf der linken Seite berechnet werden kann.