Relationen/Endliche Menge/Reflexiv, symmetrisch/Anzahl/Aufgabe/Lösung

Es sei ${}M=\{1,\ldots ,n\}$. Eine Relation ${}R$ ist gegeben durch eine bestimmte Menge von geordneten Paaren ${}(x,y)$, ${}x,y\in M$. Daher kann man sich eine Relation auf ${}M$ so vorstellen, dass in einer ${}n\times n$-Tabelle gewisse Stellen angekreuzt werden und andere nicht.

Bei einer beliebigen Relation gibt es keine weiteren Bedingungen, sodass es ${}2^{n^{2}}$ Relationen gibt (das war nicht gefragt).

Bei einer reflexiven Relation muss auf der Diagonalen immer ein Kreuz sein, ansonsten hat man keine Bedingung, es gibt also ${}n^{2}-n=n(n-1)$ freie Stellen und daher ${}2^{n(n-1)}$ reflexive Relationen.

Bei einer symmetrischen Relation hat man oberhalb der Diagonalen (einschließlich dieser) volle Freiheiten (unterhalb der Diagonalen muss sich der Eintrag wiederholen). Da gibt es ${}{\frac {n^{2}-n}{2}}+n={\frac {n^{2}+n}{2}}$ Plätze und somit gibt es ${}2^{\frac {n^{2}+n}{2}}$ symmetrische Relationen.

Bei einer symmetrischen und reflexiven Relation hat man echt oberhalb der Diagonalen volle Wahlfreiheiten. Davon gibt es ${}{\frac {n^{2}-n}{2}}$ Plätze, sodass es ${}2^{\frac {n^{2}-n}{2}}$ symmetrische und reflexive Relationen gibt.

Zur gelösten Aufgabe