endliche mengen

Neue Frage »

petrov Auf diesen Beitrag antworten »
endliche mengen
Hallo, hab grosses problem mit folgender aufgabe !!

es seien n element N und A eine endliche Menge mit |A| = n

sei weiter S := {f: A -> A| f bijektiv} die Menge aller bijektiven Abbildungen von A nach A und P(A) die Potenzmenge von A. Für welche n element N gilt; |S| > |P(A)| ? (als Vorraussetzung darf |S| = n! verwendet werden)

Bitte um schnelle Hilfe

danke
mfg petrov
Leopold Auf diesen Beitrag antworten »

Jetzt mußt du nur noch wissen, daß



ist. Kennst du die entsprechende Formel?
petrov Auf diesen Beitrag antworten »

daran scheitert ja die ganze sache :-) !! bin erstsemestler und hab jetzt am anfang voll probleme mit LA !! hoff du kannst mir weiterhelfen ...
Leopold Auf diesen Beitrag antworten »

Ist , so gilt .

Beweis z.B. mit vollständiger Induktion oder so
petrov Auf diesen Beitrag antworten »

sorry wenn ich vielleicht auf dem schlauch sitz, aber wie mach ich das mit der vollst. Ind. !! bzw. wie beweise ich damit die ungleichung ??
könntest mir vielleicht mal den anfang (ansatz) aufschreiben ??

mfg petrov
Leopold Auf diesen Beitrag antworten »

Der Beweis mit Induktion geht so:


:
hat kein Element, ist also die leere Menge. Die Potenzmenge von besitzt dann genau ein Element, nämlich die leere Menge. Da , gilt die Formel also im Fall .


Gelte nun die Formel für ein konkretes . Dann ist nachzuweisen, daß sie auch für gilt.

Sei also eine Menge mit Elementen. Wir zeichnen ein Element aus.
Die Teilmengen von teilen wir in zwei Kategorien ein:

Kategorie I: Teilmengen, die enthalten
Kategorie II: Teilmengen, die nicht enthalten

Und jetzt ist es ein Leichtes, mit der Induktionsvoraussetzung zu begründen, daß zu jeder Kategorie Teilmengen gehören.

Das will ich aber dir überlassen ...
 
 
petrov Auf diesen Beitrag antworten »

was meinst du mit der aussage: " Da A, gilt die Formel .."
sorry ich kann mit der aufgabe rein gar nichts anfangen. ist die begründung das für n=0 2hochn=1 ist und n! auch 1 ist ?? aber wie komm ich dann drauf für welche n gilt: |S|>|P(A)| ??

ist dir die LA am anfang auch so schwer gefallen, oder mach ich das falsche studium ?=?

petrov
Leopold Auf diesen Beitrag antworten »

Also im Moment sind wir bei der Aussage



Diese soll mit Induktion bewiesen werden.

Ist diese erst einmal bewiesen, dann ist zu überprüfen, für welche die Ungleichung



gilt.

Wenn du hier die ersten einsetzt, siehst du schnell, ab welchem das richtig ist. Und dann mußt du nur darauf hinweisen, daß bei steigendem links immer ein Faktor , rechts dagegen nur ein Faktor 2 hinzukommt.


Zu deiner Frage, ob ich LA auch als schwer empfunden habe.
Das ist leider schon Jahrzehnte her, so daß ich das nicht mehr so genau weiß. In Erinnerung ist mir nur noch, daß ich am Anfang auch nicht viel verstanden habe, aber einfach nur, weil so vieles auf einmal kam. In den Weihnachtsferien habe ich mich hingesetzt und bin meine Aufzeichnungen durchgegangen. Auf einmal ist der Groschen gefallen.

Ich glaube, Mathematik ist in gewisser Hinsicht ein sehr grausames Studium. Denn wer nicht dafür geeignet ist, merkt das sehr schnell. Ich empfehle dir, zunächst nicht aufzugeben, sondern dich hinzusetzen und das Ganze Zeile für Zeile durchzukauen, bis der Groschen fällt. Wenn der Groschen aber vor Beginn des zweiten Semesters immer noch nicht gefallen ist, solltest du nüchtern und ohne an dir selbst zu verzweifeln eine Entscheidung fällen ...
petrov Auf diesen Beitrag antworten »

ich studier ja informatik und nicht mathe aber anfangs hat man eben ziemlich viel mathe (LA HM und WT). aber ab dem 3. semester fällt das dann razs :-).
ok ich denke/hoffe das wird reichen !! ich beiss mich nochmal in die aufgabe rein! danke für alles.
Informatikstudent Auf diesen Beitrag antworten »

Zitat:
Original von Leopold
Der Beweis mit Induktion geht so:


:
hat kein Element, ist also die leere Menge. Die Potenzmenge von besitzt dann genau ein Element, nämlich die leere Menge. Da , gilt die Formel also im Fall .


Gelte nun die Formel für ein konkretes . Dann ist nachzuweisen, daß sie auch für gilt.

Sei also eine Menge mit Elementen. Wir zeichnen ein Element aus.
Die Teilmengen von teilen wir in zwei Kategorien ein:

Kategorie I: Teilmengen, die enthalten
Kategorie II: Teilmengen, die nicht enthalten

Und jetzt ist es ein Leichtes, mit der Induktionsvoraussetzung zu begründen, daß zu jeder Kategorie Teilmengen gehören.


Hallo, ich verzweifele gerade an dieser Aufgabe, also am Beweis, dazu mal ne Frage: Du sagst, daß zu jeder Kategorie Teilmengen gehören, aber dann wäre die Mächtigkeit doch 2x ?
Informatikstudent Auf diesen Beitrag antworten »

Ups, hab's grad' kapiert, ist ja für n+1 Hammer
Guest Auf diesen Beitrag antworten »

also ich versteh dass, wenn a nicht elemnt der teilmengen ist es 2^n teilmengen sind, aber nicht warum es 2^n teilmengen sind, wenn a element dieser teilmengen ist.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »