Anzahl monotoner Funktionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Ermitteln Sie die Anzahl der monoton steigenden Funktionen [mm] f:\{1,...,n\}\to\{1,...,n\}, [/mm] für die zusätzlich gilt f(x) [mm] \le [/mm] x. |
Hilfe, diese Aufgabe macht mich noch wahnsinnig :)
Ich kann die Anzahl natürlich als Verkettung von Summenzeichen darstellen, also n-1 Summenzeichen hintereinander und davon zwei durch umformen eliminieren, aber weiter bekomme ich das dann nicht vereinfacht und ein Ausdruck, in dem nicht mal die Anzahl der Summenzeichen fix ist, ist nicht gerade ne besonders tolle Lösung.
Da das eine Übungsaufgabe ist, schätze ich mal, dass es tatsächlich eine einfachere Formel dafür gibt, mit nöchstens doppelter Summe oder womöglich als geschlossene Formel mit Hilfe von Binomialkoeffizienten und Partitionen, aber ich kann sie nicht finden.
Hab auch schon versucht, die Anzahl der Funktionen einer n-Elementigen Menge irgendwie rekursiv aus der Anzahl einer kleineren Menge abzuleiten, aber auch das hat nicht geklappt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Mo 30.10.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
