Anzahl der k-Partitionen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:57 So 08.05.2011 | | Autor: | janisE |
| Aufgabe | Beweisen Sie: Die Anzahl der starken Partitionen von n mit s Summanden ist gleich der Anzahl der schwachen Partitionen von (n-s) mit s Summanden
Defs:
Eine Darstellung [mm]n = x_1 + x_2 + \cdots + x_s, x_i \in \IN[/mm] heißt schwache Partitition von n mit s Teilen falls [mm]x_i \geq 0[/mm] und starke Partitition falls [mm]x_i \geq 1[/mm].
Die Anzahl der Partitionen von n mit [mm]1 \leq s \leq n[/mm] Teilen ist [mm]2^{(n-1)}[/mm].
Seien n und s natürliche Zahlen. Dann ist die Anzahl der schwachen Partitionen von n mit s Teilen [mm]\binom{n+s-1}{s-1}[/mm]. |
Hallo!
Es muss also gezeigt werden, dass die Anzahl der starken Partitionen gleich [mm]\binom{(n-s)+s-1}{s-1} = \binom{n-1}{s-1}[/mm] ist.
Da ich mich unheimlich schwer damit tue, Gleichheit von Kardinalitäten über Bijektion zu zeigen, versuche ich einen argumentativen Ansatz. Aber ich hier komme ich leider nicht weiter.
Grundsätzlich gilt für die Möglichkeiten der starken Partition von n mit s Möglichkeiten
[mm]\sum\limits_{i=1}^n \text{\# Möglichkeiten von starken Part. von } (n-i) \text{ mit } ( s-1 ) \text{ Teilen } = \sum\limits_{i=1}^n \binom{(n-i)-1}{s-2}[/mm]
Mit dem Ansatz das i als erstes Element zu wählen, und dann versuche die restlichen (s-1) Elemente als Summe (n-i) zu gestalten.
Viel weiter hilft mir das jedoch auch nicht.
Könnt ihr mir bitte etwas weiterhelfen einen Ansatz und Weg zu finden?
Danke im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:11 So 08.05.2011 | | Autor: | felixf |
Moin!
> Beweisen Sie: Die Anzahl der starken Partitionen von n mit
> s Summanden ist gleich der Anzahl der schwachen Partitionen
> von (n-s) mit s Summanden
>
> Defs:
>
> Eine Darstellung [mm]n = x_1 + x_2 + \cdots + x_s, x_i \in \IN[/mm]
> heißt schwache Partitition von n mit s Teilen falls [mm]x_i \geq 0[/mm]
> und starke Partitition falls [mm]x_i \geq 1[/mm].
>
> Die Anzahl der Partitionen von n mit [mm]1 \leq s \leq n[/mm] Teilen
> ist [mm]2^{(n-1)}[/mm].
>
> Seien n und s natürliche Zahlen. Dann ist die Anzahl der
> schwachen Partitionen von n mit s Teilen
> [mm]\binom{n+s-1}{s-1}[/mm].
>
> Hallo!
>
> Es muss also gezeigt werden, dass die Anzahl der starken
> Partitionen gleich [mm]\binom{(n-s)+s-1}{s-1} = \binom{n-1}{s-1}[/mm]
> ist.
>
> Da ich mich unheimlich schwer damit tue, Gleichheit von
> Kardinalitäten über Bijektion zu zeigen,
Das ist hier aber mit Abstand der einfachste Weg.
Sei $X = [mm] \{ (x_1, \dots, x_s) \in \IZ^s \mid \sum_{i=1}^s x_i = n, \; x_i \ge 1 \}$ [/mm] und $Y = [mm] \{ (x_1, \dots, x_s) \in \IZ^s \mid \sum_{i=1}^s x_i = n - s, \; x_i \ge 0 \}$. [/mm] Du willst jetzt eine Bijektion $X [mm] \to [/mm] Y$ finden.
Schreib die Mengen fuer $n = 3$ und $s = 2$ doch mal konkret auf. Und evtl. fuer $n = 4$ wenn dir nichts auffaellt. Siehst du etwas?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:38 So 08.05.2011 | | Autor: | janisE |
> Das ist hier aber mit Abstand der einfachste Weg.
>
> Sei [mm]X = \{ (x_1, \dots, x_s) \in \IZ^s \mid \sum_{i=1}^s x_i = n, \; x_i \ge 1 \}[/mm]
> und [mm]Y = \{ (x_1, \dots, x_s) \in \IZ^s \mid \sum_{i=1}^s x_i = n - s, \; x_i \ge 0 \}[/mm].
> Du willst jetzt eine Bijektion [mm]X \to Y[/mm] finden.
Danke für die Antwort, Felix!
Also, die Bijektion entspricht der Abbildung
[mm]f : X \rightarrow Y = \{ (x_1 - 1,\cdots,x_s - 1) = x | x \in X \}[/mm]
Beweis der Bijektivität:
Injektivität:
Eigentlich trivial, wie soll man das beweisen? Aus festem s für X,Y und Abhängigkeit [mm]n_Y = n_X - s[/mm] per Definition von X,Y folgt, dass es für jedes Y genau ein Urbild gibt (oder?).
Surjektivität:
Für jedes s-Tupel [mm](x_1,\cdots,x_s) \in X[/mm] gilt [mm]\sum\limits_{i=1}^s x_i = (n-s)[/mm]. Wird nun die Inverse Funktion f' angewandt ergibt sich [mm](n-s) + s \cdot 1 = (n-s) + s = n[/mm]. Damit lässt sich jedes Element auf eine n-Partition mit s Teilen zurückführen.
Stimmt das soweit bzw. an welcher Stelle muss ich den Beweis korrigieren oder weiter ausführen? (Leider nicht meine Stärke..)
Danke für deine Geduld!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:21 So 08.05.2011 | | Autor: | felixf |
Moin!
> > Das ist hier aber mit Abstand der einfachste Weg.
> >
> > Sei [mm]X = \{ (x_1, \dots, x_s) \in \IZ^s \mid \sum_{i=1}^s x_i = n, \; x_i \ge 1 \}[/mm]
> > und [mm]Y = \{ (x_1, \dots, x_s) \in \IZ^s \mid \sum_{i=1}^s x_i = n - s, \; x_i \ge 0 \}[/mm].
> > Du willst jetzt eine Bijektion [mm]X \to Y[/mm] finden.
>
> Danke für die Antwort, Felix!
>
> Also, die Bijektion entspricht der Abbildung
>
> [mm]f : X \rightarrow Y = \{ (x_1 - 1,\cdots,x_s - 1) = x | x \in X \}[/mm]
Du meinst $f : X [mm] \to [/mm] Y$, [mm] $(x_1, \dots, x_s) \mapsto (x_1 [/mm] - 1, [mm] \dots, x_s [/mm] - 1)$.
Du musst uebrigens noch zeigen, dass dies wohldefiniert ist, sprich dass [mm] $(x_1 [/mm] - 1, [mm] \dots, x_s [/mm] - 1) [mm] \in [/mm] Y$ liegt falls [mm] $(x_1, \dots, x_s) \in [/mm] X$.
> Beweis der Bijektivität:
Am einfachsten ist, wenn du eine Abbildung $g : Y [mm] \to [/mm] X$ angibst, so dass $f [mm] \circ [/mm] g$ und $g [mm] \circ [/mm] f$ die Identitaet sind. Daraus folgt sofort, dass beide bijektiv sind.
> Injektivität:
>
> Eigentlich trivial, wie soll man das beweisen? Aus festem s
> für X,Y und Abhängigkeit [mm]n_Y = n_X - s[/mm] per Definition von
> X,Y folgt, dass es für jedes Y genau ein Urbild gibt
> (oder?).
Ich wuerd "klar" hinschreiben 
Ansonsten: seien [mm] $(x_1, \dots, x_s), (x_1', \dots, x_s') \in [/mm] X$ mit [mm] $f(x_1, \dots, x_s) [/mm] = [mm] f(x_1', \dots, x_1')$. [/mm] Also ist [mm] $(x_1 [/mm] - 1, [mm] \dots, x_s [/mm] - 1) = [mm] (x_1' [/mm] - 1, [mm] \dots, x_s' [/mm] - 1)$, womit [mm] $x_i [/mm] - 1 = [mm] x_i' [/mm] - 1$ fuer alle $i$ gilt. Addition von 1 auf beiden Seiten liefert [mm] $x_i [/mm] = [mm] x_i'$ [/mm] fuer alle $i$, und somit [mm] $(x_1, \dots, x_s) [/mm] = [mm] (x_1', \dots, x_s')$.
[/mm]
> Surjektivität:
>
> Für jedes s-Tupel [mm](x_1,\cdots,x_s) \in X[/mm] gilt
Du willst vermutlich ein Tupel aus $Y$ nehmen?
> [mm]\sum\limits_{i=1}^s x_i = (n-s)[/mm]. Wird nun die Inverse
> Funktion f' angewandt
Dass es die gibt musst du doch noch zeigen, dadurch dass zu zeigst das $f$ bijektiv ist.
Oder nimm dir einfach ein Tupel [mm] $(y_1, \dots, y_s) \in [/mm] Y$, und konstruiere daraus ein Tupel [mm] $(x_1, \dots, x_s) \in [/mm] X$ mit [mm] $f(x_1, \dots, x_s) [/mm] = [mm] (y_1, \dots, y_s)$. [/mm] (Das ist ganz einfach, du musst nur zeigen dass es wirklich in $X$ liegt.)
> ergibt sich [mm](n-s) + s \cdot 1 = (n-s) + s = n[/mm].
> Damit lässt sich jedes Element auf eine n-Partition mit s
> Teilen zurückführen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:16 So 08.05.2011 | | Autor: | janisE |
> > [mm]f : X \rightarrow Y = \{ (x_1 - 1,\cdots,x_s - 1) = x | x \in X \}[/mm]
>
> Du meinst [mm]f : X \to Y[/mm], [mm](x_1, \dots, x_s) \mapsto (x_1 - 1, \dots, x_s - 1)[/mm].
Ja, mir war nicht klar wie ich die Manipulation von Tupeln richtig beschreibe. So leuchtet es ein, danke!
> Du musst uebrigens noch zeigen, dass dies wohldefiniert
> ist, sprich dass [mm](x_1 - 1, \dots, x_s - 1) \in Y[/mm] liegt
> falls [mm](x_1, \dots, x_s) \in X[/mm].
Das würde ich so machen:
i) Da [mm]\forall x_i \in X : x_i \geq 1 \rightarrow x_i - 1 \geq 0[/mm]
ii) [mm]n - (s * 1) = n - s[/mm]
Damit sind alle Elemente gemäß Definition vorhanden und die Summe entspriht (n-s)
> > Beweis der Bijektivität:
>
> Am einfachsten ist, wenn du eine Abbildung [mm]g : Y \to X[/mm]
> angibst, so dass [mm]f \circ g[/mm] und [mm]g \circ f[/mm] die Identitaet
> sind. Daraus folgt sofort, dass beide bijektiv sind.
Das wusste ich nicht, danke für diesen äußerst hilfreichen Hinweis! Muss ich für g dann analog wie bei f auch die Wohlgeformtheit zeigen?
ansonsten ist [mm]g: Y \rightarrow X, (x_1, \dots, x_s) \mapsto (x_1 + 1, \dots, x_s + 1)[/mm]
[mm]f \circ g: (x_1, \dots, x_s) \mapsto (\underbrace{x_1 - 1}_{f} \underbrace{+1}_{g} , \dots, (x_s - 1) + 1) = (x_1, \dots, x_s) = id_X[/mm]
[mm]g \circ f: (x_1, \dots, x_s) \mapsto (\underbrace{x_1 + 1}_{g} \underbrace{-1}_{f} , \dots, (x_s + 1) - 1) = (x_1, \dots, x_s) = id_Y[/mm]
Vielen Dank für deine Hilfe und Mühe mit mir!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:59 So 08.05.2011 | | Autor: | felixf |
Moin!
> > Du musst uebrigens noch zeigen, dass dies wohldefiniert
> > ist, sprich dass [mm](x_1 - 1, \dots, x_s - 1) \in Y[/mm] liegt
> > falls [mm](x_1, \dots, x_s) \in X[/mm].
>
> Das würde ich so machen:
>
> i) Da [mm]\forall x_i \in X : x_i \geq 1 \rightarrow x_i - 1 \geq 0[/mm]
>
> ii) [mm]n - (s * 1) = n - s[/mm]
>
> Damit sind alle Elemente gemäß Definition vorhanden und
> die Summe entspriht (n-s)
![[ok]](/images/smileys/ok.gif "[ok]")
> > > Beweis der Bijektivität:
> >
> > Am einfachsten ist, wenn du eine Abbildung [mm]g : Y \to X[/mm]
> > angibst, so dass [mm]f \circ g[/mm] und [mm]g \circ f[/mm] die Identitaet
> > sind. Daraus folgt sofort, dass beide bijektiv sind.
>
> Das wusste ich nicht, danke für diesen äußerst
> hilfreichen Hinweis!
Den solltest du dir merken, das ist eine sehr wichtige Eigenschaft von bijektiven Funktionen 
> Muss ich für g dann analog wie bei f
> auch die Wohlgeformtheit zeigen?
Ja. Aber das geht genauso einfach wie bei $f$.
> ansonsten ist [mm]g: Y \rightarrow X, (x_1, \dots, x_s) \mapsto (x_1 + 1, \dots, x_s + 1)[/mm]
>
> [mm]f \circ g: (x_1, \dots, x_s) \mapsto (\underbrace{x_1 - 1}_{f} \underbrace{+1}_{g} , \dots, (x_s - 1) + 1) = (x_1, \dots, x_s) = id_X[/mm]
>
> [mm]g \circ f: (x_1, \dots, x_s) \mapsto (\underbrace{x_1 + 1}_{g} \underbrace{-1}_{f} , \dots, (x_s + 1) - 1) = (x_1, \dots, x_s) = id_Y[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:42 Mo 09.05.2011 | | Autor: | janisE |
Perfekt, vielen, vielen Dank!
|
|
|
|
