www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Kombinatorik
Kombinatorik < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kombinatorik: Tipp / Korrektur
Status: (Frage) beantwortet Status 
Datum: 14:30 Di 03.05.2016
Autor: Chrizzldi

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

        
Bezug
Kombinatorik: Antwort
Status: (Antwort) fertig Status 
Datum: 18:03 Di 03.05.2016
Autor: Leopold_Gast

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.

Bezug
                
Bezug
Kombinatorik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:17 Mo 09.05.2016
Autor: Chrizzldi

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!

Bezug
                        
Bezug
Kombinatorik: Antwort (fehlerhaft)
Status: (Antwort) fehlerhaft Status 
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

Bezug
                                
Bezug
Kombinatorik: Korrekturmitteilung
Status: (Korrektur) fundamentaler Fehler Status 
Datum: 09:52 Mi 11.05.2016
Autor: Leopold_Gast

Nicht alles stimmt (siehe meinen neuen Beitrag).

Bezug
                        
Bezug
Kombinatorik: Antwort
Status: (Antwort) fertig Status 
Datum: 09:51 Mi 11.05.2016
Autor: Leopold_Gast

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.mathebank.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]