reflex.&sym. Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei M={1,2,...,n}.
(i) Wieviele reflexive Relationen gibt es auf M?
(ii) Wieviele symmetrische Relationen gibt es auf M? |
Hallo!
Reflexive Relationen sind es [mm] \bruch{n}{2} [/mm] , oder? Aber wieviel symmetrische Relationen sind es? Wie bekomme ich das denn raus?
Danke!
Raingirl87
|
|
| |
|
Hallo,
also schon die Zahl der reflexiven Relationen stimmt wohl nicht ganz.
[mm] R\subseteq\{1,\ldots\ }
[/mm]
heisst ja reflexiv genau dann, wenn
[mm] \forall i\in \{1,\ldots , n\}\:\: (i,i)\in [/mm] R.
Dann kannst Du aber für jedes der [mm] n^2-n [/mm] weiteren Paare (x,y) noch separat festlegen, ob [mm] (x,y)\in [/mm] R oder nicht, so dass die
Anzahl dann
[mm] 2^{n^2-n}
[/mm]
ist.
Bei den symmetrischen kann ich halt nur für 2er-Mengen (anstatt Paaren) sowie für die Paare (x,x) festlegen, ob sie drin sind oder nicht,
somit ergibt sich als Anzahl
[mm] 2^{\frac{n(n-1)}{2}+n}
[/mm]
Gruss,
Mathias
|
|
|
| |
|
Irgendwie verstehe ich da nur Bahnhof. :(
Könntest du das evtl bissel genauer erklären, wie man da drauf kommt?
LG, Raingirl87
|
|
|
| |
|
Hallo und guten Tag,
eine Relation [mm] R\subseteq\{1,\ldots ,n\}\times\{1,\ldots n\}
[/mm]
ist doch dadurch bestimmt, welche Paare (x,y) sie enthält. Wenn Du zB nach der Anzahl aller solchen Relationen fragst,
so hast Du für jedes der [mm] n^2 [/mm] Paare (x,y) die beiden Möglichkeiten [mm] (x,y)\in [/mm] R und [mm] (x,y)\not\in [/mm] R, insgesamt gibt es also
[mm] 2^{n^2} [/mm] solche Relationen.
Analog geht es dann bei Deiner Aufgabe.
Gruss,
Mathias
|
|
|
|
