Quadratische Summenformel

Aufrufe: 520     Aktiv: 29.05.2020 um 08:29
0

 

Hallo Leute,

 

Ich möchte gerne eine Formel für die Anzahl der Elemente in der Menge \(\{(a,b,c) \in \{1,…,n+1\}^3|a<c,b<c\}\) mittels der Unterscheidung in folgende Fälle erstellen (durch das doppelte Abzählprinzip):

1. \(a=b\)

2. \(a<b\)

3. \(a>b\)

 

Für \(a=b\) habe ich mir die gaussche Summenformel \(\frac{n(n+1)}{2}\) hergeleitet. Da ich weiß, dass das Endergebnis die Summe der 3 Fälle \(\frac{(n^2+n)(2n+1)}{6}\) sein muss, weiß ich, dass das Ergebnis für die anderen beiden Fälle jeweils \(\frac{n^3-n}{6}\) ist.

Allerdings kann ich mir überhaupt nicht zusammenreimen, warum dem so ist.

Also wie ergibt sich diese Formel irgendwie logisch aus den gegebenen Kombinationsmöglichkeiten?

 

Vielen Dank!

 

Diese Frage melden
gefragt

Student, Punkte: 22

 
Musst du das durch das doppelte Abzählprinzip beweisen? Das scheint mir recht kompliziert.   ─   42 29.05.2020 um 00:58
ja.leider
und mit Fallunterscheidung. Also a=b, a kleiner b und umgekehrt
   ─   jh 29.05.2020 um 08:27
Kommentar schreiben
1 Antwort
0

Meine Lösungsidee wäre die Folgende:

Für ein festes \(c \ge 2\) definieren wir \( A_c = \{ (a,b,c) \vert a,b<c \} \). Die Abbildung \( f: A_c \rightarrow \{1, \dots, c-1\}^2, (a,b,c) \rightarrow (a,b) \) ist offensichtlich eine Bijektion. Also ist \( \vert A_c \vert = \vert \{1, \dots, c-1 \}^2 \vert = (c-1)^2 \). Außerdem ist \( \{ (a,b,c) \vert a,b < c \} = \cup_{c=2}^{n+1} A_c \) eine Partition. Und somit folgt \( \vert \{ (a,b,c) \vert a,b<c \} \vert = \sum_{c=2}^{n+1} \vert A_c \vert = \sum_{c=2}^{n+1} (c-1)^2 = \sum_{c=1}^n c^2 = \frac{(n^2+n)(2n+1)}{6} \).

Diese Antwort melden
geantwortet

Student, Punkte: 7.02K

 

Kommentar schreiben