Die Mathe-Redaktion - 29.06.2017 04:08 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 436 Gäste und 2 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Kombinatorische Herleitung von Potenzsummen
Freigegeben von matroid am Fr. 31. Juli 2015 19:59:34
Verfasst von Martin_Infinite -   1421 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Kombinatorische Herleitung von Potenzsummen

Wir geben eine einfache kombinatorische Herleitung einer expliziten Formel für die Potenzsumme <math>\displaystyle\sum_{k=0}^{n} k^d</math> als ein Polynom in <math>n</math>, wobei der Exponent <math>d \geq 0</math> fest ist. Dabei werden uns Binomialkoeffizienten und Stirling-Zahlen helfen.

Binomialkoeffizienten

Für <math>n,k \in \mathds{N} = \{0,1,2,\dotsc\}</math> sei der Binomialkoeffizient <math>\displaystyle\binom{n}{k}</math> die Anzahl der <math>k</math>-elementigen Teilmengen einer <math>n</math>-elementigen Menge. Für <math>k>n</math> ist also <math>\displaystyle\binom{n}{k}=0</math>. Für <math>k \leq n</math> gilt

<math>\displaystyle\binom{n}{k} = \frac{n \cdot (n-1) \cdot \dotsc \cdot (n-k+1)}{k!},</math>

weil hierbei nacheinander <math>k</math> Elemente aus einer <math>n</math>-elementigen Menge gewählt werden und anschließend die Anzahl der Permutationen <math>k!</math> herausgeteilt wird.

Für festes <math>d \in \mathds{N}</math>  gilt

<math>\displaystyle\sum_{k=0}^{n} \binom{k}{d} = \binom{n+1}{d+1}.</math>

Denn um eine <math>d+1</math>-elementige Menge aus <math>\{1,\dotsc,n+1\}</math> auszuwählen, können wir zunächst einmal das größte Element auswählen, etwa <math>k+1</math> für <math>k \in \{0,\dotsc,n\}</math>, und dann den Rest auswählen, welcher eine <math>d</math>-elementige Teilmenge von <math>\{1,\dotsc,k\}</math> ist.

Surjektive Abbildungen

Nun möchten wir aber nicht Binomialkoeffizienten, sondern die Potenzen <math>k^d</math> aufsummieren. Es ist <math>k^d</math> die Anzahl der Abbildungen einer <math>d</math>-elementigen Menge in eine <math>k</math>-elementige Menge. Jede solche Abbildung ist bestimmt durch ihr Bild (welches etwa <math>i</math> Elemente hat) und eine surjektive Abbildung auf dieses Bild. Daraus folgt

<math>\displaystyle k^d = \sum_{i=0}^{d} \binom{k}{i} \cdot T(d,i),</math>

wobei <math>T(d,i)</math> die Anzahl der surjektiven Abbildungen einer <math>d</math>-elementigen Menge auf eine <math>i</math>-elementige Menge bezeichnet. Für <math>d < i</math> ist also <math>T(d,i)=0</math>. Zusammen mit der ersten Summe erhalten wir daher:

<math>\displaystyle \sum_{k=0}^{n} k^d = \sum_{k=0}^{n} \sum_{i=0}^{d} \binom{k}{i} \cdot T(d,i) = \sum_{i=0}^{d} \sum_{k=0}^{n} \binom{k}{i} \cdot T(d,i) = \sum_{i=0}^{d} \binom{n+1}{i+1} \cdot T(d,i).</math>

Wir haben also die Potenzsumme als ein Polynom in <math>n</math> dargestellt. Um das noch konkreter zu machen, müssen wir nur noch die <math>T(d,i)</math> ausrechnen.

Stirling-Zahlen

Sind <math>X,Y</math> zwei Mengen, so bestimmt eine surjektive Abbildung <math>f : X \to Y</math> für jedes <math>y \in Y</math> eine nichtleere Teilmenge <math>f^*(\{y\}) \subseteq X</math>, die Faser von <math>y</math>. Diese Fasern sind paarweise disjunkt und überdecken <math>X</math>, ergeben also eine Partition von <math>X</math>. Umgekehrt liefert jede durch <math>Y</math> indizierte Partition von <math>X</math> eine surjektive Abbildung <math>f : X \to Y</math>. Daraus folgt, dass <math>T(d,i)</math> die Anzahl der geordneten Partitionen einer <math>d</math>-elementigen Menge in <math>i</math> Mengen ist.

