Diskrete mathe < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:03 Mo 08.05.2006 | | Autor: | Sunny85 |
| Aufgabe | Man zeige, dass für alle positiven ganzen Zahlen k und n gilt:
[mm] p_{k}(n)\le(n-k+1)^k-1
[/mm]
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich weiß, das dieses pk(n) die Anzahl der Partitionen mit genau k Teilen ist. Nur leider weiß ich nicht, wie ich diese Information verwenden soll. Muss ich die Gleichung umstellen? Ich wäre sehr dankbar, wenn mir jemand bei diesem Problem helfen könnte.
|
|
| |
|
Hallo und guten Tag,
ist es richtig, dass es dabei um Mengenpartitionen der Menge [mm] \{1,\ldots n\}
[/mm]
in mindestens k nicht-leere Mengen geht ?
Wenn ja:
Das erste Element 1 gehört zu einer Klasse.
Fall 1: Diese hat genau ein Element. [mm] p_{k-1}(n-1) [/mm] Möglichkeiten
Fall 2: Diese hat mind. zwei Elemente [mm] p_{k}(n-1) [/mm] Möglichkeiten
Also haben wir die Rekursion
[mm] p_k(n)=p_{k-1}(n-1)+p_k(n-1)
[/mm]
und [mm] p_1(n)=1 [/mm] für alle [mm] n\in\IN
[/mm]
Nun würd ich vielleicht zunächst versuchen, die behauptete Ungleichung induktiv zu beweisen.
Im Induktionsschritt wäre dabei dann sowas zu zeigen wie
[mm] ((n-1)-(k-1)+1)^{k-1}-1+((n-1)-k+1)^k-1\leq (n-k+1)^k-1,
[/mm]
also
[mm] (n-k+1)^{k-1}+(n-k)^k\leq (n-k+1)^k.
[/mm]
Viel Erfolg,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Do 11.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
