| Autor |
Beitrag |
    
Robert
| | Veröffentlicht am Montag, den 13. August, 2001 - 16:00: | 
|
Hi,
kann mir jemand von euch zeigen, wie man den polynomischen Lehrsatz durch vollständige Induktion beweist?
Der Satz lautet folgendermaßen:
(x1 + x2 +...+xn)n = S k1+k2+...+kn = n n!/k1!*k2!*...*kn!*x1k1*x2k2*...*xnkn
Dabei wird über alle Tupel (k1,k2,...,kn) natürlicher Zahlen summiert, für die k1 + k2 +...+ kn = n.
Bitte helft mir!
Danke
Robert |
Robert
| | Veröffentlicht am Dienstag, den 14. August, 2001 - 15:24: |
|
Hallo? Ist niemand an der Aufgabe interessiert?
Ist sie zu schwer oder vielleicht zu leicht?
Ich wäre über eine Antwort erfreut.
Robert |
mrsmith
| | Veröffentlicht am Dienstag, den 14. August, 2001 - 17:11: |
|
hi Robert,
oder vielleicht zu standardmaessig...
anmerkung: die dimension der tupel x_1,...x_m sollte von 1 bis m gewaehlt werden,
um die sache uebersichtlicher zu gestalten.
dann sieht die linke seite z.b. so aus
(x_1 + x_2 + ... +x_m)^n.
wie man nun sofort sieht, reicht es, den satz zunaechst fuer m=2 zu zeigen. eine
zweite induktion ueber m wird ihn dann fuer beliebige m gueltig machen.
die induktion ueber n fuer den fall m=2 aber sieht so standardmaessig aus, dass du
sie bestimmt spaetestens im zweiten lehrbuch er analysis findest. wenn nicht, dann
waere das allerdings doch ein zeichen, dass die aufgabe zu einfach war.
viele gruesse mrsmith |
Matroid (Matroid)
| | Veröffentlicht am Dienstag, den 14. August, 2001 - 21:12: |
|
Hi Robert,
in http://www.univie.ac.at/future.media/mo/materialien/matroid/files/vi/vi.html#9c geht es um Binomialkoeffizienten. Da findest Du vielleicht den Tipp, den Du brauchst.
Gruß
Matroid |
H.R.Moser,megamath.
| | Veröffentlicht am Mittwoch, den 15. August, 2001 - 09:31: |
|
Hi Robert,
Ein Induktionsbeweis des polynomischen Lehrsatzes ist keineswegs
trivial. Nötig ist eine sorgfältige Planung und Vorbereitung.
Als bekannt werde der Induktionsbeweis des binomischen Lehrsatzes
vorausgesetzt. ( siehe z.B. bei Matroid nach ! ) .
Wenn wir den Binomialkoeffizient n über k ("n tief k") als
Fakultätenbruch schreiben, lautet der binomische Satz:
( x + y ) ^ n = sum [ n ! / { j ! * ( n - j ) ! } * x ^ j * y ^ (n-k) ]..............(1)
Summationsindex j = 0, ... ,n ;
indem wir
j = a , n - j = b mit a + b = n setzen, kommt:
( x + y ) ^ n = sum [ n ! / { a! * b! } * x ^ a * y ^ b ]................................(2)
Die Summe erstreckt sich auf alle Zerlegungen
a + b = n , wobei a und b nicht negative ganze Zahlen sind.
Der polynomische Lehrsatz für m Summanden
x, y , z .... lautet entsprechend:
(x + y + z + ....) ^ n = sum [ n ! / {a! * b! * c!...} * x ^ a * y^ b *z ^ c...]...(3)
Auch hier erstreckt sich die Summation auf alle Zerlegungen
a + b + c + .... = n
mit m Summanden aus nicht negativen ganze Zahlen..
Skizze eines Induktionsbeweises der Formel (3) nach m
(Schluss von m-1 auf m) .
1) Verankerung
Die Formel gilt für m = 2: es entsteht der binomische Lehrsatz.
2) Vererbung
Sei u = y + z +... (Summe mit m - 1 Summanden)
Es gilt nach (2) :
( x + u ) ^ n = sum [n ! / {a!*k!} * x ^ a * u ^ k .................................(4)
Summation über alle a + k = n .
Nach der Induktionsvoraussetzung gilt die Formel (3) für (m - 1)
also:
u ^ k = (y + z +....) ^ k = sum [ k ! / {b ! * c ! *...} * y ^ b * z ^ c...]...(5)
Summation über alle b + c + ... = k
Aus (4 ) und (5 ) folgt Formel (3) qed.
Mit freundlichen Grüßen
H.R.Moser,megamath. |
H.R.Moser,megamath.
| | Veröffentlicht am Mittwoch, den 15. August, 2001 - 17:41: |
|
Hi Robert,
Wir wollen es nicht nur bei einem Beweis des polynomischen Satzes
bewenden lassen ; nützlich ist auch der Gebrauch des Satzes.
Vor allen Dingen interessiert uns die Frage, wieviele Summanden
in der Entwicklung auftreten.
Die Antwort lautet:
Für m als Anzahl der Summanden x , y , ... , deren Summe mit n
potenziert wird, gilt für die Anzahl der Summanden P die Formel.
P ( m , n ) = ( n + m -1 )! / [ n ! * (m - 1) ! ]..................................(I)
Für den binomischen Lehrsatz erhält man mit m = 2 :
P( 2 , n ) = n + 1 , wie es sein muss
.
Beispiel.
Wir behandeln den Spezialfall m = 3 , n = 4.
Es handelt sich somit um die Entwicklung von T = (x +y + z) ^ 4 .
Wie wir beim Induktionsbeweis gezeigt haben, ist vor allen Dingen
die Gleichung
a + b + c = 4 in nicht negativen ganzen Zahlen a , b , c zu lösen
Welches ist die Anzahl P (3 , 4 ) dieser Lösungen ?
Zur Ermittlung dieser Zahl gehen wir mit einer bekannten Methode der Kombinatorik so vor:
Wir setzen eine Sequenz von n = 4 Einsen und (m-1) = 2 Querstrichen
als Trennungszeichen (letztere können auch nebeneinander
oder am Anfang und Ende stehen ).
als Beispiele dienen die Sequenzen
1 1 / 1 / 1 für die Lösung 2 + 1 + 1 = 4 , also a = 2 , b = 1 c = 1.
1 / / 1 1 1 für die Lösung 1 + 0 + 3 = 4, also a = 1 , b = 0 , c = 3
/ 1 / 1 1 1 für die Lösung 0 + 1 + 3 = 4, also a = 0 , b = 1 , c = 3.
/ / 1 1 1 1 für die Lösung 0 + 0 + 4 =4, also a = 0 , b = 0 , c = 4
Die Anzahl P der Lösungen ist gleich der Anzahl Permutationen mit Wiederholungen von 4 Zeichen 1 und 2 Zeichen / , somit:
P = 6 ! / { 4! * 2! } = 15.
Explizit lauten die Lösungen (Reihenfolge a,b.c) :
0 0 4 ....1 0 3 ....2 0 2 ....3 0 1....4 0 0
0 1 3 ....1 3 0 ....2 2 0 ....3 1 0
0 2 2 ....1 1 2 ....2 1 1
0 3 1 ....1 2 1
0 4 0
Für die Entwicklung
(x+y+z+w) ^ 15 mit m = 4 , n = 15 zum Beispiel kommt
P(4,15) = 816 , wie man leicht nachrechnet.
usw.
Mit freundlichen Grüßen
H.R.Moser,megamath. |
|