Wenn <math>S(d,i)</math> die Anzahl der ungeordneten Partitionen einer <math>d</math>-elementigen Menge in <math>i</math> Mengen ist, wo also die Reihenfolge der Mengen keine Rolle spielt, so gilt folglich

<math>T(d,i) = i! \cdot S(d,i).</math>

Daraus folgt nun unsere allgemeine Formel für Potenzsummen:

<math>\displaystyle \sum_{k=0}^{n} k^d = \sum_{i=0}^{d} \binom{n+1}{i+1} \cdot i! \cdot  S(d,i) = \sum_{i=0}^{d} \frac{(n+1) \cdot  n \cdot  \dotsc \cdot  (n-i+1)}{i+1} \cdot S(d,i).</math>
 
Man nennt <math>S(d,i)</math> die Stirling-Zahl zweiter Art. (Dies ist auch die Anzahl der Äquivalenzrelationen auf einer <math>d</math>-elementigen Menge mit <math>i</math> Äquivalenzklassen.) Es gilt offenbar <math>S(0,0)=1</math>, <math>S(d,0)=S(0,d)=0</math> für <math>d>0</math>. Es besteht die Rekursionsformel

<math>S(d+1,i+1)=S(d,i)+(i+1)\cdot S(d,i+1),</math>

denn wenn man die Menge <math>\{1,\dotsc,d+1\}</math> in <math>i+1</math> Mengen partitioniert, gibt es zwei Möglichkeiten: Entweder enthält die Menge, die <math>d+1</math> enthält, lediglich <math>d+1</math>. Dann ist der Rest eine Partition von <math>\{1,\dotsc,d\}</math> in <math>i</math> Mengen. Oder aber, die besagte Menge enthält nicht nur <math>d+1</math>. Dann entfernen wir <math>d+1</math> aus dieser Menge und verbleiben mit einer Partition von <math>\{1,\dotsc,d\}</math> in <math>i+1</math> Mengen, sowie mit der Information, in welcher der <math>i+1</math> Mengen <math>d+1</math> ursprünglich war.

Wir können damit die folgende Tabelle einiger Stirling-Zahlen zweiter Art erstellen, wobei in der Zeile <math>d \in \{0,1,\dotsc,10\}</math> die Werte <math>S(d,0),\dotsc,S(d,d)</math> stehen.

<math>\begin{tabular}{ccccccccccc}
1 \\0& 1 \\0& 1& 1 \\0& 1& 3& 1 \\0& 1& 7& 6& 1 \\0& 1& 15& 25& 10& 1 \\0& 1& 31& 90& 65& 15& 1 \\0& 1& 63& 301& 350& 140& 21& 1 \\0& 1& 127& 966& 1701& 1050& 266& 28& 1 \\0& 1& 255& 3025& 7770& 6951& 2646& 462& 36& 1 \\0& 1& 511& 9330& 34105& 42525& 22827& 5880& 750& 45& 1 \end{tabular}</math>

Eine weitere Rekursionsformel ist

<math>\displaystyle S(d,i+1) = \sum_{p=0}^{d-1} \binom{d}{p} S(p,i).</math>

Das lässt sich damit erklären, dass eine Partition einer <math>d</math>-elementigen Menge in <math>i+1</math> Mengen dasselbe ist wie eine Partition einer ausgewählten echten Teilmenge einer <math>d</math>-elementigen Menge in <math>i</math> Mengen.

Beispiele

Mit unserer allgemeinen Formel für Potenzsummen berechnen wir nun konkrete Potenzsummen; die Stirling-Zahlen sind dabei fett markiert:
 
<math>\displaystyle \sum_{k=0}^{n} k^0 = \frac{n+1}{1} \cdot \mathbf{1} = n+1.</math>

