Anzahl der antisymmetrischen Relationen aus 5

04.01.2012, 17:00

PPO

Anzahl der antisymmetrischen Relationen aus 5

Meine Frage:
Wie viele verschiedene antisymmetrische Relationen auf einer fünf elementigen Menge gibt es?

Meine Ideen:
Die Definition von Antisymmetrie ist ja: (xRy => yRx) => x=y für alle x,y aus M.
Für die Anzahl der symmetrischen Relationen gilt ja: $\begin{eqnarray*} 2^{\frac{n (n-1)}{2} } \end{eqnarray*}$
Allerdings soll laut Musterlösung bei dieser Aufgabe 1889568 herauskommen. Da das aber keine Zweierpotenz ist, verwirrt mich das Ganze etwas.

Überlegt hatte ich mir das eigentlich als Matrix: Antisymmetrie hieße da, dass wenn in der einen Hälfte eine 1 steht, muss im symmetrischen Gegenüber eine 0 stehen. Bei einer 0 muss ebenfalls eine 0 stehen und auf der Diagonalen ebenfalls. Daher dachte ich an auch hier an $\begin{eqnarray*} 2^{\frac{n (n-1)}{2} } \end{eqnarray*}$ , was aber nicht mit der Musterlösung übereinkommt.

04.01.2012, 17:47

mathinitus

Auf diesen Beitrag antworten »

RE: Anzahl der antisymmetrischen Relationen aus 5

Zitat:

Original von PPO
Die Definition von Antisymmetrie ist ja: (xRy => yRx) => x=y für alle x,y aus M.

Nicht ganz.

04.01.2012, 17:58

PPO

Auf diesen Beitrag antworten »

Ja, hab mich da verschrieben, meinte natürlich

(xRy $\begin{eqnarray*} \wedge \end{eqnarray*}$ yRx) => x=y für alle x,y aus M.

04.01.2012, 18:44

Leopold

Auf diesen Beitrag antworten »

Ohne Beschränkung der Allgemeinheit seien $\begin{eqnarray*} 1,2,3,4,5 \end{eqnarray*}$ die fünf Elemente von $\begin{eqnarray*} M \end{eqnarray*}$ . Eine Relation auf $\begin{eqnarray*} M \end{eqnarray*}$ ist eine Teilmenge von $\begin{eqnarray*} M \times M \end{eqnarray*}$ . Sie besteht aus Paaren $\begin{eqnarray*} (a,b) \end{eqnarray*}$ mit $\begin{eqnarray*} a,b \in M \end{eqnarray*}$ . Die Paare $\begin{eqnarray*} (a,b) \end{eqnarray*}$ und $\begin{eqnarray*} (b,a) \end{eqnarray*}$ mögen invers zueinander heißen.

Jetzt betrachten wir alle Paare $\begin{eqnarray*} (a,b) \end{eqnarray*}$ mit $\begin{eqnarray*} a \leq b \end{eqnarray*}$ . Davon gibt es $\begin{eqnarray*} 15 \end{eqnarray*}$ Stück, $\begin{eqnarray*} 5 \end{eqnarray*}$ von der Sorte $\begin{eqnarray*} (a,a) \end{eqnarray*}$ und $\begin{eqnarray*} 10 \end{eqnarray*}$ von der Sorte $\begin{eqnarray*} (a,b) \end{eqnarray*}$ mit $\begin{eqnarray*} a<b \end{eqnarray*}$ .

Für die Paare $\begin{eqnarray*} (a,a) \end{eqnarray*}$ legen wir zwei Zustände fest:
$\begin{eqnarray*} 0 \end{eqnarray*}$ für "nicht in der Relation enthalten"
$\begin{eqnarray*} 1 \end{eqnarray*}$ für "in der Relation enthalten"

Für die Paare $\begin{eqnarray*} (a,b) \end{eqnarray*}$ mit $\begin{eqnarray*} a<b \end{eqnarray*}$ legen wir drei Zustände fest:
$\begin{eqnarray*} 0 \end{eqnarray*}$ für "weder das Paar noch sein Inverses ist in der Relation enthalten"
$\begin{eqnarray*} 1 \end{eqnarray*}$ für "das Paar ist in der Relation enthalten"
$\begin{eqnarray*} -1 \end{eqnarray*}$ für "das Inverse des Paars ist in der Relation enthalten"

Ist nun $\begin{eqnarray*} R \end{eqnarray*}$ eine antisymmetrische Relation, so kann man jedem der $\begin{eqnarray*} 15 \end{eqnarray*}$ Paare seinen Zustand $\begin{eqnarray*} Z_R(a,b) \end{eqnarray*}$ zuordnen. $\begin{eqnarray*} Z_R \end{eqnarray*}$ kann mit einem $\begin{eqnarray*} 15 \end{eqnarray*}$ -Tupel identifiziert werden. Dazu ordnen wir die $\begin{eqnarray*} 15 \end{eqnarray*}$ Paare $\begin{eqnarray*} (a,b) \end{eqnarray*}$ mit $\begin{eqnarray*} a \leq b \end{eqnarray*}$ zum Beispiel lexikographisch:

