Diskrete Mathematik/Gemischte Satzabfrage/15/Aufgabe/Lösung

1. In einem endlichen booleschen Verband besitzt jedes Element  $x\in B$  eine eindeutige Darstellung der Form

   $x=a_1\bigsqcup \dots \bigsqcup a_n$

   mit Atomen

   $a_j$.
2. Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge. Dann ist die Anzahl der surjektiven Abbildungen von $A$ nach $B$ gleich

   $\sum _{j=0}^k(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{k}{j})j^n.$

3. Es sei  $G=(V,E)$  ein Graph mit zugehöriger Adjazenzmatrix $A$. Dann ist die Anzahl der Wege von $u$ nach $v$ der Länge $\ell$ gleich dem Eintrag an der Stelle $(u,v)$ zur Matrixpotenz $A^{\ell }$.

Zur gelösten Aufgabe