Kann es sein das sich in der Musterloesung ein Fehler eingeschlichen hat ?

Aufgabe 4
es sei A={1,2,3} B={u,v,w} C={0,1}
a)
Wieviele ternaere Relationen gibt es ueber A,B,C ?

da muesste meiner Meinung nach das Ergebnis 3^18 sein
und nicht 2^18.

Liege ich da richtig oder irre ich mich ?

Das scheint mir eigentlich richtig zu sein..
Erläuterung:

unter einer ternären Relation versteht man eine Teilmenge des Karthesischen Produkts dreier Mengen (hier A, B, C). Wieviele Solche Teilmengen kann es geben? Nun, zählen wir doch mal alle Elemente auf: Aus der ersten Menge gibt es 3 Elemente, aus der zweite ebenfalls 3, aus C kommen nur 2 Elemente, es gibt also
3*3*2 Tripel der Form (a, b, c) € AxBxC
Für die Relation ist es jetzt entscheident, ob jedes einzelne mögliche solches Element darin ist, bei jedem Element gibt es genau 2 Möglichkeiten: drin, oder draußen. Also ergibt sich für die Anzahl verschiedener Relationen 2^18 Möglichkeiten [img]http://www.fb18.de/gfx/23.gif[/img]

ah ok,
da war ich mit meiner Vermutung wohl auf dem Holzweg…

danke.

Ok scheinbar bin ich zu bloed…

z.B.
gegeben sei A=|7| B=|3|

Wieviele surjektive Abbildungen A->B gibt es ?

Die Lsg is sicherlich banal, mir leider aber vollkommen unergruendlich..

Dieser Kombinatorik-Scheiss macht mich noch wahnsinnig..[img]http://www.fb18.de/gfx/28.gif[/img]

Wenn du sagen wolltest:
gegeben sei |A| = 7 |B| = 3 (dass A also 7 Elemente hat, und B 3), dann sind das alle Funktionen, die Auf A definiert sind und alle Werte in B abdecken, es gibt für das erste Element aus a also 3 Möglichkeiten, für a2 noch 2, und für a3 noch eine Möglichkeit, zugeordnet zu werden. Und a4-a7 sind beliebig abzubilden, d.h. 3*2*1*3*3*3*3 = 3! * 3^4

Ich hoffe, ich habe nix vergessen, vielleicht muss da auch noch ein Faktor von (7 über 3) rein, hab gerade keine Lust, darüber nachzudenken

ha, na dann ist das ja wirklich einfach.

ah, jetzt hab ich es gefunden…

Man berechnet die Stirlingnummer der zweiten Art und multipliziert mit |B|!….

Wenn du sagen wolltest:
gegeben sei |A| = 7 |B| = 3 (dass A also 7 Elemente hat, und B 3), dann sind das alle Funktionen, die Auf A definiert sind und alle Werte in B abdecken, es gibt für das erste Element aus a also 3 Möglichkeiten, für a2 noch 2, und für a3 noch eine Möglichkeit, zugeordnet zu werden. Und a4-a7 sind beliebig abzubilden, d.h. 3*2*1*3*3*3*3 = 3! * 3^4

Ich hoffe, ich habe nix vergessen, vielleicht muss da auch noch ein Faktor von (7 über 3) rein, hab gerade keine Lust, darüber nachzudenken

Das würde ich auch so sagen. (7 über 3) muß rein, damit die 3*2*1 beliebig auf den Elementen von A sitzen kann.

Um die erste Frage noch anschaulicher zu machen:
Die Menge M = AxBxC hat eine Kardinalität von 18 und gefragt ist nach der Anzahl der Elemente der Potenzmenge dieser Menge.
Und die ist immer 2^|M|.

Dieser Kombinatorik-Scheiss macht mich noch wahnsinnig..[img]http://www.fb18.de/gfx/28.gif[/img]

ich find das dagegen recht spannend, hab das auch mal angeschaut, und dann hats auch gleich ein paar stunden gedauert ;),

