www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 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" - KompositionenAnzahl
KompositionenAnzahl < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

KompositionenAnzahl: Nachweisen von letzterem
Status: (Frage) beantwortet Status 
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?

  

        
Bezug
KompositionenAnzahl: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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! :-)

Bezug
        
Bezug
KompositionenAnzahl: Antwort
Status: (Antwort) fertig Status 
Datum: 20:58 Fr 04.11.2011
Autor: reverend

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]

> 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


Bezug
        
Bezug
KompositionenAnzahl: Antwort
Status: (Antwort) fertig Status 
Datum: 15:44 Fr 18.11.2011
Autor: Schokokuchen

Danke für den Hinweis reverend.

Ich weiß nicht, ob es für den Fragesteller noch relevant ist, aber ich habs nun so gemacht:

Teil 1 ist im wesentlichen so, wie bei clemenum, nur etwas anders aufgeschrieben.
[]http://i39.tinypic.com/b4hulw.jpg
[]http://i42.tinypic.com/1bvgg.jpg



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


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]