250024 UE Diskrete Mathematik
Gruppe 1 10:15-11:00 im D1.01
Gruppe 2 11:15-12:00 im D1.01


Hier finden Sie die Beispiele zur Übung.

Der erste Termin der Vorlesungsprüfung ist am Freitag dem 12. März 14-17 im D101.

Beispiele für die nächste Stunde: alle weiteren ausgenommen 47 bis inklusive 48.

Hinweis zu Beispiel 31: Wir wissen, dass F(z)=1/(1-z-z2) die erzeugende Funktion der Fibonacci-Zahlen ist. Die erzeugende Funktion der Folge 1, -2, 22, -23, 24, -25,... ist G(z)=1/(1+2z). Warum?
Zeige dass F'(z)⋅G(z)=F(z)2 ist. Ein Koeffizientenvergleich für zn ergibt die gewünschte Identität.

Dass Sie sich eigenstündig Gedanken zu den an der Tafel diskutierten Beispielen machen, ist wichtiger als das korrekte Resultat. Es müssen mindestens 60% der Beispiele angekreuzt werden. Angekreuzt wird nur mit "Kreuzerl" nicht mit "Ringerl". Wenn Sie sich nicht sicher sind, ob Ihre Lösung richtig ist, kreuzen Sie es an, sofern Sie sich ernsthaft Gedanken zu dem Problem gemacht haben.

Bei Abwesenheit kontaktieren Sie mich bitte vor der Übungsstunde per Email oder Telefon (01/4277-50647 od. 0680/1285929). Sie haben dann die Möglichkeit die Beispiele schriftlich abzugeben und mit mir zu besprechen.

Wenn die Beispiele zu schwierig erscheinen, ist das kein Grund zur Verzweiflung: Kommen Sie in die Sprechstunde oder machen Sie sich einen Termin aus um sich Tipps zu holen oder Fragen zu stellen. Sie können mich jederzeit auch außerhalb der Sprechstunde spontan kontaktieren.

Ein Lösungsweg zu Beispiel 41:

Es sei p(n) die Anzahl der Partionen von n.
q(n) sei die Anzahl der Partionen von n, die keine durch 3 teilbahren Summanden besitzen.
r(n) sei die Anzahl der Partitionen von n, bei denen kein Summand 3 mal vorkommt.

Es sei a(3k) die Anzahl der Partionen von 3k, wo alle Summanden durch 3 teilbar sind. Solche Partionen können bijektiv auf Partionen von 3k abgebildet werden, wo die Häufigkeiten aller Summanden durch 3 teilbar sind. Die Bijektion ist die Abbildung, bei der jeder (durch 3 teilbare) Summand in drei gleiche Teile (in Trippel) zerlegt wird. Z.B: 3+3+9 wird abgebildet auf 1+1+1+1+1+1+3+3+3. Bei der Umkehrabbildung werden jeweils drei gleiche Summanden (Trippel) zusammemngefasst. Es ist außerdem a(3k)=p(k).
Es gilt
(a) q(n)=p(n)-q(n-3)a(3)-q(n-6)a(6)-...-q(n-3k)a(3k)-.... und
(b) r(n)=p(n)-r(n-3)a(3)-r(n-6)a(6)-...-r(n-3k)a(3k)-.....

Da q und r dieselbe Rekursion erfüllen, folgt mittels Induktion q(n)=r(n), was zu zeigen war.

Warum gelten (a) und (b)?
(a) q(n-3k)a(3k) ist die Anzahl der Partionen von n, bei denen die Summe der durch 3 teilbaren Summanden gleich 3k ist.
(b) Es ist r(n-3k)a(3k) die Anzahl der Partionen von n, bei denen die Summe einer maximalen Menge disjunkter Trippel gleich 3k ist.


Im Folgenden finden Sie die Noten, gemessen an Kreuzerln und Tafelmeldungen, aktualisiert am 27.01.2010. Sollten Sie nicht in der Liste aufscheinen, wird Ihnen kein Zeugnis ausgestellt. Sollten Sie damit oder mit der Note nicht einverstanden sein, melden Sie sich bis spätestens Montag 1. Februar (am besten per Email). Alle Angaben ohne Gewähr.

Gruppe 1
Matrikelnummer Note
0809797 2
0504111 1
0409967 2
8403551 3
0803551 3
0847859 4
0105267 3
0649293 2
0749185 2
8803117 2
0747190 4
0709591 3
0801860 2
0801965 2
0848567 1
0803513 4
0809525 2
0808550 3
0140154 2
0846664 2
0408468 1

Gruppe 2
0809606 2
0800455 2
7426009 1
0652267 3
0800899 1
0846300 3
0225715 2
0809818 1
0804084 1
0807084 1
0846087 1
0753952 2
0803406 1
0807780 1
0846305 1
0802443 1
0801265 1
0803462 1
0809513 2
0804631 1
0847188 2
0809524 2
0650964 2
0808567 2