Bestimme Anzahl der Elementen < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:23 Sa 28.10.2006 | | Autor: | no-name |
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
[mm] \fedon\mixon\parallel\ [/mm] Liebe Mathematiker,
ich habe folgende Aufgabe zu lösen:
Sie x [mm] \in \IN [/mm] und [mm] M_x [/mm] := (1,...,x). Bestimmen Sie die Anzahl der
Elemente der Menge
(f : [mm] M_x \to M_3 [/mm] | f surjektive Abbildung)
Die Mächtigkeit von [mm] M_3= [/mm] (1,2,3) ist [mm] |M_3|= [/mm] 3
=> [mm] M_x [/mm] hat mindestens 3 Elemente, weil es eine surjektive Abbildung
f : [mm] M_x \to M_3 [/mm] gibt.
Wie bekomme ich aber die exakte Anzahl?
|
|
| |
|
>
> Sie x $ [mm] \in \IN [/mm] $ und $ [mm] M_x [/mm] $ := (1,...,x). Bestimmen Sie die Anzahl der
Elemente der Menge
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Ich verstehe die Menge [mm] M_x [/mm] leider nicht. Da scheint ja etwas anderes gemeint zu sein als [mm] M_x=\{1,2,...,x\}, [/mm] bei welcher man die Anzahl der Elemente sehr einfach bestimmen kann.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:42 So 29.10.2006 | | Autor: | no-name |
x ist nur eine beliebiges Element, dass herausgegriffen worden ist. Man kann auch (vielleicht exakter) schreiben:
[mm] M_n [/mm] = {1,...,n}, [mm] n\in\IN
[/mm]
|
|
|
| |
|
> Sei n [mm] \in \INund M_n [/mm] := [mm] \{1,...,n\}. [/mm]
>Bestimmen Sie die Anzahl der Elemente der Menge
> [mm] \{f : M_n \to M_3 | f surjektive Abbildung \} [/mm]
Hallo,
Du hast schon richtig erkannt, daß n [mm] \ge [/mm] 3 sein muß, damit man eine surjektive Abbildung erhalten kann.
Betrachten wir also [mm] F_3:= \{f : M_3\to M_3 | f surjektive Abbildung \}.
[/mm]
Welche Möglichkeiten gibt es für Surjektionen?
1.Möglichkeit
f(1)=1 f(2)=2 f(3)=3
2.Möglichkeit
f(1)=3 f(2)=1 f(3)=2
3.Möglichkeit
f(1)=2 f(2)=3 f(3)=1
4.Möglichkeit
f(1)=1 f(2)=3 f(3)=2
5.Möglichkeit
f(1)=3 f(2)=2 f(3)=1
6.Möglichkeit
f(1)=2 f(2)=1 f(3)=3
Also ist [mm] |F_3|=6
[/mm]
Überlegungen für den Fall n >3 finden sich in meinem Post weiter unten:
https://matheraum.de/read?i=191044#artikelmenu
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Korrektur) Korrekturmitteilung  | | Datum: | 19:30 So 29.10.2006 | | Autor: | maybe. |
> Beh.: [mm]|F_n|=2*3^{n-2}[/mm] für alle [mm]n\ge[/mm] 3.
hallo angela,
da wette ich aber dagegen!
noch mal das beispiel n=4:
nach deiner berechnung: [mm] 2*3^{2} [/mm] = 18
hat man eine surjektive abbildung von [mm] M_{4}-->M_{3} [/mm] müssen für genau genau 2 elemente von [mm] M_{4} [/mm] die Funktionswerte identisch sein.
du hast berücksichtigt, dass f(1)=f(4) oder f(2)=f(4) oder f(3)=f(4)
aber es kann doch auch f(1)=f(2) oder f(2)=f(3) oder f(1)=f(3) gelten!
das hast du bei deiner abzaehlung nicht berücksichtigt!
hier mal paar beispiele, die erste ziffer steht jeweils für f(1) usw.
1123
1132
1223
3221
usw...
das sind dann noch mal 12 fälle. der beweis per induktion hört sich gut an man bräuchte eben nur erstmal eine formel die man beweisen kann.
gruss und danke für die bemühnungen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:37 So 29.10.2006 | | Autor: | maybe. |
hier habe ich mal meinen lösungsansatz gepostet (noch bevor ich auf diesen thread gestossen bin):
https://matheraum.de/read?t=190953
|
|
|
| |
|
Hallo,
ich wage es, einen neuen Lösungsansatz Deiner kritischen Begutachtung vorzulegen:
Man habe die Menge [mm] M_n [/mm] mit n Elementen.
Damit ich die Bedingung der Surjektivität erfülle, wähle ich aus diesen n Argumenten zunächst drei aus, denen ich die Werte 1,2,3 zuordne.
Aus einer Menge von n Elementen kann man [mm] \vektor{n \\ 3} [/mm] 3-elementige Mengen auswählen.
Für jede Auswähl gibt es 6 Möglichkeiten, die Zahlen 1,2,3 zuzuordnen.
Also hat man bisher [mm] \vektor{n \\ 3}*6 [/mm] Möglichkeiten.
Hierbei sind aber die verbleibenden n-3 Argumente noch nicht berücksichtigt, für die es jeweils völlig frei und ohne Einschränkungen drei Möglichkeiten 1,2 oder 3 gibt.
Insgesamt ergeben sich [mm] \vektor{n \\ 3}*6*3^{n-3}Möglichkeiten.
[/mm]
Das wäre ggf. natürlich ordnungsgemäß zu beweisen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Korrektur) Korrekturmitteilung | | Datum: | 23:00 So 29.10.2006 | | Autor: | maybe. |
Hi,
also so habe ich es ganz am anfang versucht als ich mit der aufgabe begonnen habe, bin aber auf folgendes problem gestossen:
also mal ein beispiel für n=6:
ich hab 6 bogenschützen und 3 scheiben die ich abschiessen muss. obwohl ich weiss, dass meine schuetzen immer treffen (sie haben alle nur einen pfeil)will ich sicher gehen und such mir 3 aus die erstmal alle auf eine andere scheibe schiessen.
dazu hab ich $ [mm] \vektor{n \\ 3} [/mm] $ möglichkeiten. die 3 können dann noch unter sich ausmachen wer welche scheibe abschiesst. (3! möglichkeiten)
ergibt dann wie du sagst: $ [mm] \vektor{n \\ 3}\cdot{}3! [/mm] $
das entspricht ja dem ziehen von 3 kugeln unter beachtung der reihenfolge:
[mm] \bruch{n!}{(n-k)!}
[/mm]
na gut also ich hatte ja gesagt sei n=6. also nehm ich mir die schuetzen 1,2 und 3 und jeder schiesst die scheibe mit seiner nummer ab.
f(1)=1, f(2)=2, f(3)=3
die anderen können dann abschiessen was sie wollen.
du hast das so genannt:
> Hierbei sind aber die verbleibenden n-3 Argumente noch
> nicht berücksichtigt, für die es jeweils völlig frei und
> ohne Einschränkungen drei Möglichkeiten 1,2 oder 3 gibt.
sagen wir jetzt doch mal
f(4)=3,f(5)=2,f(6)=1
na und jetzt kommts :
an einem anderen tage such ich mir schuetze 4,5 und 6 aus und sag ihnen dass sie erstmal die 3 scheiben abschiessen sollen:
f(4)=3, f(5)=2, f(6)=1
und die anderen dürfen jetzt völlig frei drauf los ballern:
aber was wenn:
f(1)=1, f(2)=2, f(3)=3
??
na dann habe ich die selbe abbildung wie an dem ersten tage.
fazit: in deiner berechnung kommen abbildungen doppelt vor!
und eben das war auch mein problem :)
meinen lösungsansatz habe ich ja bereits gepostet, weiss aber immer noch nicht ob er richtig oder falsch ist ...
grüsse!
man ich bin mir sicher, dass ie aufgabe kein hexenwerk ist :)
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:03 So 29.10.2006 | | Autor: | maybe. |
Aufgabe
Sei $ n [mm] \in \IN [/mm] $ und $ [mm] M_{n}:=\{1,...,n\} [/mm] $
Wie viele Elemente hat $ [mm] \{f: M_{n} \to M_{3} : f \mbox{ surjektiv}\} [/mm] $?
Also ich will doch alle Abbildungen bei denen die 1, die 2 und die 3 'getroffen' werden. Also $ [mm] f(M_{n})=\{1,2,3\}. [/mm] $ Erst mal hab ich mir überlegt wie viele Abbildungen es überhaupt gibt, und dachte mir dass ich jetzt mal meine n (von 1 bis n durchnummerierten) Kugeln, also die Elemente von $ [mm] M_{n} [/mm] $ vor mir liegen habe und die jetzt in 3 verschieden Urnen werfe. (Die Urnen sind die Elemente 1, 2 und 3 von $ [mm] M_{3}). [/mm] $
Naja für die erste Kugel habe ich 3 Möglichkeiten, für die zweite auch, usw.
also: $ [mm] |\{f:M_{n} --> M_{3}\}| [/mm] $ = $ [mm] 3^{n} [/mm] $
Na gut. Jetzt dachte ich mir, ich ziehe die Möglichkeiten bei denen in mindestens einer der Urnen keine Kugel liegt einfach wieder ab:
1.Fall:
IN MINDESTENS EINER DER BEIDEN URNEN IST KEINE KUGEL AM SCHLUSS
--> alle kugeln müssen in 2 urnen verteilt werden. jetzt habe ich doch (ähnlich wie oben) $ [mm] 2^{n} [/mm] $ möglichkeiten die kugeln zu verteilen. das schliesst die beiden spezialfälle "alle in eine" und "alle in die andere urne" schon ein. Dann kann ich mir aber noch aussuchen in welchen beiden urnen alle kugeln liegen sollen. es gibt 3 möglichkeiten 2 urnen auszusuchen (anschaulicher: 3 möglichkeiten eine wegzulassen)
also haben wir $ [mm] 3\cdot{}2^{n} [/mm] $ möglichkeiten für eine nichtsurjektive abbildung
==> es gibt $ [mm] 3^{n}-3\cdot{}2^{n} [/mm] $ surjektive abbildungen.
Jetzt hätte ich aber nicht geschrieben, wenn ich mir da so sicher wäre :)
Also erstmal habe ich das ganze mal für n=4 ausprobiert:
laut formel : $ [mm] 3^{4}-3\cdot{}2^{n}= [/mm] $ 81-48 = 33
gezählt habe ich aber nur 30 :(
und dann komme ich auf keinen vernünftigen lösungsweg das ganze direkt zu berechnen (also ohne den umweg über "alle mögliche abbildungen")
das müsste sich doch per urnenmodell recht einfach berechnen lassen, ich steh aber irgendwie auf dem schlauch.
also wär super wenn mal jemand schauen kann wo mein fehler liegt und/oder mir sagt wie das ganze auch 'direkt' geht.
vielen dank schonmal
Ich habe diese Frage bereits hier:
https://matheraum.de/read?t=190953
gestellt, aber die diskussion ist jetzt hier her 'gewandert'
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:19 Di 31.10.2006 | | Autor: | marquez |
Habe dieselbe Aufgabe und eure Diskussion verfolgt. Bin auf eine Formel gestoßen, die meiner Auflistung für [mm] M_5 \to M_3 [/mm] zufolge immerhin für diese Abbildung gilt. Die Formel lautet:
[mm] 3^{n-1}+[(-1)^{n}*3]
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Fr 03.11.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
