Polynome vom Grad höchstens k < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen,
die folgende Frage ist mir in der Numerik begegnet, lässt sich aber auf ein kombinatorisches Problem reduzieren:
Sei $P$ der Raum der Polynome auf dem [mm] $\IR^n$ [/mm] vom Grad höchstens $k$, d.h. genauer:
$$P:= [mm] \{p:\IR^n \mapsto \IR \; | \; p(x)= \sum_{|\alpha|=0}^k c_{\alpha}x^{\alpha} \}$$
[/mm]
wobei [mm] $\alpha \in \IR^n$ [/mm] und [mm] $x^{\alpha} [/mm] = [mm] x_1^{\alpha_1} [/mm] * [mm] \dots [/mm] * [mm] x_n^{\alpha_n}$ [/mm] die übliche Definition eines Multiindex ist.
Nun ist meine Frage: Welche Dimension hat $P$?
Das Ganze lässt sich meiner Meinung nach auf ein kombinatorisches Problem zurückführen. Nämlich indem man $n$-Fächer nimmt und auf diese Ziffern aus [mm] $\{0, \dots , k \}$ [/mm] verteilt (wobei auch Zahlen doppelt vorkommen dürfen). Dürfte man dies ohne Einschränkungen tun, so hätte man ja [mm] $(k+1)^n$ [/mm] Möglichkeiten. Schränkt man nun die Ziffern so ein, dass deren Summe $k$ ergeben muss, dann wird es für mich irgendwie zu kompliziert. Als Ergebnis kommt angeblich [mm] $\vektor{n + k\\ k}$ [/mm] heraus. Aber wie kommt man darauf?
Vielen Dank.
Grüße Andre
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 08:27 Mi 07.09.2011 | Autor: | statler |
Guten Morgen!
> die folgende Frage ist mir in der Numerik begegnet, lässt
> sich aber auf ein kombinatorisches Problem reduzieren:
>
> Sei [mm]P[/mm] der Raum der Polynome auf dem [mm]\IR^n[/mm] vom Grad
> höchstens [mm]k[/mm], d.h. genauer:
>
> [mm]P:= \{p:\IR^n \mapsto \IR \; | \; p(x)= \sum_{|\alpha|=0}^k c_{\alpha}x^{\alpha} \}[/mm]
>
> wobei [mm]\alpha \in \IR^n[/mm] und [mm]x^{\alpha} = x_1^{\alpha_1} * \dots * x_n^{\alpha_n}[/mm]
> die übliche Definition eines Multiindex ist.
>
> Nun ist meine Frage: Welche Dimension hat [mm]P[/mm]?
>
> Das Ganze lässt sich meiner Meinung nach auf ein
> kombinatorisches Problem zurückführen. Nämlich indem man
> [mm]n[/mm]-Fächer nimmt und auf diese Ziffern aus [mm]\{0, \dots , k \}[/mm]
> verteilt (wobei auch Zahlen doppelt vorkommen dürfen).
> Dürfte man dies ohne Einschränkungen tun, so hätte man
> ja [mm](k+1)^n[/mm] Möglichkeiten. Schränkt man nun die Ziffern so
> ein, dass deren Summe [mm]k[/mm] ergeben muss, dann wird es für
> mich irgendwie zu kompliziert. Als Ergebnis kommt angeblich
> [mm]\vektor{n + k\\ k}[/mm] heraus. Aber wie kommt man darauf?
Du ziehst aus den n+1 Dingen $1,\ [mm] x_1,\ \ldots\ [/mm] ,\ [mm] x_n$ [/mm] k-mal mit Zurücklegen. Das gibt die Basiselemente. Die Anzahlformel für 'mit Zurücklegen, ohne Reihenfolge' findest du in jedem Buch über Kombinatorik oder elementare Wahrscheinlichkeitsrechnung (hoffe ich mal).
Gruß aus HH-Harburg
Dieter
|
|
|
|
|
Hallo Dieter,
vielen Dank, dass war genau der Zusammenhang der mir fehlte.
Grüße Andre
|
|
|
|