Erzeugende Funktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:57 So 24.05.2009 | | Autor: | Held |
| Aufgabe | How many pairs X, Y of distinct subsets of [mm] \{1,2,... ,n \} [/mm] with X [mm] \subset [/mm] Y [mm] \subseteq \{1,2,... ,n \}are [/mm] there?
Give 2 different approaches to determine the number of pairs based on the 2 given hints:
1) Count the pairs inductively.
2) Give a generating function of the form f(x) [mm] =\bruch{Q(z)}{P(z)}with [/mm] polynomials P and Q. |
Hallo,
Ich komme mit Aufgabenteil 2 nicht zurecht.
Ich denke wenn ich eine Rekursiongleichung finde, dann hätt ich auch sofort die Generating Funktion.
Mein Problem ist,dass ich bisher keine Rekusionsgleichung gefunden habe.
Aufgabe 1) hab ich gelöst und es kommt raus das für [mm] \{1,2,... ,n \} [/mm] gibt es [mm] 3^{2 } -2^{n} [/mm] viele Möglichkeiten Mengen X und Y in obiger Form zu finden.
Wenn ich von dieser Lösung ausgehe und meine Erzeugende Funktion mit Koeffizienten [mm] a_{n}=3^{n}-2^{n} [/mm] wähle, so folgt nach rumrechnen
[mm] \bruch{Q(z)}{P(z)} [/mm] = [mm] \bruch{1}{1-3z} [/mm] - [mm] \bruch{1}{1-2z}
[/mm]
Aber die Aufgabe ist ja, ich soll eine Erzeugende Funktion finden und daraus herleiten, wieviele Mengen X,Y es gibt nicht umgekehrt.
Gibt es eine Möglichkeit sich eine Erzeugende Funktion zu basteln ohne Rekusionsgleichung, oder gibt es eine Rekursionsgleichung in diesem Fall?
Gruß Held
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Di 26.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