$\begin{eqnarray*} \begin{matrix}(1,1) & (1,2) & \ldots & (1,5) & (2,2) & (2,3) & \ldots & (2,5) & \ldots \ldots & (5,5) \end{matrix} \end{eqnarray*}$

In dieser Reihenfolge tragen wir in das $\begin{eqnarray*} 15 \end{eqnarray*}$ -Tupel den Zustand des jeweiligen Paares ein. Die Beziehung zwischen der Menge der antisymmetrischen Relationen und den Zustandstupeln ist eineindeutig. Die Aufgabe ist daher gelöst, wenn man alle möglichen Zustandstupel gezählt hat. Das ist aber nun eine leichte kombinatorische Übung.

EDIT
Unklarheiten beseitigt

05.01.2012, 10:38

PPO

Auf diesen Beitrag antworten »

Aha, also durch die Berechnung der 5-Tupel über {0, 1} für (a, a) multipliziert mit der Anzahl der 10-Tupel über {-1, 0, 1} komme ich auf das richtige Ergebnis:

$\begin{eqnarray*} 2^5 * 3^{10} = 1889568 \end{eqnarray*}$

Allerdings verstehe ich den Zusammenhang zwischen dem Zustandstupel und der Menge der antisymmetrischen Relationen nicht so wirklich. Kannst du das noch einmal erläutern? Ich würde mir da gerne eine allgemeine Formel für aufstellen.

05.01.2012, 17:46

Leopold

Auf diesen Beitrag antworten »

In einer antisymmetrischen Relation können nicht ein Paar und sein Inverses zugleich enthalten sein (Ausnahmen sind die Selbstinversen, also die Paare $\begin{eqnarray*} (a,a) \end{eqnarray*}$ ). Deswegen die drei Zustände für die Paare $\begin{eqnarray*} (a,b) \end{eqnarray*}$ mit $\begin{eqnarray*} a<b \end{eqnarray*}$ .

Betrachten wir als Beispiel die folgendermaßen definierte Relation $\begin{eqnarray*} R_1 \end{eqnarray*}$ :

$\begin{eqnarray*} 3~R_1~2 \, ; \ \ 2~R_1~5 \, ; \ \ 4~R_1~4 \end{eqnarray*}$

Oder in Mengenschreibweise:

$\begin{eqnarray*} R_1 = \left\{ (3,2),(2,5),(4,4) \right\} \end{eqnarray*}$

Offenbar ist $\begin{eqnarray*} R_1 \end{eqnarray*}$ antisymmetrisch. Jetzt betrachten wir die Zustandsfunktion $\begin{eqnarray*} Z_{R_1} \end{eqnarray*}$ , gleich als Tupel geschrieben. Dazu ordnen wir alle Paare $\begin{eqnarray*} (a,b) \in M \times M \end{eqnarray*}$ mit $\begin{eqnarray*} a \leq b \end{eqnarray*}$ lexikographisch und tragen in der so definierten Reihenfolge die Zustände der Paare in das $\begin{eqnarray*} 15 \end{eqnarray*}$ -Tupel ein:

$\begin{eqnarray*} Z_{R_1} = \left( 0,0,0,0,0,0,-1,0,1,0,0,0,1,0,0 \right) \end{eqnarray*}$

Die $\begin{eqnarray*} -1 \end{eqnarray*}$ steht steht, weil das Inverse des Paares $\begin{eqnarray*} (2,3) \end{eqnarray*}$ , nämlich $\begin{eqnarray*} (3,2) \end{eqnarray*}$ , in der Relation vorkommt. Die $\begin{eqnarray*} 1 \end{eqnarray*}$ steht zweimal, weil nämlich die Paare $\begin{eqnarray*} (2,5) \end{eqnarray*}$ und $\begin{eqnarray*} (4,4) \end{eqnarray*}$ in der Relation vorkommen. Und die anderen Paare sind weder selbst noch invers vertreten. Daher die $\begin{eqnarray*} 0 \end{eqnarray*}$ an den restlichen Stellen.

Zu $\begin{eqnarray*} R_1 \end{eqnarray*}$ gibt es ein eindeutig bestimmtes Zustandstupel. Gebe ich dir umgekehrt ein Zustandstupel vor, so kannst du mir auch sofort die dazu gehörige antisymmetrische Relation nennen. Versuche es einmal mit

$\begin{eqnarray*} Z_{R_2} = \left( 0,-1,-1,-1,-1,0,0,0,0,0,0,0,0,1,1 \right) \end{eqnarray*}$

Dagegen ist das folgende Tupel ein ungültiges Zustandstupel. Warum?

$\begin{eqnarray*} \left( 0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0 \right) \end{eqnarray*}$

Entscheidend ist, daß die Menge der antisymmetrischen Relationen durch $\begin{eqnarray*} R \mapsto Z_R \end{eqnarray*}$ bijektiv auf die Menge der (gültigen) Zustandstupel abgebildet werden kann. Das machen die Beispiele klar. Und Bijektivität heißt Gleichmächtigkeit.