<math>\displaystyle \sum_{k=0}^{n} k^1 = \frac{(n+1)n}{2} \cdot \mathbf{1} = \frac{(n+1)n}{2}.</math>

<math>\displaystyle \sum_{k=0}^{n} k^2 = \frac{(n+1)n}{2} \cdot \mathbf{1} + \frac{(n+1)n(n-1)}{3} \cdot \mathbf{1} = \frac{n(n+1)(2n+1)}{6}.</math>

<math>\displaystyle \sum_{k=0}^{n} k^3 = \frac{(n+1)n}{2} \cdot \mathbf{1} + \frac{(n+1)n(n-1)}{3} \cdot \mathbf{3} + \frac{(n+1)n(n-1)(n-2)}{4} \cdot \mathbf{1} \\~~~~~~~~~ = \frac{n^2 (n+1)^2}{4}.</math>

<math>\displaystyle \sum_{k=0}^{n} k^4 = \frac{(n+1)n}{2} \cdot \mathbf{1} + \frac{(n+1)n(n-1)}{3} \cdot \mathbf{7} + \frac{(n+1)n(n-1)(n-2)}{4} \cdot \mathbf{6} \\ ~~~~~~~~~~~~\, + \frac{(n+1)n(n-1)(n-2)(n-3)}{5} \cdot \mathbf{1}\\
 ~~~~~~~~~ =  \frac{n(n+1)(6n^3 + 9n^2 + n - 1)}{30}.</math>

<math>\displaystyle \sum_{k=0}^{n} k^5 = \frac{(n+1)n}{2} \cdot \mathbf{1} + \frac{(n+1)n(n-1)}{3} \cdot \mathbf{15} + \frac{(n+1)n(n-1)(n-2)}{4} \cdot \mathbf{25} \\ ~~~~~~~~~~~~ + \frac{(n+1)n(n-1)(n-2)(n-3)}{5} \cdot \mathbf{10} + \frac{(n+1)n(n-1)(n-2)(n-3)(n-4)}{6} \cdot \mathbf{1} \\ ~~~~~~~~~ =  \frac{n^2 (n + 1)^2 (2 n^2 + 2 n - 1)}{12}.</math>

Das schrittweise Zusammenfassen der Polynome habe ich hierbei weggelassen; dies ist reine Fleißarbeit.

Schluss

Schließlich sei noch bemerkt, dass es viele weitere Darstellungs- wie Herleitungsmöglichkeiten für die Potenzsummen gibt, die auch hier auf dem Matheplaneten besprochen wurden. Ich möchte darauf an dieser Stelle aber nicht weiter eingehen. Stattdessen möchte ich diesen Artikel mit einem kombinatorischen Beweis für die Beobachtung

<math>\displaystyle \sum_{k=0}^{n} k^3 = \Bigl(\sum_{k=0}^{n} k\Bigr)^2</math>

abschließen:

<math>\begin{tikzpicture}[scale=0.4]
\draw[step=1.0,black!40,thin] (0,0) grid (15,15);
\draw [thick] (0,0) to (15,0) to (15,15) to (0,15) to (0,0);
\draw [thick] (0,10) to (10,10) to (10,0);
\draw [thick] (0,6) to (6,6) to (6,0);
\draw [thick] (0,3) to (3,3) to (3,0);
\draw [thick] (0,1) to (1,1) to (1,0);
\draw [thick] (3,1) to (1,1) to (1,3);
\draw [thick] (6,3) to (3,3) to (3,6);
\draw [thick] (2,6) to (2,10);
\draw [thick] (6,2) to (10,2);
\draw [thick] (6,10) to (6,6) to (10,6);
\draw [thick] (5,15) to (5,10);
\draw [thick] (15,5) to (10,5);
\draw [thick] (10,15) to (10,10) to (15,10);
\end{tikzpicture}</math>

Beweis durch langes Angucken. Viele weitere Beweise dieses Typs finden sich in dem Buch "Proofs without words" von Roger B. Nelson.

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 1421
 
Aufrufstatistik des Artikels
Insgesamt 7 externe Besuche in 2017.06 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com114.3%14.3 %
http://google.de571.4%71.4 %
http://www.sm.de114.3%14.3 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.06.27 23:47https://www.google.de/

