6. Übungsblatt Endliche Körper und Codierung SS 2008

35. Berechnen Sie die Möbius-Funktion für den Verband der Unterkörper des Körpers mit q Elementen.

36. Sein W ein r-dim Teilraum eines n-dim 𝔽_{q}-Vektorraums V. Finden Sie eine Formel für die Anzahl der k-dim Teilräume von V, die mit W trivialen Durchschnitt haben.

37. Im Spezialfall n = k + r des vorigen Beispiels kann man die Lösung auf elementare Art (ohne Möbius-Inversion) finden.

38. Sei U ein Teilraum eines n-dim 𝔽_{q}-Vektorraums V, und W ein m-dimensionaler 𝔽_{q}-Vektorraum. Finden Sie eine Formel für die Anzahl der linearen Abbildungen φ: V → W mit ker(φ) = U (via Möbius-Inversion angewendet auf die Anzahl der φ mit ker(φ) ⊇ U). Für die Anzahl der injektiven linearen Abbildungen φ: V → W erhält man: ∑_{k=0}^{n}(−1)^{k} \left[{n \atop k}\right]_{q} q^{\binom{k}{2}}q^{m(n−k)}.

39. Finden Sie auf elementare Weise (ohne Möbius-Inversion) eine einfachere Formel für die Anzahl der injektiven linearen Abbildungen φ: V → W (V ein n-dim 𝔽_{q}- Vektorraum, W ein m-dimensionaler 𝔽_{q}-Vektorraum). Mit der Formel für die injektiven linearen Abbildungen aus dem vorigen Beispiel gleichgesetzt, erhält man eine Gleichung, aus der folgende Polynomgleichung folgt:

∏_{k=0}^{n−1}(x − q^{k}) = ∑_{k=0}^{n}(−1)^{k} \left[{n \atop k}\right]_{q} q^{\binom{k}{2}}x^{n−k}

40. Für alle n ∈ ℕ gilt: ∑_{d|n} \frac{μ(d)}{d} = \frac{φ(n)}{n}.