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. |
|