KompositionenAnzahl < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:24 Mi 02.11.2011 | | Autor: | clemenum |
| Aufgabe | | Sei $1 [mm] \le [/mm] k < n.$ Zeige, daß die Anzahl der Kompositionen von $n$ genau [mm] $2^{n-1}$ [/mm] beträgt und der Teil $k$ genau $(n - k + [mm] 3)2^{n- k-2}$ [/mm] -mal auftritt. |
Für den ersten zu beweisen Teil, stelle ich mal folgende Frage:
Wie viele Kompositionen von [mm] $[n]:=\{1,2,3\ldots,n\} [/mm] $ mit genau $k$ Summanden gibt es ?
Sei zunächst $k$ festgehalten.
Am sinnvollsten erscheint eine bijektive Abbildung: Jede Komposition $n = [mm] a_1 +a_2+\ldots+a_k$ [/mm] von $n$ mit $k$ Summanden ordne man die Menge ihrer ersten $k- 1$ Partialsummen zu, also:
[mm] $a_1+a_2+\ldots+a_k \mapsto \{a_1,a_1+a_2,a_1+a_2+a_3,\ldots, a_1+\ldots + a_{k-1} \}.$ [/mm] Offenbar ergibt sich eine $(k-1)$-Menge von $[n-1].$ Damit ergibt sich (mit der Bijektionsregel) die Anzahl zu [mm] ${n-1\choose k-1} [/mm] $
Sei nun $k$ beliebig.
Für die Anzahl aller Kompositionen ergibt sich aus obiger Feststellung nun sofort:
[mm] $\sum_{k=0}^{n-1} [/mm] {n-1 [mm] \choose [/mm] k.}$ Und das ist gerade die Mächtigkeit einer $(n-1)$-elementigen Potenzmenge, also [mm] $2^{n-1} [/mm] $
Den anderen Teil der Behauptung kann ich jedoch mit einer bijektiven Abbildung nicht beweisen, anfangs dachte ich noch, dass es funktioniert. Ich stehe bei diesem Teil auf der Leitung im Moment. Kann mir da jemand weiterhelfen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:06 Mi 02.11.2011 | | Autor: | clemenum |
Eine Frage:
Ist die zweite Behauptung echt soo kompliziert, dass es nichtmal ihr - Experten - lösen könnt? :-O
Okay, dann muss ich das morgen dem Prof. sagen (dass es eine Überforderung für den Durchschnittsstudenten darstellt)^^
Ich dachte anfangs auch, dass die zweite Behauptung analog aus der Voraussetzung der ersten folgt, aber, so einfach ist es offenbar doch nicht...
Trotzdem wäre ich euch sehr dankbar, wenn ihr das Rätsel doch knacken könntet! 
|
|
|
| |
|
Hallo clemenum,
ich bin zwar kein Experte, aber ich versuchs mal...
> Sei [mm]1 \le k < n.[/mm] Zeige, daß die Anzahl der Kompositionen
> von [mm]n[/mm] genau [mm]2^{n-1}[/mm] beträgt und der Teil [mm]k[/mm] genau [mm](n - k + 3)2^{n- k-2}[/mm]
> -mal auftritt.
> Für den ersten zu beweisen Teil, stelle ich mal folgende
> Frage:
> Wie viele Kompositionen von [mm][n]:=\{1,2,3\ldots,n\}[/mm] mit
> genau [mm]k[/mm] Summanden gibt es ?
> Sei zunächst [mm]k[/mm] festgehalten.
> Am sinnvollsten erscheint eine bijektive Abbildung: Jede
> Komposition [mm]n = a_1 +a_2+\ldots+a_k[/mm] von [mm]n[/mm] mit [mm]k[/mm] Summanden
> ordne man die Menge ihrer ersten [mm]k- 1[/mm] Partialsummen zu,
> also:
> [mm]a_1+a_2+\ldots+a_k \mapsto \{a_1,a_1+a_2,a_1+a_2+a_3,\ldots, a_1+\ldots + a_{k-1} \}.[/mm]
> Offenbar ergibt sich eine [mm](k-1)[/mm]-Menge von [mm][n-1].[/mm] Damit
> ergibt sich (mit der Bijektionsregel) die Anzahl zu
> [mm]{n-1\choose k-1}[/mm]
> Sei nun [mm]k[/mm] beliebig.
> Für die Anzahl aller Kompositionen ergibt sich aus obiger
> Feststellung nun sofort:
> [mm]\sum_{k=0}^{n-1} {n-1 \choose k.}[/mm] Und das ist gerade die
> Mächtigkeit einer [mm](n-1)[/mm]-elementigen Potenzmenge, also
> [mm]2^{n-1}[/mm]
Sehr schön. ![[ok]](/images/smileys/ok.gif "[ok]")
> Den anderen Teil der Behauptung kann ich jedoch mit einer
> bijektiven Abbildung nicht beweisen, anfangs dachte ich
> noch, dass es funktioniert. Ich stehe bei diesem Teil auf
> der Leitung im Moment. Kann mir da jemand weiterhelfen?
Musst Du es denn kombinatorisch bzw. durch eine bijektive Abbildung beweisen? Mir fällt da auch keine ein.
Betrachten wir die Zahlen, die übrigbleiben, wenn k bereits als Summand feststeht. Die Restsumme n-k kann nun - wie Du gerade gezeigt hast - auf [mm] 2^{n-k-1} [/mm] Weisen dargestellt werden.
Aber gehen wir eine Ebene tiefer: die Restsumme durch m Summanden darzustellen, geht auf [mm] \vektor{n-k-1\\m-1} [/mm] Weisen, wie Du ebenfalls oben gezeigt hast.
Nun kann an jeder Stelle der Summation der Summand k eingefügt werden.
Es gibt also bei m+1 Summanden (wovon einer k ist) gerade [mm] (m+1)\vektor{n-k-1\\m-1} [/mm] Möglichkeiten, n darzustellen.
Nun bleibt "nur noch" die Gesamtschau:
Sei z(k,n) die Zahl der Kompositionen von n, die den Summanden k beinhalten. Dann ist
[mm] z(k,n)=\summe_{m=1}^{n-k}(m+1)\vektor{n-k-1\\m-1}
[/mm]
Damit hätten wir ja schonmal eine schöne Formel. Fragt sich nur, wie man jetzt zeigt, dass sie der Behauptung aus der Aufgabe entspricht. Wahrscheinlich etwa so, wie Du den ersten Teil gelöst hast, über "Festhalten" und Induktion.
Aber diesen Einsatz von Gehirnschmalz überlasse ich mal Dir oder anderen, die sich hier noch einbringen wollen.
Grüße
reverend
|
|
|
|
![[]](http://i39.tinypic.com/b4hulw.jpg){kind=small}
http://i39.tinypic.com/b4hulw.jpg![[]](http://i42.tinypic.com/1bvgg.jpg){kind=small}
http://i42.tinypic.com/1bvgg.jpg