Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten |
11.05.2010, 20:06 | rad238 | Auf diesen Beitrag antworten » | ||
Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten ich habe wieder eine Frage: Wir zerlegen eine natürliche Zahl in Summanden , mit : Jeder Summand kann auch mehrfach vorkommen. Es sei die Anzahl der Möglichkeiten, in die angegebenen Summanden zu zerlegen. Dann ist wobei die Lösung der "charakteristischen Gleichung" ist. Ich verstehe nicht, was die Lösung eines Polynoms mit der Anzahl von möglichen Summenzerlegungen zu tun hat. Weiß das jemand? Besten Dank im Voraus! PS das Problem kommt aus der Herleitung der Informationsentropie für diskrete, störungsfreie Kanäle in "A Mathematical Theoy of Communication" von Shannon. |
||||
11.05.2010, 20:39 | AD | Auf diesen Beitrag antworten » | ||
Na wenn das nicht ein Fall für Mystic und seine erzeugenden Funktionen ist... |
||||
11.05.2010, 21:35 | akechi90 | Auf diesen Beitrag antworten » | ||
Du kannst die Anzahl interpretieren als , wobei die Anzahl der Zerlegungen von in der besagten Summanden bezeichnet. Du überzeugst dich leicht davon, dass der Koeffizient von in dem Polynom ist. Also sind die Koeffizienten von gerade die . Nun hast du . Setze eine Partialbruchzerlegung an und forme alles in geometrische Reihen um. Dadurch bekommst du eine asymptotische Formel. Gruß, Carsten |
||||
11.05.2010, 23:33 | rad238 | Auf diesen Beitrag antworten » | ||
RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten Hallo Carsten, vielen Dank! Ich glaube, jetzt habe ich es verstanden... Der erste Schritt ist kompliziert... Ich habe das erst einmal für 2 Summanden (2 und 4) ausprobiert. Die Teile müssen ja in der Summe gleich sein, und in der binomischen Formel ist das zufällig der Exponent, wohingegen der Koeffizient die zugehörige Anzahl von möglichen Anordnungen angibt. Für mehr als 2 Summanden scheint es auch zu gehen... Dann geht es weiter mit mit Somit ist Ich denke, das Polynom hat nur eine positive, reelle Nullstelle. Und die ist . Dann kann ich den Grenzwert ausrechnen: Andreas edit: Klammerzeichen in der 1. Gleichung korrigiert |
||||
11.05.2010, 23:36 | AD | Auf diesen Beitrag antworten » | ||
RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten Anmerkung: Im Nenner fehlt eine Klammer (auch schon bei akechi90), die durchaus wichtig ist, wohl nur ein Versehen. Richtig ist also . |
||||
11.05.2010, 23:40 | akechi90 | Auf diesen Beitrag antworten » | ||
RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten
Dankeschön, der Fehler wird behoben |
||||
Anzeige | ||||
|
||||
12.05.2010, 09:31 | Mystic | Auf diesen Beitrag antworten » | ||
RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten
Ich sehe zwar auch, dass es asymptotisch gesehen genau um diese Nullstelle geht, aber bei dir fehlt doch jede Begründung dafür...Imho sieht man das doch erst, nachdem man sämtliche Nullstellen (inklusive der komplexen!) näherungsweise berechnet hat, oder habe ich da was übersehen? |
||||
12.05.2010, 10:20 | AD | Auf diesen Beitrag antworten » | ||
Sehe ich auch so: Zunächst mal muss man die Formulierung
im Eröffhnungsbeitrag präzisieren: soll sicher die einzige positive reelle Lösung der charakteristischen Gleichung sein! Nachzuweisen ist jetzt für alle anderen (reellen und auch komplexen) Lösungen dieser Gleichung, dass sie betragsmäßig größer als sind. Kann schon sein, dass man das ohne konkretes Ausrechnen dieser Nullstellen irgenwie sieht - mir fehlt heute leider auch dieser "Blick". |
||||
12.05.2010, 19:06 | akechi90 | Auf diesen Beitrag antworten » | ||
Dass die anderen Nullstellen zumindest betragsweise sein müssen, sieht man wohl recht schnell mithilfe der Dreiecksungleichung ein. Wahrscheinlich muss man das auch einfach mithilfe eines CAS nachweisen... Gruß, Carsten |
||||
12.05.2010, 19:09 | AD | Auf diesen Beitrag antworten » | ||
Ohne sie zu bestimmen, d.h. nur anhand der Koeffizienten? Wie geht das? |
||||
12.05.2010, 19:16 | akechi90 | Auf diesen Beitrag antworten » | ||
RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten Deine Gleichung lautet . Was passiert denn, wenn eine komplexe Zahl betragsweise kleiner ist als die einzige reelle Lösung (die darüberhinaus positiv ist)? Was sagt dann die Dreiecksungleichung? |
||||
12.05.2010, 19:32 | AD | Auf diesen Beitrag antworten » | ||
Danke! |
||||
12.05.2010, 20:09 | akechi90 | Auf diesen Beitrag antworten » | ||
Ich muss meinen vorigen Beitrag ergänzen und etwas korrigieren: Man kann sogar beweisen, dass alle anderen Lösungen der Gleichung betragsweise größer sein müssen als die (wegen Monotonie) eindeutig bestimmte positive Lösung der Gleichung. Es gibt auch negative Nullstellen, deshalb gibt es keine eindeutige reelle Lösung, nur eine eindeutige positive. Es gilt ja genau dann Gleichheit in der Dreiecksungleichung (im Komplexen), wenn die einzelnen Summanden sich lediglich um einen positiven Faktor unterscheiden. D.h. die einzige Lösung mit demselben Betrag wie , die darüberhinaus die besagte Gleichung erfüllt, muss selbst sein. Damit sind auch andere unangenehme Effekte ausgeschlossen, die beim Entwickeln der expliziten Formel auftreten können. |
||||
12.05.2010, 21:12 | AD | Auf diesen Beitrag antworten » | ||
Ja, ist schon klar. Diese Argumentation passt übrigens auf sämtliche algebraischen Gleichungen mit nichtnegativen reellen und negativem . |
||||
13.05.2010, 15:57 | rad238 | Auf diesen Beitrag antworten » | ||
Ja, die Begründung hatte ich aufgehoben. Vielen Dank für die underschöne Erklärung mit der Dreiecksungleichung! Dann schreibe ich das mal schön auf. sind die Lösungen von Weil die linke Seite der Gleichung für stetig, streng monoton von nach steigt, ist sie an genau einer Stelle =1. Also gibt es genau eine positive Lösung . Zudem gibt es 9 komplexe (und/oder) negative Lösungen Aus der Dreiecksungleichung für komplexe Zahlen folgt, dass alle anderen Lösungen betragsmäßig größer sind als . Ihr Kehrwert ist daher betragsmäßig kleiner. Der Summand wächst also bei schneller als alle anderen Summanden. Darum ist der Grenzwert Zur Dreiecksungleichung: Die Gleichung mit hat wg. der Monotonie genau eine pos. Lösung . Zudem gibt es komplexe (und/oder) negative Lösungen mit: mit folgt aus der Dreiecksungleichung und Das Gleicheitszeichen gilt, wenn Ein Beispiel: Dann ist , aber auch ist eine Lösung mit gleichem Betrag. Nur in dem speziellen Beispiel kann man das ausschließen, weil es nur ein gibt, welches die Gleichung erfüllen kann, z.B. mit und : Das ist dann also die eine pos. Lösung. Demnach ist das Argument mit der Dreiecksungleichung nur in diesem speziellen Fall gültig, oder? |
||||
13.05.2010, 20:36 | akechi90 | Auf diesen Beitrag antworten » | ||
Für Zerlegungen dieser Art ist das Argument allgemeingültig, d.h. du kannst sogar einen allgemeineren Satz beweisen, da die auftretenden Gleichungen stets von der Form sind - das Argument mit der Dreiecksungleichung zieht also so gut wie immer (sofern deine besagte Teilmenge nicht die 0 enthält). |
||||
13.05.2010, 21:48 | Mystic | Auf diesen Beitrag antworten » | ||
Sehe ich nicht so, aber vielleicht habe ich ja auch nur etwas mißverstanden... Wenn wir o.B.d.A voraussetzen, dass gilt so gilt das im Falle offenbar nicht mehr, wenn gleichzeitig erfüllt ist... @rad238 Mir war das vom Anfang an klar, dass es stimmt, dass für alle anderen Nullstellen des fraglichen Polynoms gilt (wenngleich ich das anders bewiesen und das einfache Argument mit der Dreiecksungleichung nicht sofort gesehen habe), aber mir ging es hauptsächlich darum, aufzuzeigen, dass da noch ein Stück Argumentation fehlt, was sich inzwischen ja auch bestätigt hat... |
||||
13.05.2010, 21:56 | AD | Auf diesen Beitrag antworten » | ||
Spielst du darauf an, dass in diesem Fall der durch den ersetzt werden muss, weil ja dann für alle nicht durch teilbaren Zahlen gilt? Da würde ich als Kriterium, um dass zu verhindern, aber eher das noch einschränkendere ausmachen, oder übersehe ich jetzt was? |
||||
13.05.2010, 22:02 | Mystic | Auf diesen Beitrag antworten » | ||
Ich weiß jetzt nicht genau, was du meinst, aber wenn es hier z.B. um die Gleichung gegangen wäre, dann hätte die doch zwei betragsgleiche reelle Lösungen mit kleinstmöglichem Betrag gehabt... Ich denke, die Aussage von akechi90 war aber, falls ich ihn richtig verstanden habe, dass es das unter seinen Voraussetzungen nicht gibt... |
||||
13.05.2010, 22:05 | AD | Auf diesen Beitrag antworten » | ||
Ich wollte schon vorschnell antworten: "Nein, ich meine etwas anderes." Bei tieferem Nachdenken hängen aber beide Dinge miteinander zusammen! |
||||
13.05.2010, 22:54 | Mystic | Auf diesen Beitrag antworten » | ||
Ja, das sehe ich inzwischen auch... Und ja, man muss sogar voraussetzen, da sonst der fragliche Grenzwert nicht existiert... Edit: Auch in meinem Beispiel oben hätte ich natürlich besser so argumentieren sollen, dass man unter der Voraussetzung zuerst die eindeutig bestimmte positive reelle Lösung von bestimmt und anschließend dann die d Lösungen von , welche alle betragsgleich und von minimalem Betrag sind... |
||||
14.05.2010, 20:49 | akechi90 | Auf diesen Beitrag antworten » | ||
Tatsache, man sollte tatsächlich die Teilerfremdheit der Zahlen mit einbeziehen, sonst läuft das nicht wie gewollt |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|