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

Hallo,
ich habe wieder eine Frage:

Wir zerlegen eine natürliche Zahl $\begin{eqnarray*} T \end{eqnarray*}$ in Summanden $\begin{eqnarray*} x_i \end{eqnarray*}$ , mit

$\begin{eqnarray*} x_i \in \{ 2, 4, 5, 7, 8, 10 \} \end{eqnarray*}$ :

$\begin{eqnarray*} T = \sum\limits_i^{} {x_i } \end{eqnarray*}$

Jeder Summand kann auch mehrfach vorkommen.

Es sei $\begin{eqnarray*} N(T) \end{eqnarray*}$ die Anzahl der Möglichkeiten, $\begin{eqnarray*} T \end{eqnarray*}$ in die angegebenen Summanden zu zerlegen. Dann ist

$\begin{eqnarray*} \mathop {\lim }\limits_{T \to \infty } \frac{{\log \left( {N\left( T \right)} \right)}} {T} = \log \left( {\frac{1} {{\mu _0 }}} \right) \end{eqnarray*}$

wobei $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ die Lösung der "charakteristischen Gleichung"

$\begin{eqnarray*} 1 = \mu^2 + \mu^4 + \mu^5 + \mu^7 + \mu^8 + \mu^{10} \end{eqnarray*}$

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

Augenzwinkern

11.05.2010, 21:35

akechi90

Auf diesen Beitrag antworten »

Du kannst die Anzahl $\begin{eqnarray*} N(T) \end{eqnarray*}$ interpretieren als $\begin{eqnarray*} N(T) = \sum_{j=0}^{\infty}~ N_j(T) \end{eqnarray*}$ , wobei $\begin{eqnarray*} N_j(T) \end{eqnarray*}$ die Anzahl der Zerlegungen von $\begin{eqnarray*} T \end{eqnarray*}$ in $\begin{eqnarray*} j \end{eqnarray*}$ der besagten Summanden bezeichnet.
Du überzeugst dich leicht davon, dass $\begin{eqnarray*} N_j(T) \end{eqnarray*}$ der Koeffizient von $\begin{eqnarray*} x^T \end{eqnarray*}$ in dem Polynom $\begin{eqnarray*} (x^2 + x^4 + x^5 + x^7 + x^8 + x^{10})^j \end{eqnarray*}$ ist. Also sind die Koeffizienten von $\begin{eqnarray*} F(x) = \sum_{j=0}^{\infty}~ (x^2 + x^4 + x^5 + x^7 + x^8 + x^{10})^j \end{eqnarray*}$ gerade die $\begin{eqnarray*} N(T) \end{eqnarray*}$ .

Nun hast du $\begin{eqnarray*} F(x) = \frac{1}{1-(x^2 + x^4 + x^5 + x^7 + x^8 + x^{10})} \end{eqnarray*}$ . 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 $\begin{eqnarray*} j \end{eqnarray*}$ Teile müssen ja in der Summe gleich $\begin{eqnarray*} T \end{eqnarray*}$ 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

$\begin{eqnarray*} \frac{1}{1-(x^2 + x^4 + x^5 + x^7 + x^8 + x^{10})} = \sum_{j=1}^{10}~ \frac{K_j}{x-\mu_j} \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{j=1}^{10}~ \frac{-K_j}{\mu_j} \cdot \frac{1}{1-\frac{x}{\mu_j}} \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{j=1}^{10}~ \frac{-K_j}{\mu_j} \sum_{k=0}^{\infty}~(\frac{x}{\mu_j})^k \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{k=0}^{\infty}~c_k \cdot x^k \end{eqnarray*}$

mit $\begin{eqnarray*} c_k = \sum_{j=1}^{10}~ \frac{-K_j}{\mu_j^{k+1}} \end{eqnarray*}$

Somit ist $\begin{eqnarray*} N(T) = \sum_{j=1}^{10}~ \frac{-K_j}{\mu_j^{T+1}} \end{eqnarray*}$

Ich denke, das Polynom hat nur eine positive, reelle Nullstelle. Und die ist $\begin{eqnarray*} \mu_x < 1 \end{eqnarray*}$ .
Dann kann ich den Grenzwert ausrechnen:

$\begin{eqnarray*} \mathop {\lim }\limits_{T \to \infty } \frac{{\log \left( {N\left( T \right)} \right)}} {T} = \mathop {\lim }\limits_{T \to \infty } \frac{\phi + \log \left( {\frac{1} {{\mu_x }}} \right) \cdot (T+1) }{T} = \log \left( \frac{1}{\mu_x} \right) \end{eqnarray*}$