also das einfache ergebnis wie bisher prophezeit klappt ja schon nicht mal bei 3 elemente -> 2 elemente (6 möglichkeiten),

ein anderer weg (den ich jetzt aus langeweile ausfürlich darstelle [img]http://www.fb18.de/gfx/23.gif[/img]):
man schaut sich die mächtigkeit der bildmengen an

für 3->2
1.möglichkeit:
bild 1: 1 urbild
bild 2: 2 urbilder

2. möglichkeit
bild 1: 2 urbilder
bild 2: 1 urbild

das ergibt für die 1. möglichkeit (3 über 1) funktionen,
für die 2. möglichkeit (3 ü 2) funktionen

macht zusammen 6 stück,


schaut man sich weitere n -> 2 an,
z. b. 5 -> 2

so ergibt sich
1.möglichkeit:
bild 1: 1 urbild
bild 2: 4 urbilder

2. möglichkeit
bild 1: 2 urbilder
bild 2: 3 urbilder

3.möglichkeit:
bild 1: 3 urbild
bild 2: 2 urbilder

4. möglichkeit
bild 1: 4 urbilder
bild 2: 1 urbilder

funktionen: (5 ü 1) + (5 ü 2) + (5 ü 3) + (5 ü 4) = 30


also für allgemeines n -> 2 immer alle möglichen (n ü irgendwas) bis auf (n ü 0) und (n ü n),

damit kriegt man die allgemeine formel für die anzahl der funktionen für n -> 2:
alle (n ü irgendwas) - (n ü 0) - (n ü n)
= 2^n - 1 -1
= 2^n-2



nun geht der spass für n -> 3 los, wird ne ganz andere formel,

beispiel 7 -> 3 [img]http://www.fb18.de/gfx/22.gif[/img]

1.möglichkeit:
bild 1: 1 urbild
restliche 6 urbilder auf die anderen beiden bilder verteilt

2.möglichkeit:
bild 1: 2 urbilder
restliche 5 urbilder auf die anderen beiden bilder verteilt

…

5.möglichkeit:
bild 1: 5 urbilder
restliche 2 urbilder auf die anderen beiden bilder verteilt


ergibt an anzahl der funktionen:
(7 ü 1) * anzahl von (6 -> 2) +
(7 ü 2) * anzahl von (5 -> 2) +
(7 ü 3) * anzahl von (4 -> 2) +
(7 ü 4) * anzahl von (3 -> 2) +
(7 ü 5) * anzahl von (2 -> 2)

=
(7 ü 1) * (2^6 - 2) +
(7 ü 2) * (2^5 - 2) +
(7 ü 3) * (2^4 - 2) +
(7 ü 4) * (2^3 - 2) +
(7 ü 5) * (2^2 - 2)

da sieht man auch wieder fast alle (7 über irgendwas), zusammen mit den 2er potenzen könnte das eine binominalentwicklung von (1+2)^7 sein, die ganzen (-2) kann man mit den fast allen (7 über irgendwas) zu 2^7 * (-2) zusammenfassen, und so kriegt man mit ein bisschen erweitert und kürzen

= (1+2)^7 - 2^7 * (-2) - 2^7 + 3
= 3(3^6-2^7+1)

(= 1806 übrigens)

die allgemeine formel ist dann 3(3^(n-1)- 2^n + 1), hat auch schon 2 weitere tests bestanden ;)

Hey Slater, gibts auch irgendwas, was du nicht kannst? [img]http://www.fb18.de/gfx/25.gif[/img]

na wozu studier ich denn noch [img]http://www.fb18.de/gfx/24.gif[/img]

Wahrscheinlich liest den Thread sowieso keiner mehr, aber falls doch will ich noch ein bisschen mehr Verwirrung stiften [img]http://www.fb18.de/gfx/22.gif[/img]

