Kombinatorik < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe 1 | Seien $k$ und $r$ natürliche Zahlen.
Wie viele $r$-Tupel [mm] $(x_1, \ldots, x_r)$ [/mm] von nicht-negativen Zahlen gibt es mit [mm] $x_1 [/mm] + [mm] \ldots [/mm] + [mm] x_r \leq [/mm] k$? |
| Aufgabe 2 | | Für welche natürlichen Zahlen $r$ und $k$ ist die Anzahl in a) genau doppelt so groß wie die Anzahl aller $r$-Tupel [mm] $(x_1, \ldots, x_r)$ [/mm] von nicht-negativen Zahlen mit [mm] $x_1 [/mm] + [mm] \ldots [/mm] + [mm] x_r [/mm] = k?$ |
Hallo liebes Matheforum,
ich knabbere gerade an den zwei Aufgaben.
Zu Aufgabe 1) fehlt mir glaube ich Basiswissen, also ein bestimmter Satz aus der Kombinatorik. Mein Gedankengang war/ist zu folgender Überlegung gekommen:
Ich müsste wissen, wieviele unterschiedliche Zahlen in den Tupel zulässig sind. Mir ist nur nicht klar, wie ich das prüfen kann. Aber z.B. das Tupel:
[mm] $(x_1, \ldots, x_1, x_{k - r + 1}$ [/mm] beschreibt ja gerade die Kombinationen an Tupel die [mm] \binom{r}{1} [/mm] sind. Weil wir ja nur zwei unterschiedliche Zahlen haben. Ich habe mir jetzt auch überlegt, dass weiter zu spielen, also die Frage zu stellen welche Kombinationen für 3 unterschiedliche Zahlen möglich sind. Dann für 4 usw. Aber das Gefühl so auf dem richtigen Weg zu sein habe ich nicht. Ist mein Denkansatz komplett verkehrt?
Danke für eure Tipps!
(Aufgabe 2 setzt leider das Verständnis von Aufgabe 1 voraus).
Viele Grüße,
Chris
|
|
| |
|
Durch Einführen einer weiteren Variablen [mm]x_{r+1}[/mm], die nichtnegativer ganzer Zahlen fähig ist, kannst du aus der Ungleichung eine Gleichung machen:
[mm]x_1 + x_2 + \ldots + x_r \leq k \ \ \Leftrightarrow \ \ x_1 + x_2 + \ldots + x_r + x_{r+1} = k[/mm]
Wie ist das gemeint? Nehmen wir als Beispiel [mm]r=3[/mm] und [mm]k=2[/mm]. Es gibt dann eine Bijektion zwischen den [mm](x_1,x_2,x_3)[/mm], deren Summe höchstens 2 ist, und den [mm](x_1,x_2,x_3,x_4)[/mm], deren Summe genau 2 ist. Die zusätzliche Variable [mm]x_4[/mm] füllt zur vollen Summe 2 auf. Geben wir die Bijektion konkret in Listenform an:
Summe=0
[mm](0,0,0) \mapsto (0,0,0,2)[/mm]
Summe=1
[mm](1,0,0) \mapsto (1,0,0,1)[/mm]
[mm](0,1,0) \mapsto (0,1,0,1)[/mm]
[mm](0,0,1) \mapsto (0,0,1,1)[/mm]
Summe=2
[mm](1,1,0) \mapsto (1,1,0,0)[/mm]
[mm](1,0,1) \mapsto (1,0,1,0)[/mm]
[mm](0,1,1) \mapsto (0,1,1,0)[/mm]
[mm](2,0,0) \mapsto (2,0,0,0)[/mm]
[mm](0,2,0) \mapsto (0,2,0,0)[/mm]
[mm](0,0,2) \mapsto (0,0,2,0)[/mm]
Links hast du alle Tripel mit Summe höchstens 2, rechts alle Quadrupel mit Summe genau 2.
Das heißt, statt die [mm]r[/mm]-Tupel mit höchstens [mm]k[/mm] als Summe zu zählen, kann man auch die [mm](r+1)[/mm]-Tupel mit genau [mm]k[/mm] als Summe zählen. Und wie macht man das?
Auch das vielleicht an einem Beispiel mit [mm]k=5[/mm]:
[mm]x_1 + x_2 + x_3 + x_4 = 5[/mm]
Die Summe 5 symbolisieren wir durch 5 Kugeln: ooooo. Und diese 5 Kugeln verteilen wir auf vier Fächer, das erste Fach für [mm]x_1[/mm], das zweite für [mm]x_2[/mm] und so weiter. Um die Fächer zu trennen, benötigen wir 3 Trennwände.
|ooo|o|o würde 0+3+1+1=5 entsprechen, ooooo||| würde 5+0+0+0=5 entsprechen, o|o|oo|o würde 1+1+2+1=5 entsprechen. Statt also die Summen zu zählen, kann man auch die zugehörigen Symbole aus o und | zählen. Das ist aber ein bekanntes kombinatorisches Problem.
|
|
|
| |
|
Lieber Leopold_Gast,
vielen Dank für dieses tolle Konstrukt. Du hast mir unglaublich weitergeholfen. Und wenn ich dein Ansatz richtig verstanden habe, dann ist damit ja quasi Aufgabenteil 2 schon beantwortet (Es gibt keine Zahl).
Für mich hat es sehr viel Sinn ergeben und ich meine die Antwort nun so richtig beantworten zu können:
[mm] \binom{k + r - 1}{r - 1}
[/mm]
Wobei $k + r - 1$ eben die Anzahl aller Pläte (inkl. Trennwände) und $r-1$ die Anzahl der Trennwände für $r$ Fächer ist.
Vielen vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 18:48 Mo 09.05.2016 | | Autor: | reverend |
Hallo Chrizzidi,
> Lieber Leopold_Gast,
>
> vielen Dank für dieses tolle Konstrukt. Du hast mir
> unglaublich weitergeholfen. Und wenn ich dein Ansatz
> richtig verstanden habe, dann ist damit ja quasi
> Aufgabenteil 2 schon beantwortet (Es gibt keine Zahl).
>
> Für mich hat es sehr viel Sinn ergeben und ich meine die
> Antwort nun so richtig beantworten zu können:
> [mm]\binom{k + r - 1}{r - 1}[/mm]
> Wobei [mm]k + r - 1[/mm] eben die Anzahl
> aller Pläte (inkl. Trennwände) und [mm]r-1[/mm] die Anzahl der
> Trennwände für [mm]r[/mm] Fächer ist.
>
> Vielen vielen Dank!
Ja, das stimmt so.
Grüße
reverend
|
|
|
| |
|
Nicht alles stimmt (siehe meinen neuen Beitrag).
|
|
|
| |
|
[mm]a_{k,r} = {{k+r} \choose r} = {{k+r} \choose k}[/mm] ist die Anzahl der [mm]r[/mm]-Tupel mit Summe [mm]\leq k[/mm]
[mm]b_{k,r} = {{k+r-1} \choose {r-1}} = {{k+r-1} \choose k}[/mm] ist die Anzahl der [mm]r[/mm]-Tupel mit Summe [mm]=k[/mm]
Die Gleichung [mm]a_{k,r} = 2 \, b_{k,r}[/mm] ist durchaus lösbar.
Anscheinend hast du nicht beachtet, daß die Anzahl der Variablen beim ersten Abzählungstrick erhöht wurde.
Beispiel für [mm]k=r=3[/mm]
000
100
010
001
110
101
011
200
020
002
111
210
120
201
102
021
012
300
030
003
Mit Summe [mm]\leq 3[/mm] gibt es genau doppelt so viele Tripel wie mit Summe [mm]=3[/mm].
|
|
|
|