smile

smile

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

$\begin{eqnarray*} \frac{1}{1-(x^2 + x^4 + x^5 + x^7 + x^8 + x^{10})} \end{eqnarray*}$ .

11.05.2010, 23:40

akechi90

Auf diesen Beitrag antworten »

RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten

Zitat:

Original von Arthur Dent
Anmerkung: Im Nenner fehlt eine Klammer (auch schon bei akechi90), die durchaus wichtig ist, wohl nur ein Versehen. Richtig ist also

$\begin{eqnarray*} \frac{1}{1-(x^2 + x^4 + x^5 + x^7 + x^8 + x^{10})} \end{eqnarray*}$ .

Dankeschön, der Fehler wird behoben smile

smile

Anzeige

12.05.2010, 09:31

Mystic

Auf diesen Beitrag antworten »

RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten

Zitat:

Original von rad238
Ich denke, das Polynom hat nur eine positive, reelle Nullstelle. Und die ist $\begin{eqnarray*} \mu_x < 1 \end{eqnarray*}$ .
Dann kann ich den Grenzwert ausrechnen:

$\begin{eqnarray*} \mathop {\lim }\limits_{T \to \infty } \frac{{\log \left( {N\left( T \right)} \right)}} {T} = \mathop {\lim }\limits_{T \to \infty } \frac{\phi + \log \left( {\frac{1} {{\mu_x }}} \right) \cdot (T+1) }{T} = \log \left( \frac{1}{\mu_x} \right) \end{eqnarray*}$

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? verwirrt

verwirrt

12.05.2010, 10:20

AD

Auf diesen Beitrag antworten »

Sehe ich auch so: Zunächst mal muss man die Formulierung

Zitat:

Original von rad238
wobei $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ die Lösung der "charakteristischen Gleichung"

$\begin{eqnarray*} 1 = \mu^2 + \mu^4 + \mu^5 + \mu^7 + \mu^8 + \mu^{10} \end{eqnarray*}$

ist.

im Eröffhnungsbeitrag präzisieren: $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ 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 $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ sind. Kann schon sein, dass man das ohne konkretes Ausrechnen dieser Nullstellen irgenwie sieht - mir fehlt heute leider auch dieser "Blick". Augenzwinkern

Augenzwinkern

12.05.2010, 19:06

akechi90

Auf diesen Beitrag antworten »

Dass die anderen Nullstellen zumindest betragsweise $\begin{eqnarray*} \geq \mu_0 \end{eqnarray*}$ 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 »

Zitat:

Original von akechi90
sieht man wohl recht schnell mithilfe der Dreiecksungleichung ein.

Ohne sie zu bestimmen, d.h. nur anhand der Koeffizienten? Wie geht das? verwirrt

verwirrt

12.05.2010, 19:16

akechi90

Auf diesen Beitrag antworten »

RE: Nullstelle eines Polynoms als Anzahl von Kombinationsmöglichkeiten
Deine Gleichung lautet $\begin{eqnarray*} 1 = \mu^2 + \mu^4 + \mu^5 + \mu^7 + \mu^8 + \mu^{10} \end{eqnarray*}$ . 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!

Idee!

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 $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ , die darüberhinaus die besagte Gleichung erfüllt, muss $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ 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

$\begin{eqnarray*} a_nx^n + \cdots + a_1x+a_0 = 0 \end{eqnarray*}$

mit nichtnegativen reellen $\begin{eqnarray*} a_1,\ldots,a_n \end{eqnarray*}$ und negativem $\begin{eqnarray*} a_0 \end{eqnarray*}$ .

13.05.2010, 15:57

rad238

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Ich sehe zwar auch, dass es asymptotisch gesehen genau um diese Nullstelle geht, aber bei dir fehlt doch jede Begründung dafür...

Ja, die Begründung hatte ich aufgehoben. Augenzwinkern

Augenzwinkern

Vielen Dank für die underschöne Erklärung mit der Dreiecksungleichung! Dann schreibe ich das mal schön auf.

$\begin{eqnarray*} \mathop {\lim }\limits_{T \to \infty } \frac{{\log \left( {N\left( T \right)} \right)}} {T} = \mathop {\lim }\limits_{T \to \infty } \frac{{\log \left( {\sum_{j=1}^{10}~ \frac{-K_j}{\mu_j^{T+1}}} \right)}} {T} \end{eqnarray*}$

