| Autor |
Beitrag |
    
Niels2 (Niels2)
Senior Mitglied
Benutzername: Niels2
Nummer des Beitrags: 910
Registriert: 06-2001
| | Veröffentlicht am Montag, den 24. November, 2003 - 15:42: | 
|
Hi Kollegen,
hier ist eine weitere schwierigere Aufgabe aus meiner Serie 5 der Linearen Algebra Übungen.
Da ja bekanntlich es schwierig ist in Zahlreich Aufgaben mit diversen Sonderzeichen präzise zu formulieren stelle ich am besten den gesammten Zettel hier ihn, mich persönlich würden nur Vorschläge zu Aufgabe 4 auf dem Zettel interessieren, Aufgabe 1 wurde schon gelöst und den rest habe ich auch schon fertig gelöst.
Also, hier ist der Zettel:
Und wie gesagt ich würde mich über Lösungsvorschläge für Aufgabe 4 freuen.
Hinweis zu Aufgabe 4: (Tipp vom Prof)
Man versuche eine gleichzeitige Induktion über n+m oder zumindest eine "doppelte Induktion" erst über n und dann gekapselt über m !
Allerdings hat mir der Hinweis nicht viel weitergeholfen....
Wie gesagt, ich würde mich wie immer über schnelle Hilfe freuen, und danke euch/ihr/ihm schon jetzt im Voraus für die Hilfe.
mfg
Niels |
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 707
Registriert: 11-2001
| | Veröffentlicht am Montag, den 24. November, 2003 - 18:51: |
|
Niels,
Lösen wir zunächst 4 b):
Es handelt sich um die verklausulierte
kombinatorische Aufgabe: Auf wieviele verschiedene
Arten lässt sich n als Summe von m nichtnegativen
ganzen zahlen schreiben, d.h. : wieviele Lösungen
(x1,...,xm) mit xi € N0 hat die Gleichung
x1+...+xm = n.
(Man kann ja o.B.d.A. M = {1,2,...,m} annehmen und
für k € M statt kf (= f(k) in anderer Notierung) auch
xk schreiben).
Noch anschaulicher: n nicht unterscheidbare Objekte
sollen auf m Schubfächer verteilt werden. In obiger
Gleichung ist also xi die Anzahl der Objekte im
i-ten Fach. Die zulässigen Verteilungen entsprechen
nun bijektiv den Folgen der Länge m+n-1 gebildet
mit 2 Zeichen, z.B. | und *: * kennzeichnet ein Objekt,
| trennt zwei Schubfächer. Beispiel:
* | | *** | ** entspricht m=4, n=5, x1=1,x2=0,
x3=3, x4=2.
Nun gibt es bekanntlich genau binom(m+n-1,n) =
binom(m+n-1,m-1) solcher Zeichenfolgen. Daher gilt
b(m,n) = binom(m+n-1,n).
Die kombinatorische Summenregel besagt nun
a(m,n) = b(m,0)+b(m,1) +...+ b(m,n) = binom(m+n,n).
Letzteres folgt leicht durch Induktion bzgl. n bei festem
m.
mfG Orion
|
Niels2 (Niels2)
Senior Mitglied
Benutzername: Niels2
Nummer des Beitrags: 911
Registriert: 06-2001
| | Veröffentlicht am Montag, den 24. November, 2003 - 20:38: |
|
Hallo Orion,
immer langsam- schließlich bin ich erst im 1. Semester....
Den Anfang habe ich ja noch verstanden, aber dann gehts los...
Noch anschaulicher: n nicht unterscheidbare Objekte
sollen auf m Schubfächer verteilt werden. In obiger
Gleichung ist also xi die Anzahl der Objekte im
i-ten Fach. Die zulässigen Verteilungen entsprechen
nun bijektiv den Folgen der Länge m+n-1 gebildet
mit 2 Zeichen, z.B. | und *: * kennzeichnet ein Objekt,
| trennt zwei Schubfächer. Beispiel:
* | | *** | ** entspricht m=4, n=5, x1=1,x2=0,
x3=3, x4=2.
Welche Folgen, und warum entsprechen sie der Länge m+n-1 gebildet mit 2 Zeichen? Welche 2 Zeichen? in deinem Beispiel was ich noch nachvollziehen konnte finde ich nur 1 Zeichen, nämlich das * (Sternchen), ich dachte "|" sumbolisiert nur die Trennwand der Schubladen?
Nun gibt es bekanntlich genau
binom(m+n-1,n)=binom(m+n-1,m-1) solcher Zeichenfolgen. Daher gilt
b(m,n)=binom(m+n-1,n).
Das mag ja für dich alles so bekannt sein, aber für mich ist das nicht bekannt.Also, wie kommst du auf diese Formel? Mit simple Kenntnisse über Binomialkoeffizienten reichen wohl nicht aus- mehr habe ich eigentlich nicht zur Verfügung...
Die kombinatorische Summenregel besagt nun
a(m,n)=b(m,0)+b(m,1)+...+b(m,n)=binom(m+n,n).
Letzteres folgt leicht durch Induktion bzgl. n bei festem
m.
hat das a(m,n) etwas mit dem a(m,n) auf dem Zettel zu tun oder nicht? und mit b(m,n) sind die von dir so definierten Binomialkoeffizienten gemeint oder?
Ich würde mich freuen wenn du diese Fragen meinerseits an dich auch noch klären könntest.
mfg
Niels}
|
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 708
Registriert: 11-2001
| | Veröffentlicht am Montag, den 24. November, 2003 - 22:02: |
|
Hallo Niels,
Die beiden Zeichen sind "|" (Strich) und "*" (Stern).
Meistens schreibt man "1" und "0" und spricht dann
von Nulleinsfolgen (die Informatiker würden vielleicht
lieber "Bitfolgen" sagen). Ich bin mal davon ausgegangen, dass Du über Grundbegriffe der
Kombinatorik verfügst. Dort lernt man, dass es genau
binom(N,k) = N!/k!/(N-k)! Nulleinsfolgen der Länge N
mit genau k-mal "0" gibt : das ist gerade die Anzahl
Möglichkeiten, aus N numerierten Plätzen k Plätze
auszuwählen (um diese nämlich mit 0 zu besetzen).
Warum im obigen Problem N = m+n-1 und k=n ist,
habe ich mit dem Zahlenbeispiel zu erklären versucht.
a(m,n) und b(m,n) sind genaun die in der Aufgabe
definierten Anzahlen. binom(N,k) ist wie gesagt der
Binomialkoeffizient ("N über k"):
binom(N,k) = N!/k!(N-k)! = N(N-1)***(N-k+1)/k!
Für den erwähnten Induktionsbeweis braucht man
die folgende Eigenschaft (Pascal-Dreieck !):
binom(N,k) + binom(N,k+1) = binom(N+1,k+1).
Mach dir anhand der Definitionen klar, dass man a(m,n) erhält, indem man
die Anzahlen b(m,0), b(m,1),...,b(m,n) aufaddiert.
mfG Orion
|
Niels2 (Niels2)
Senior Mitglied
Benutzername: Niels2
Nummer des Beitrags: 912
Registriert: 06-2001
| | Veröffentlicht am Dienstag, den 25. November, 2003 - 07:19: |
|
Hi Orion,
mal sehen ob ich das jetzt alles verstanden habe:
In der Aufgabe ist N=n+m-1 weil mindestens ein Fach nur ein Zeichen enthält?
Das Beispiel verstehe ich glalube ich, aber die Begründung warum N=n+m-1 müsstest du nochmal in Worte fassen- wäre jedenfalls toll wenn du das machen könntest....
Das mit dem Pascaldreieck ist klar, und die Summenformel beim Pascaldreieck haben wir auch schon gehabt- der Beweis per Induktion am Ende sollte daher kein Problem sein. Die Frage ist nur warum man über die "kombinatorische Summenformel" von b(m,n) auf a(m,n) kommt.Klar, die Summenformel kann man eben per Induktion beweisen, nur der Kombinatorische Hintergedanke dabei ist mir schleierhaft.Wenn du den auch nochmal kurz erläutern könntest wäre es sehr hilfreich.
Ich bin halt kombinatorisch schwach....
mfg
Niels |
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 709
Registriert: 11-2001
| | Veröffentlicht am Dienstag, den 25. November, 2003 - 10:13: |
|
Niels,
Wir wollen n nicht unterscheidbare Objekte (z.B.
weisse Tischtennisbälle, hier gekennzeichnet durch *)
auf m Fächer verteilen. Stell dir die Fächer
nebeneinander angeordnet vor, etwa
Fach 1 | Fach 2 | .... | Fach m
Dazu brauchst Du m-1 Trennstriche. Nachdem Du nun
die n Objekte in den Fächern nebeneinander verstaut
hast, kannst Du die Konfiguration eben durch eine
Zeichenfolge bestehend aus m-1 mal "|" und n mal "*"
beschreiben, also eine Folge der Länge N = m-1+n
mit Zeichen aus der 2-elementigen Menge (dem "Alphabet") {|,*}, in der genau n mal das Zeichen *
( und daher m-1 mal das Zeichen |) vorkommt. Die
Kombinatorik sagt, dass es genau binom(m+n-1,n)
solche Folgen gibt => b(m,n) = binom(m+n-1,n).
Wie kommt man von da auf a(m,n)? Ich benutze Deine
Notation und kürze ab
sum{x€M}xf =: S.
Es gilt S £ n <=> S=r , r € {0,1,...,n}
Die abzuzählende Menge A:= {f | S £ n} ist daher
offenbar die Vereinigung der n+1 disjunkten Mengen
Ar := {f | S = r} , r = 0,...,n
mit | Ar | = b(m,r).
Die zitierte Summenregel besagt in Worten:
Die Kardinalzahl der Vereinigung endlich vieler paarweise disjunkter endlicher Mengen ist = der Summe der Kardinalzahlen dieser Mengen.
Also
| A | = | A0 | + | A1 | + ... + | An | <=>
a(m,n) = b(m,0) + b(m,1) + ... + b(m,n).
Die b(m,r) wurden aber oben bestimmt :
b(m,r) = binom(m+r-1, r).
Alles klar ?
(Beitrag nachträglich am 25., November. 2003 von Orion editiert)
mfG Orion
|
Niels2 (Niels2)
Senior Mitglied
Benutzername: Niels2
Nummer des Beitrags: 913
Registriert: 06-2001
| | Veröffentlicht am Dienstag, den 25. November, 2003 - 18:21: |
|
Hi Orion,
mal sehen ob ich es jetzt verstanden habe....
den Fall b(m,n) kann man also auf ein Anordnungsproblem zurückführen. Die Klassische Frage wäre, wieviele Möglichkeiten der Anordnung von je k aus n Elementen gibt es:
Klassische Antwort:
[n über k]
wir wollen nun aber die Anzahlt der Möglichkeiten der Darstellung von Folgen der Laänge n+m-1 wissen, bei denen also die n Objekte Zugeordent werden. Klassische Antwort:
[n+m-1 über n]=[n+m-1 über m-1]
D.h Aufgabe 4b ist recht "einfach" über klassische Kombinatorik einzusehen...
um dann a(m,n) zu errechnen Forme man die Notation um, wie du es getan hast und muss dann halt "nur" die Kardinalitäten der Einzelmengen addieren, um Die Kardinalitäten der Gesamtmenge zu erhalten. Und mann muss die Vereinigung von n+1 disjunkten Mengen betrachten, weil r Element {0,....,n} ist und die Mengen damit die Mächtigkeit n+1 besitzt (n+1 Elemente enthält)
Wenn ich das so richtig verstanden habe habe ich es begriffen...
also, noch bitte einmal kontrollieren....
mfg
Niels |
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 710
Registriert: 11-2001
| | Veröffentlicht am Mittwoch, den 26. November, 2003 - 08:23: |
|
Niels,
Du müsstest Dich mal mit den Grundaufgaben der
abzählenden Kombinatorik vertraut machen, am besten
an Hand eines Buches : Das ist ohnehin ganz wichtig. Nur soviel: Die Anzahl der
Möglichkeiten, k Elemente aus einer Menge von n
Elementen a n z u o r d n e n ist nicht = binom (n,k)
sondern
= n*(n-1)*...*(n-k+1) = k!*binom(n,k).
binom(n,k) ist die Antwort auf die Frage: Auf wieviele
Arten kann man aus einer Menge von n Elementen
k Elemente a u s w ä h l e n (z.B.im sog. Urnenmodell: k numerierte Kugeln aus einer "Urne" mit n solcher Kugeln) Beachte: Wenn von Elementen einer Menge die Rede ist, so handelt es
sich um u n t e r s c h e i d b a r e Objekte.
In unserem Fall w ä h l e n wir aus den m+n-1
Plätzen n Plätze a u s und besetzen sie mit den n
n i c h t u n t e r s c h e i d b a r e n Objekten *.
Daher b(m,n) = binom(m+n-1,n).
Das müsstest Du Dir noch klar machen.
mfG Orion
|
Niels2 (Niels2)
Senior Mitglied
Benutzername: Niels2
Nummer des Beitrags: 914
Registriert: 06-2001
| | Veröffentlicht am Mittwoch, den 26. November, 2003 - 12:32: |
|
Hi Orion,
vielen Dank für deine Hilfe!
Noch eine Frage:
könntest du mir ein gutes Buch zur Kombinatork empfehlen? Möglichst eins was zum Selbststudium zu gebrauchen ist.
mfg
Niels
|
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 712
Registriert: 11-2001
| | Veröffentlicht am Mittwoch, den 26. November, 2003 - 14:13: |
|
Niels,
das Wichtigste sterht auf den ersten paar Seiten von
Arthur Engel : Stochastik, Klett Studienbücher.
mfG Orion
|
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 713
Registriert: 11-2001
| | Veröffentlicht am Mittwoch, den 26. November, 2003 - 16:47: |
|
Ich sollte vielleicht noch erwähnen:
Max Jeger, Einführung in die Kombinatorik , 2 Bde.
Ebenfalls in der Reihe Klett Studienbücher.
mfG Orion
|
|
Blatt05