Also: Das mit 3*3*3*3*3*2*1*(7 ueber 3) find ich nicht so wahnsinnig gluecklich. Mir ist zwar klar, wie es gedacht ist (man zeichnet sozusagen drei Elemente speziell aus, die dann 3*2*1 "sind"), aber davon auf die Loesung zu schliessen finde ich zum einem nicht ganz offensichtlich (vielleicht bin ich auch nur zu dusselig…) zum anderem ist das Ergebnis aber auch falsch, denn es soll 1806 rauskommen (siehe auch Slaters Ergebnis).

Ich haette folgende Loesungsidee anzubieten:

Man guckt sich an wieviele Moeglichkeiten es gibt ueberhaupt 7 auf 3 Elemente abzubilden (das sind 3^7) davon zieht man nun die Moeglichkeiten ab, die nicht surrjektiv sind, d.h. zuerst die Moeglichkeiten dass alle 7 Elemente auf nur eins der Drei Elemente abgebildet werden (das sind drei Moeglichkeiten), dann zieht man noch die Moeglichkeiten ab, dass alle 7 Elemente nur auf zwei der drei Elemente abgebildet werden, dass sind dreimal 2^7 Moeglichkeiten.
Eine Sache ist nun (leider - vergisst man leicht) noch zu beachten. In den 2^7 Moeglichkeiten die 7 auf 2 Elemente abzubilden sind auch jeweils 2 Moeglichkeiten drin alle 7 auf 1 Elemente abzubilden, aber das haben wir eben schon abgezogen. Insgesamt muessen wir also rechnen:

3^7 - 3 - 3*(2^7 - 2) = 3^7 - 3*2^7 + 3

Nocheinmal zusammengefasst:
3^7 - Die Moeglichkeiten 7 auf drei Elemente abzubilden
3 - Die drei Moeglichkeiten alle 7 auf nur ein Element
einer drei Elementigen Menge abzubilden
2^7 - 2 - Die Moeglichkeiten sieben Elemente auf genau zwei Elemente abzubilden (2^7 waeren alle Moeglichkeiten sieben auf zwei Elemente abzubilden, d.h. inkl. der beiden Moeglichkeiten alle 7 auf nur ein Element abzubilden)

Ergebnis obiger Rechnung: 1806

Cheers,
Frank

mist, ich wusste dass es auch einen einfachen weg gibt,

aber egal, wie im fussball, am ende zählt nur das ergebnis [img]http://www.fb18.de/gfx/10.gif[/img]

Kombinatorik wahr schon im abitur das einzige was ich nicht wirklich mochte oder eher gesagt ich fand es interessant aber habe mich immer genau für die falsche Methode entschieden irgend was zu berechnen

Dennoch scheint es mir ihr habt vergessen, dass ein Element gar nicht abgebildet werden muss.
Sei A={1,2,3,4,5,6,7}
B=[a,b,c}
und f:A->B

dann ist f(1)=a, f(2)=b, f(4)=c auch eine surjektive. Abbildung oder nicht? Meiner Meinung nach wird aber dieser Fall von keine der genannten Lösungen berücksichtigt. Falls ich falsch liege habe ich ja noch 4 tage zeit :)

dann ist f(1)=a, f(2)=b, f(4)=c auch eine surjektive. Abbildung oder nicht? Meiner Meinung nach wird aber dieser Fall von keine der genannten Lösungen berücksichtigt.

Dann wäre es ja auch keine Abbildung von A nach B, wie es in der Aufgabenstellung gefordert war.

Definition:
Eine Abbildung (Funktion) ist eine eindeutige Relation einer Menge A auf eine Menge B bei der jedem Element aus A genau ein Elemnt der Menge B zugeordnet wird.

Oh ja du hast recht. Ich war der Meinung egwesen auf Seite 62 des Scriptes von Andreae sei ein Beispiel gewesen wo nicht jedem Element ein Bild zugeprdnet wurde. Lag aber voll daneben.
Sorry :(