[Seitenanfang]

" Mathematik: Kombinatorische Herleitung von Potenzsummen" | 13 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: Kombinatorische Herleitung von Potenzsummen
von PhysikRabe am Fr. 31. Juli 2015 20:53:15


Das Quadrat ganz unten könnte man also zugleich als "q.e.d."-Halmos-Quadrat dieses kombinatorischen Beweises ansehen?  razz

Also ich habe mit Kombinatorik nichts am Hut, aber mir hat dein Artikel sehr gefallen! Gut verständlich und angenehm zu lesen - und außerdem eine Abwechslung zu den abstrakteren Themen, über die du normalerweise schreibst!

Darf man auf weitere Artikel hoffen?

Viele Grüße,
PhysikRabe

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von ZetaX am Fr. 31. Juli 2015 21:35:50


Hier gibt's das letzte Bild übrigens in animiert: artofproblemsolving.com/articles/proof-without-words (rehcts unten).

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von Ex_Mitglied_40174 am Fr. 31. Juli 2015 23:30:08


Das Quadrat ganz unten ist sehr schön
als Hintergrundbild geeignet.

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von weird am Sa. 01. August 2015 09:10:06


Ich kann mich dem Lob von PhysikRabe oben nur voll und ganz anschließen. Hätte man mich zu diesem Thema befragt, so hätte ich wohl genau den gleichen Weg eingeschlagen, denn sowohl das Pascalsche Dreieck und dessen Eigenschaften, als auch Stirlingzahlen sind ja sowas wie ein Steckenpferd von mir.

Das Einzige was mir vielleicht fehlt, wenn man jetzt unbedingt Kritik üben will, ist ein kurzer Verweis auf andere nichtkombinatorische Beweismöglichkeiten, der vielleicht ganz gut zur Abrundung in die Einleitung des ansonsten sehr gelungenen Artikels gepasst hätte.

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von Ex_Mitglied_40174 am Sa. 01. August 2015 10:39:19


Das geht doch auch mit Bernoulli-Zahlen.

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von Martin_Infinite am Sa. 01. August 2015 10:58:33


Ich bin mit Absicht nicht auf die anderen wohlbekannten Darstellungsmöglichkeiten eingegangen. Siehe dazu:

Wikipedia: Faulhabers Formel
Matheplanet: Potenzsummen
Matheplanet: Endliche Summen
Notizbuch: Potenzsummen

Ich finde die Herleitung über Binomialkoeffizienten, die mir gestern übrigens spontan eingefallen ist, bisher am elegantesten. Der Vorteil an Faulhabers Formel ist aber natürlich, dass man die Koeffizienten des Polynoms direkt hinschreiben kann, nachdem man die Bernoulli-Zahlen <math>B_d</math> berechnet hat. Es gibt übrigens den Zusammenhang <math>B_d = \sum_{i=0}^{d} (-1)^i \frac{i!}{i+1} S(d,i)</math>.

@PhysikRabe: Es ist schon seit einiger Zeit ein Artikel über kombinatorische Spezies mit Anwendungen in Arbeit, aber ich weiß nicht, wann er fertig wird.

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von shadowking am Mo. 03. August 2015 02:57:41


