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

In einem endlichen booleschen Verband besitzt jedes Element ${}x\in B$ eine eindeutige Darstellung der Form
${}x=a_{1}\sqcup \ldots \sqcup a_{n}\,$

mit Atomen
${}a_{j}$ .
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}{\binom {k}{j}}j^{n}.$
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 }$ .

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.