 |
 |
 |
 |
 |
 |
Startseite » Forum » Anzahl der Relationen
Anzahl der Relationen
Universität / Fachhochschule
Mengentheoretische Topologie
Tags: Mengentheoretische Topologie
 
|
  |
|---|
|
Es seien A und endlichen Mengen. Wie kann man die Anzahl der Relationen 2^(AxB) in Abhängigkeit von und mit folgenden Eigenschaften: ist rechtseindeutig ist rechtseindeutig aber nicht linkstotal ist linkstotal oder nicht rechtseindeutig Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
|
|
|
Eine Idee zu Sei und . Rechtseindeutig bedeutet, dass jedes Element in höchstens einmal getroffen werden darf. Nun kann jede mögliche Teilmenge von Bild einer Relation sein. Da gibt es erstmal verschiedene Teilmengen. Und jede davon hat irgendwo zwischen 0 und Elemente. Weine ich eine dieser Teilmengen herausgreife, etwa eine mit Elementen.dann gibt es gerade über verschiedene. Die Elemente einer solchen Teilmenge haben irgendwo in A ihre Urbilder. Weil keine Linkseindeutigkeit gefordert ist, kann jedes der Bildelemente a verschiedene Urbilder haben. Da gibt es für jede k-elementige Bildmenge also verschiedene Möglichkeiten, sprich Relationen, welche genau diese Bildmenge rechtseindeutig treffen. Das liefert für alle über k-elementigen Bildmengen insgesamt über Relationen. Die Gesamtzahl der Relationen ist dann die Summe dieses Ausdrucks über alle möglichen also von 0 bis . für Seien alle Relation auf gegeben, wobei A und endliche Mengen sind mit und . Dann sind alle Relationen linkstotal, bei denen jedes Element aus in mindestens einem Paar vorkommt, aber egal in wievielen sonst noch. Wenn man jetzt ein beliebiges Element aus A nimmt, dann kann es maximal mit Elementen aus verknüpft sein. Wenn dann alle Paare mit als erster Komponente betrachtet werden, dann können die Elemente aus jeder beliebigen Teilmenge von außer der leeren Menge die zweiten Komponenten dazu bilden. Dafür gibt es Möglichkeiten (Eins weniger als die Anzahl der Teilmengen von . Das sollte für jedes Element von A gelten. Für gibt es verschiedene Möglichkeiten, es mit Partnern zu versorgen, für auch, usw. für alle a Elemente aus A. Als Gesamtzahl hat man demnach Möglichkeiten. Was meint ihr? Und was ist mit ? |
 |
|
Hallo, zu a) rechtseindeutig heißt ja, dass zu jedem Element aus maximal ein Element aus zugeordnet wird. Es gibt zu jedem je Teilmengen mit Elementen. Jedem dieser Elemente kann jedes Element aus zugeordnet werden, was Relationen mit Elementen ergibt, aufsummert über alle bekomme ich so (ohne Gewähr ;-)). Gruß ermanus |
1483626
1483501