Kombinatorische Algorithmen

Blatt 10 SS00

Prof. Laue

Abgabe 12.07.2000
 
 
 
 
 

Aufgabe 13 (3+3+1+6) Gausspolynom
 

In Aufgabe 6 wurde das Hasse Diagramm der Partitionen innerhalb des Rechtecks mit k Zeilen und n Spalten betrachtet. Jeder solchen Partition (sei sie vom Gewicht m) wird das Monom qm zugeordnet. Die Summe über alle Partitionen ergibt ein Polynom g(n+k,n). Im Beispiel der Partitionen innerhalb des 2x2 Rechtecks hat man: g(4,2) = q4 + q3 + 2q2 + q + 1. Diese Polynome mit 2 Parameter werden Gausspolynome genannt.

1) Zeigen Sie die Rekursion:
        g(n+1,k) = g(n,k-1) + qk g(n,k)
     wobei man g(n,0) := 1 definiert

2) man zeige:
                  (qn -1)(qn-q)............(qn-qk-1)
     g(n,k)=  --------------------------------------------
                  (qk-1)(qk-q)...............(qk-qk-1)

3) warum nennt man die Gausspolynome auch q-Binomalkoeffizienten?

4) Sei q eine Primzahlpotenz. Zeige:
        Die Anzahl der k-dimensionalen Untervektorräume eines n-dimensionalen Vektorraums über dem Körper mit q Elementen ist: g(n,k)
 
 

Aufgabe 14 (2)

Sie haben ein wichtiges Manuscript mit n Blättern geschrieben. Sie öffnen leichtsinnigerweise das Fenster und ein Windstoß verteilt die Blätter gleichmäßig im Zimmer. Zeigen Sie: Nach dem Einsammeln ist mit einer Wahrscheinlichkeit >1/3 kein einziges Blatt an der richtigen Stelle. (n groß genug)