$\begin{eqnarray*} \mu_j \end{eqnarray*}$ sind die Lösungen von

$\begin{eqnarray*} \mu^2 + \mu^4 + \mu^5 + \mu^7 + \mu^8 + \mu^{10} = 1 \end{eqnarray*}$

Weil die linke Seite der Gleichung für $\begin{eqnarray*} \mu \geq 0 \end{eqnarray*}$ stetig, streng monoton von $\begin{eqnarray*} 0 \end{eqnarray*}$ nach $\begin{eqnarray*} \infty \end{eqnarray*}$ steigt, ist sie an genau einer Stelle =1. Also gibt es genau eine positive Lösung $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ . Zudem gibt es 9 komplexe (und/oder) negative Lösungen $\begin{eqnarray*} \mu_j \end{eqnarray*}$

Aus der Dreiecksungleichung für komplexe Zahlen folgt, dass alle anderen Lösungen $\begin{eqnarray*} \mu_j \end{eqnarray*}$ betragsmäßig größer sind als $\begin{eqnarray*} \mu_0 \end{eqnarray*}$ . Ihr Kehrwert $\begin{eqnarray*} \frac{1}{\mu_j} \end{eqnarray*}$ ist daher betragsmäßig kleiner. Der Summand $\begin{eqnarray*} \frac{-K_0}{\mu_0^{T+1}} \end{eqnarray*}$ wächst also bei $\begin{eqnarray*} T \to \infty \end{eqnarray*}$ schneller als alle anderen Summanden. Darum ist der Grenzwert

$\begin{eqnarray*} \mathop {\lim }\limits_{T \to \infty } \frac{{\log \left( {N\left( T \right)} \right)}} {T} = \mathop {\lim }\limits_{T \to \infty } \frac{ \log \left({ -K_0 } \right) + (T+1) \cdot \log \left({ \frac{1}{ \mu_0 } }\right) } {T} = \log \left({ \frac{1}{\mu_0} }\right) \end{eqnarray*}$

Zur Dreiecksungleichung: Die Gleichung

$\begin{eqnarray*} x^a + x^b = p \end{eqnarray*}$

mit $\begin{eqnarray*} a, b, p>0 \end{eqnarray*}$ hat wg. der Monotonie genau eine pos. Lösung $\begin{eqnarray*} x_0 \end{eqnarray*}$ . Zudem gibt es $\begin{eqnarray*} \max(a,b)-1 \end{eqnarray*}$ komplexe (und/oder) negative Lösungen $\begin{eqnarray*} z_j \end{eqnarray*}$ mit:

$\begin{eqnarray*} z_j^a + z_j^b = p = x_0^a + x_0^b \end{eqnarray*}$

mit $\begin{eqnarray*} z_j = |z_j| \cdot e^{i \cdot \phi_j} \end{eqnarray*}$ folgt aus der Dreiecksungleichung

$\begin{eqnarray*} | z_j^a + z_j^b | \leq |z_j|^a + |z_j|^b \end{eqnarray*}$

und

$\begin{eqnarray*} |z_j|^a + |z_j|^b \geq x_0^a + x_0^b \end{eqnarray*}$

$\begin{eqnarray*} |z_j| \geq x_0 \end{eqnarray*}$

Das Gleicheitszeichen gilt, wenn

$\begin{eqnarray*} a \cdot \phi_j \mod 2 \pi = b \cdot \phi_j \mod 2 \pi \end{eqnarray*}$

Ein Beispiel:

$\begin{eqnarray*} x^4 + x^8 = 2 \end{eqnarray*}$

Dann ist $\begin{eqnarray*} x_0 = 1 \end{eqnarray*}$ , aber auch

$\begin{eqnarray*} z_j = i = 1 \cdot e^{i \cdot \phi_j} , \phi_j = \frac{\pi}{2} \end{eqnarray*}$

ist eine Lösung mit gleichem Betrag.

Nur in dem speziellen Beispiel

$\begin{eqnarray*} \mu^2 + \mu^4 + \mu^5 + \mu^7 + \mu^8 + \mu^{10} = 1 \end{eqnarray*}$

kann man das ausschließen, weil es nur ein $\begin{eqnarray*} \phi_j \end{eqnarray*}$ gibt, welches die Gleichung

