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
|
|