Übrigens läßt sich das Ergebnis leicht auf Mengen $\begin{eqnarray*} M \end{eqnarray*}$ mit anderen endlichen Mächtigkeiten übertragen. Du mußt dir nur überlegen, durch welchen kombinatorischen Vorgang die Zahlen $\begin{eqnarray*} r=5 \end{eqnarray*}$ und $\begin{eqnarray*} s=10 \end{eqnarray*}$ aus $\begin{eqnarray*} n=5 \end{eqnarray*}$ entstanden sind, und das verallgemeinern: $\begin{eqnarray*} 2^r \cdot 3^s \end{eqnarray*}$ ist dann die gesuchte Anzahl.

06.01.2012, 00:26

PPO

Auf diesen Beitrag antworten »

Ah, jetzt verstehe ich die Verbindung.

Zu deinen Beispielen, das wäre dann $\begin{eqnarray*} R_2 = \{(2,1), (3,1), (4,1), (5,1), (4,5), (5,5)\} \end{eqnarray*}$ bzw. Beispiel 2 ist ungültig, da für (2,2) -1 für das Inverse ungültig ist.

Dementsprechend komme ich auf die allgemeine Formel:

Seien $\begin{eqnarray*} (a,b) \in M\times M, a\leq b \end{eqnarray*}$ und $\begin{eqnarray*} |M|=n \end{eqnarray*}$ .
Dann gilt für die Anzahl der antisymmetrischen Relationen auf M:
$\begin{eqnarray*} 2^{\frac{n(n-1)}{2}} * 3^n \end{eqnarray*}$
Stimmst du da überein?

Dann bedanke ich mich für die Hilfe! :tumb:

Grüße

06.01.2012, 11:15

PPO

Auf diesen Beitrag antworten »

Ich meinte natürlich andersrum...

$\begin{eqnarray*} 2^n * 3^{\frac{n(n-1)}{2}} \end{eqnarray*}$

In meiner anfänglichen Überlegung als Matrix hatte ich die Inversen vergessen, weshalb ich nur auf eine Zweierpotenz kam.

06.01.2012, 12:36

Leopold

Auf diesen Beitrag antworten »

So stimmt das Ergebnis. Beachte aber für die Formulierung des Satzes, daß dort nur von der Menge $\begin{eqnarray*} M \end{eqnarray*}$ , ihrer Mächtigkeit und der Anzahl der antisymmetrischen Relationen die Rede sein darf. Die Paare $\begin{eqnarray*} (a,b) \end{eqnarray*}$ , egal mit welchem Zusatz, haben dort nichts verloren. Sie sind nur beweistechnisch von Interesse. Zudem haben wir im Beweis ja eine o.B.d.A.-Annahme gemacht. Die Menge der Zahlen $\begin{eqnarray*} 1,2,3,4,5 \end{eqnarray*}$ machte die Sache einfacher handhabbar. Auf einer beliebigen Menge $\begin{eqnarray*} M \end{eqnarray*}$ gibt es nicht von vorneherein eine Ordnung $\begin{eqnarray*} \leq \end{eqnarray*}$ . Man kann daher auch nicht von $\begin{eqnarray*} a \leq b \end{eqnarray*}$ sprechen.
Du kannst dir ja einmal überlegen, wozu wir überhaupt die Ordnung $\begin{eqnarray*} \leq \end{eqnarray*}$ auf der Menge der Zahlen $\begin{eqnarray*} 1,2,3,4,5 \end{eqnarray*}$ verwendet haben und wie man einen Beweis führen müßte, der ohne die o.B.d.A-Annahme auskommt.

07.01.2017, 15:09

d3fault

Auf diesen Beitrag antworten »

Die Formel für die Anzahl der antisymmetrischen Relationen stimmt.
Die Formel für die Anzahl der symmetrischen Relationen:
$\begin{eqnarray*} 2^{\frac{n (n-1)}{2} } \end{eqnarray*}$ ,
die du ganz am Anfang angibst ist falsch denke ich.

Gegenbeispiel:
Betrachte eine 3-elementige Menge A={1,2,3}, also n=3.
Laut Formel gäbe es $\begin{eqnarray*} 2^{\frac{3*2}{2} }=8 \end{eqnarray*}$ symmetrische Relationen über A.

Betrachte:
s1 = {(1,1)}
s2 = {(2,2)}
s3 = {(3,3)}
s4 = {(1,1),(2,2)}
s5 = {(1,1),(3,3)}
s6 = {(2,2),(3,3)}
s7 = {(1,1),(1,2),(2,1)}
s8 = {(1,1),(1,3),(3,1)}
s9 = {(2,2),(1,2),(2,1)}
.
.
.

Es gibt weit mehr als $\begin{eqnarray*} 2^{\frac{n (n-1)}{2} } \end{eqnarray*}$ symmetrische Relationen.
Ich komme auf folgende Formel:

$\begin{eqnarray*} 2^{\sum_{i=0}^{n}(n-i)} \end{eqnarray*}$

Neue Frage »

Antworten »

Anzahl der antisymmetrischen Relationen aus 5

Verwandte Themen