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
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:

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


Alle Foren
Status vor 1h 13m 14. matux MR Agent
LinAMoVR/Diagonalmatrix
Status vor 7h 03m 2. fred97
DiffGlGew/Existenz des Polynoms
Status vor 8h 38m 4. meili
UAnaR1/Reaktion - erwünscht
Status vor 13h 51m 27. meili
SAnaSonst/Zylinder aus O und V
Status vor 1d 1h 51m 2. fred97
FunkAna/Trennungssatz von Hahn-Banach
^ Seitenanfang ^
www.vorhilfe.de