Wenn ich schnell mal eine Potenzsumme <math>\sum_{k=0}^N k^m</math> benötige (und mein Rechner gerade läuft), dann entwickle ich die Funktion <math>f_N\,:=\left{\begin{cases} \,\frac{\mathrm{e}^{(N+1)\cdot x}-1}{\mathrm{e}^x-1} &\: x\neq 0 \\ N+1 &\: x=0 \end{cases}</math> in eine MacLaurin-Reihe (also eine Taylorreihe um x=0). Deren m-ter Koeffizient ist gerade <math>\frac{1}{m!}\sum_{k=0}^N k^m</math>.

Das kann man unter Ausnutzung der geometrischen Summe, <math>\sum_{k=0}^N u^k\,=\,\frac{u^{N+1}-1}{u-1}</math>, schnell zeigen:

<math>\displaystyle
\begin{aligned}
\sum_{k=0}^N k^m \,&=\,\sum_{k=0}^N \frac{\mathrm{d}^m}{\mathrm{d}x^m} \; \mathrm{e}^{kx}\mid_{x=0} \\
&=\,\frac{\mathrm{d}^m}{\mathrm{d}x^m} \sum_{k=0}^N \mathrm{e}^{kx} \mid_{x=0}\\
&=\,\frac{\mathrm{d}^m}{\mathrm{d}x^m} \; \frac{\mathrm{e}^{(N+1)\cdot x}-1}{\mathrm{e}^x-1}\mid_{x=0},
\end{aligned}</math>
 
also ist

<math>\displaystyle
\frac{\mathrm{e}^{(N+1)\cdot x}-1}{\mathrm{e}^x-1}\,=\,\sum_{m=0}^{\infty} \frac{1}{m!}\cdot \left(\sum_{k=0}^N k^m\right)\cdot x^m</math>.

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von Martin_Infinite am Mo. 03. August 2015 09:34:49


@shadowking: Danke! Das ist schön. Als Kombinatoriker fragt man sich dann natürlich, ob die Zahlen <math>a_m:=\sum_{k=0}^{N} k^m</math> (mit festem <math>N</math> hier) eine kombinatorische Bedeutung haben, mit der man dann die exponentielle erzeugende Funktion, die du angegeben hast, direkt durch die allgemeine Maschinerie kombinatorischer Spezies hinschreiben kann. Mir fällt spontan nichts ein, aber vielleicht weiß es ja jemand anderes.

Nachtrag: Die Identität lässt sich auch ohne Ableitungen einsehen:

<math>\displaystyle\sum_{m=0}^{\infty} \sum_{k=0}^{N} k^m \cdot \frac{x^m}{m!} = \sum_{k=0}^{N} \sum_{m=0}^{\infty} \frac{(kx)^m}{m!} = \sum_{k=0}^{N} e^{kx} = \frac{(e^x)^{N+1}-1}{e^x-1}.</math>

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von endy am Mo. 03. August 2015 21:33:58


Schöner Artikel.

@shadowking:

Wenn ich schnell mal eine Potenzsumme benötige (und mein Rechner gerade läuft), dann gebe ich die Potenzsumme einfach in den Rechner ein:
mathematica
(* In *)
Clear @a
a[m_, n_] := Sum[j^m, {j, 1, n}]
a[1, n]
a[2, n]
(* Out *)
1/2 n (1 + n)
1/6 n (1 + n) (1 + 2 n)

Man braucht also einem CAS nicht extra die Potenzsummenformeln beizubringen,obwohl dies natürlich auch möglich ist.

Deine Methode ist aber nicht wirklich effektiv.

Gruß endy






 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von sbechtel am Di. 04. August 2015 11:58:18


@endy: vielleicht nicht effizient, aber schön. Das überzeugt mich razz

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von safrazap am Mo. 23. November 2015 01:28:41


Hallo Martin,
mir hat dein Artikel sehr gut gefallen.
Er ist sehr verständlich geschrieben und ich denke alles verstanden zu haben!
Einiges war mir so noch nicht bewusst - besten Dank dafür.

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von Martin_Infinite am Mo. 23. November 2015 14:18:18


@safrazap: Danke für deinen Kommentar! smile
Man kann tatsächlich sehr viele Identitäten kombinatorisch beweisen. Eine Liste von einfachen, schweren, bishin zu bisher (mit Kombinatorik) ungelösten Identitäten sammelt R. P. Stanley in der Arbeit Bijective Proof Problems.

 [Bearbeiten]

Re: Kombinatorische Herleitung von Potenzsummen
von safrazap am Mo. 23. November 2015 22:58:00


Hallo Martin,

vielen Dank für diesen Link!

Ich bin mir sicher, dass ich mir von dieser enormen Fülle an Beispielen immer wieder etwas herauspicken werde. Mir gefallen die kombinatorischen  Begründungen sehr, dennoch würde ich mich eher als Induktions-Fan bezeichnen...

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]