$\begin{eqnarray*} a \cdot \phi_j \mod 2 \pi = b \cdot \phi_j \mod 2 \pi \end{eqnarray*}$

erfüllen kann, z.B. mit $\begin{eqnarray*} a = 4 \end{eqnarray*}$ und $\begin{eqnarray*} b = 5 \end{eqnarray*}$ :

$\begin{eqnarray*} 4 \cdot \phi_j \mod 2 \pi = 5 \cdot \phi_j \mod 2 \pi \end{eqnarray*}$
$\begin{eqnarray*} \phi_j = 0 + n \cdot 2 \pi \end{eqnarray*}$

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
$\begin{eqnarray*} \sum_{i=1}^{j}~x^{n_i} = 1 \end{eqnarray*}$
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 »

Zitat:

Original von akechi90
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
$\begin{eqnarray*} \sum_{i=1}^{j}~x^{n_i} = 1 \end{eqnarray*}$
sind - das Argument mit der Dreiecksungleichung zieht also so gut wie immer (sofern deine besagte Teilmenge nicht die 0 enthält).

Sehe ich nicht so, aber vielleicht habe ich ja auch nur etwas mißverstanden... Wenn wir o.B.d.A voraussetzen, dass gilt

$\begin{eqnarray*} n_1<n_2<\ldots<n_j \end{eqnarray*}$

so gilt das im Falle $\begin{eqnarray*} n_1 >1 \end{eqnarray*}$ offenbar nicht mehr, wenn gleichzeitig

$\begin{eqnarray*} n_1|n_k, \quad k=2,\ldots,j \end{eqnarray*}$

erfüllt ist...

@rad238

Mir war das vom Anfang an klar, dass es stimmt, dass für alle anderen Nullstellen $\begin{eqnarray*} \mu \end{eqnarray*}$ des fraglichen Polynoms gilt $\begin{eqnarray*} |\mu|> |\mu_0| \end{eqnarray*}$ (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... Augenzwinkern

Augenzwinkern

13.05.2010, 21:56

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Wenn wir o.B.d.A voraussetzen, dass gilt

$\begin{eqnarray*} n_1<n_2<\ldots<n_j \end{eqnarray*}$

so gilt das im Falle $\begin{eqnarray*} n_1 >1 \end{eqnarray*}$ offenbar nicht mehr, wenn gleichzeitig

$\begin{eqnarray*} n_1|n_k, \quad k=2,\ldots,j \end{eqnarray*}$

erfüllt ist...

Spielst du darauf an, dass in diesem Fall der $\begin{eqnarray*} \lim \end{eqnarray*}$ durch den $\begin{eqnarray*} \limsup \end{eqnarray*}$ ersetzt werden muss, weil ja dann $\begin{eqnarray*} N(T) = 0 \end{eqnarray*}$ für alle nicht durch $\begin{eqnarray*} n_1 \end{eqnarray*}$ teilbaren Zahlen gilt? verwirrt

verwirrt

Da würde ich als Kriterium, um dass zu verhindern, aber eher das noch einschränkendere

$\begin{eqnarray*} \operatorname{ggT}(n_1,n_2,\ldots,n_j)=1 \end{eqnarray*}$

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

$\begin{eqnarray*} x^2+x^4+x^6+x^8+x^{10} =1 \end{eqnarray*}$

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! Augenzwinkern

Augenzwinkern

13.05.2010, 22:54

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Ich wollte schon vorschnell antworten: "Nein, ich meine etwas anderes."

Bei tieferem Nachdenken hängen aber beide Dinge miteinander zusammen! Augenzwinkern

Augenzwinkern

Ja, das sehe ich inzwischen auch... Augenzwinkern

Augenzwinkern

Und ja, man muss sogar

$\begin{eqnarray*} ggT(n_1,n_2,\ldots,n_j)=1 \end{eqnarray*}$

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

$\begin{eqnarray*} d:=ggT(n_1,n_2,\ldots,n_j)>1 \end{eqnarray*}$

zuerst die eindeutig bestimmte positive reelle Lösung $\begin{eqnarray*} \tilde{\mu}_0 \end{eqnarray*}$ von

$\begin{eqnarray*} \sum_{k=1}^j x^{n_k/d}=1 \end{eqnarray*}$

bestimmt und anschließend dann die d Lösungen von $\begin{eqnarray*} x^d=\tilde{\mu}_0 \end{eqnarray*}$ , 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 Hammer

Hammer

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »