\magnification=\magstep1
\nopagenumbers
%\voffset=-1truecm
\hoffset=-0.5truecm
\vsize=27truecm
\baselineskip=12pt \parskip=1.5pt
\hyphenpenalty=5000 \pretolerance=200
\hyphenation{Teiler-kette Linear-kombination Kongruenz-relation} 

\bigskipamount=9pt plus 2pt minus 1.5pt


%\def\n{\underline{n}}

\font\smallrm=cmr7

% define whole mathfont family to get one lousy symbol 
\font\tennsym=msam10
\font\sevennsym=msam7
\newfam\nsymfam \def\nsym{\fam\nsymfam\tennsym}
\textfont\nsymfam=\tennsym
\scriptfont\nsymfam=\sevennsym
\mathchardef\nt="1845  % "normal subgroup" symbol (msam "45)

% blackboard bold
\font\tenbb=msbm10
\font\sevenbb=msbm7
\newfam\bbfam \def\bb{\fam\bbfam\tenbb}
\textfont\bbfam=\tenbb
\scriptfont\bbfam=\sevenbb

\font\tenbb=msbm10         % blackboard bold
\font\sevenbb=msbm7
\newfam\bbfam \def\bb{\fam\bbfam\tenbb}
\textfont\bbfam=\tenbb
\scriptfont\bbfam=\sevenbb

% making : a binary relation (for expressions like [R:I])
\newcount\codenumber \codenumber=`:
\loop\relax\if\codenumber>"FFF \advance\codenumber\by -"1000\repeat
\advance\codenumber by "3000
\mathcode`:=\codenumber

\def\divides{\mathrel\big\vert}

\def\ggT{\hbox{{\rm ggT}}}
\def\kgV{\hbox{{\rm kgV}}}
\def\id{\hbox{{\rm id}}}
\def\Ker{\hbox{{\rm Ker}}}
\def\Im{\hbox{{\rm Im}}}
\def\natn{{\bb N}}
\def\intz{{\bb Z}}
\def\F{{\bb F}}
\def\Fq{{\bb F}_q}

\def\eG{e_{\scriptscriptstyle G}}
\def\eH{e_{\scriptscriptstyle H}}
\def\Zerf{Zer\-f\"al\-lungs\-k\"or\-per}

\def\mspace{\mskip10mu plus 5 mu}


\line{{\rm 6.~\"Ubungsblatt Endliche K\"orper und Codierung} \hfill
{\rm SS 2008} }
\bigskip \bigskip \bigskip


\item{\bf 35.} 
Berechnen Sie die M\"obius-Funktion f\"ur den Verband der
Unterk\"orper des K\"orpers mit $q$ Elementen.
\bigskip

\item{\bf 36.}
Sein $W$ ein $r$-dim Teilraum eines $n$-dim
$\Fq$-Vektorraums $V$. Finden Sie eine Formel f\"ur die Anzahl
der $k$-dim Teilr\"aume von $V$, die mit $W$ trivialen 
Durchschnitt haben.
\bigskip

\item{\bf 37.}
Im Spezialfall $n=k+r$ des vorigen Beispiels kann man die L\"osung
auf elementare Art (ohne M\"obius-Inversion) finden.
\bigskip

\item{\bf 38.}
Sei $U$ ein Teilraum eines $n$-dim $\Fq$-Vektorraums $V$, und
$W$ ein $m$-dimensionaler $\Fq$-Vektorraum. Finden Sie eine Formel
f\"ur die Anzahl der linearen Abbildungen $\varphi\colon V\rightarrow W$
mit $\ker(\varphi)=U$ (via M\"obius-Inversion angewendet auf die 
Anzahl der $\varphi$ mit $\ker(\varphi)\supseteq U$).  F\"ur die
Anzahl der injektiven linearen Abbildungen $\varphi\colon V\rightarrow W$
erh\"alt man: 
$\sum_{k=0}^n(-1)^k \left[ {n\atop k} \right]_q q^{{k\choose 2}} q^{m(n-k)}$.
\bigskip

\item{\bf 39.}
Finden Sie auf elementare Weise (ohne M\"obius-Inversion) eine
einfachere Formel f\"ur die Anzahl der injektiven linearen Abbildungen
$\varphi\colon V\rightarrow W$ ($V$ ein $n$-dim $\Fq$-Vektorraum,
$W$ ein $m$-dimensionaler $\Fq$-Vektorraum). Mit der Formel f\"ur
die injektiven linearen Abbildungen aus dem vorigen Beispiel gleichgesetzt,
erh\"alt man eine Gleichung, aus der folgende Polynomgleichung folgt:
$$ \prod_{k=0}^{n-1}(x-q^k) = 
\sum_{k=0}^n(-1)^k \left[ {n\atop k} \right]_q q^{{k\choose 2}} x^{n-k}$$
\bigskip

\item{\bf 40.}
F\"ur alle $n\in\natn$ gilt:
$\sum\limits_{d | n} {{\mu(d)}\over d} = {{\varphi(n)}\over n}$.
\bigskip


\bye
