Anzahl surjektiver Funktionen

12.06.2006, 14:51

violetter Halbritter

Anzahl surjektiver Funktionen

Hallo!

Frage: Wie viele surjektive Funktionen gibt es von einer a-elemetigen endl. Menge auf ein b-elementige endl. Menge?

|M| < |N| => |{M -> N, injektiv}| = |M|!/|N|!

|M| > |N| => |{M -> N, injektiv}| = 0

|M| = |N| => |{M -> N, bijektiv}| = |M|!

|M| /= |N| => |{M -> N, bijektiv}| = 0

Wie geht das jetzt mit surjektiven Funktionen? Ich hatte die Idee, das das was mit "über" also mit der Teilmenge-Anzahl-Opperation zu tun haben könnte. Hat aber irgendwie nicht gepasst.

12.06.2006, 19:09

JochenX

Auf diesen Beitrag antworten »

Hallo,

ganz einfach ist das nicht, aber erst mal gibt's eh Forum Kloppe

. Erst sind das "Mengen mit a bzw. b Elementen" und dann heißen sie plötzlich M und N und nix mehr mit a und b. !?

Naja, egal. Augenzwinkern

Sei also die Abbildungsrichtung von M in N und m und n seien deren Kradinalitäten.
Für zwei der 3 Fälle m</=/>n kannst du dir das schnell überlegen.

Für den letzten Fall hätte ich als Vorschlag, kA, ob das zu was sinnvollem führt:
überlege dir mal (Kombinatorik!), wieviele Abb. NICHT surjektiv sind.

12.06.2006, 21:40

violetter Halbritter

Auf diesen Beitrag antworten »

Klar, die Fälle m<n und m=n sind geschenkt, ich hatte nur gedacht, das ich die gleiche Formel, die für m>n gilt vielleicht auch auf die anderen beiden Fälle oder auf zu mindest auf m=n übertragbar ist.

|M| = m, |N| = n => S(m,n) := |{M -> N, surjektiv}|

$\begin{eqnarray*} S(m,n) = n^{m} - \sum_{k=1}^{n-1}~{_{k}^n*S(m,k)} \end{eqnarray*}$

OK! Aber geht das nicht auch einfacher, z B ohne so ein Summenzeichen?

12.06.2006, 21:49

violetter Halbritter

Auf diesen Beitrag antworten »

Jagut, da muss natürlich noch hinzugesagt werden, dass:

S(x,1) := 1

und nebenbei, was ich auch nicht mag, ist das auch noch reflexisiv

12.06.2006, 22:08

Auf diesen Beitrag antworten »

Also ich kenne noch die Schreibweise

$\begin{eqnarray*} S(m,n) = \sum_{k=1}^n (-1)^{n-k} {n\choose k} k^m \end{eqnarray*}$

aber die kommt - wie zu sehen ist - auch nicht ohne Summenzeichen aus. Das geübte Auge sieht natürlich an der Struktur, woher diese Formel kommt: Von der Siebformel.

13.06.2006, 12:26

violetter Halbritter

Auf diesen Beitrag antworten »

OK, die Darstellung verzichtet zumindest auf Reflexisivität.

Die Formel sieht mir danach aus als wäre sie eigentlich das was ich vorher geschrieben habe nur eingesetzt und zusammengefasst. Denn Zusammenhang mit der Siebformell sehe ich da nicht

13.06.2006, 12:46

Auf diesen Beitrag antworten »

Ich verstehe nicht, was du hier dauernd mit "reflexiv" meinst. Meinst du nicht eher "rekursiv"?

Und nach "einfach einsetzen und umformen" sieht das hier nicht bloß aus, wenn du's wirklich mal durchführst...

13.06.2006, 14:58

violetter Halbritter

Auf diesen Beitrag antworten »

Entschuldigung natürlich meinte ich "rekursiv"

Deine Formel ist für mich trotzdem noch die Formel die ich vorher geschrieben habe aber eben zum Fortschritt mit eingesetzten Werten, so dass der jetzt nicht mehr rekursiv.

Und Trotzdem sehe ich auch keinen Zusammenhang mit der Siebformel.

Ist völlig ok, die Formel, denn auf die Rekursivität konnte verzichtet werden, dass Problem ist jetzt nur noch auf das Summenzeichen zu verzichten, da aber LOED schon durchblicken lassen hat, dass er die Formel kennt möchte ich ihn gerne darum bitten mir einen Tipp zu geben wie man das Summenzeichen aussparen kann

13.06.2006, 15:10

Auf diesen Beitrag antworten »

Der Zusammenhang ist einfach der: Sei

$\begin{eqnarray*} A_k \end{eqnarray*}$ ... Menge der Funktionen $\begin{eqnarray*} f:\;M\to N \end{eqnarray*}$ , wo $\begin{eqnarray*} k \end{eqnarray*}$ nicht als Funktionswert auftaucht.

Dann ist $\begin{eqnarray*} S(m,n)=|(A_1\cup A_2\cup\ldots\cup A_n)^c| \end{eqnarray*}$ , und das schreit ja nach Siebformel.

Zitat:

Original von violetter Halbritter
Deine Formel ist für mich trotzdem noch die Formel die ich vorher geschrieben habe aber eben zum Fortschritt mit eingesetzten Werten, so dass der jetzt nicht mehr rekursiv.

Dann zeig das hier mal, ich bin da nämlich momentan zu blind dafür.

13.06.2006, 16:29

violetter Halbritter

Auf diesen Beitrag antworten »

Wenn man bei der Formel, die ich mit Hilfe des Betrachten der nicht-surjektiven Funktionen herausbekommen habe immer statt dem S(m,k) wieder die Formel einsetzt so erhält man:

$\begin{eqnarray*} S(m,n) = n^m - \sum_{k=1}^{n-1}~{n\choose k} * ( k^m - \sum_{l=1}^{k-1}~{k\choose l} * ( l^m - \sum_{p=1}^{l - 1}~{l\choose p} * ... )) \end{eqnarray*}$

durch Ausklammern erhält man und dem vereinfachen durch das (-1)^(n-k) erhält man genau die Formel die du geschrieben hast

Was ich nicht verstehe ist S(m,n) = |(A1 U A2 U A3 U .. U An)^c|, das liegt wahrscheinlich daran das ich kein Student sondern nur Schüler der 9. Klasse bin, ich frage mich da nur woher auf ein mal diese A(1-n) und das c herkommt. Nebenbei habe ich auch keinen Schimmer wann ein Funktionswert ist.

Aber egal, ich würde die Formel ja über meine vorherige herleiten.

Außerdem kann mir LOED immernoch einen Tipp zu dem weglassen des Summenzeichens geben, das mit den nicht-surjektiven Funktionen habe ich für die Formel da oben verwendet, aber der Tipp hilft mir nicht eine Formel ohne Summenzeichen aufzustellen

EDIT by therisen: Doppelpost zusammengefügt; Latex

13.06.2006, 16:49

Auf diesen Beitrag antworten »

Wenn du 9.Klasse bist, will ich dich nicht übermäßig quälen, aber von

Zitat:

Original von violetter Halbritter
$\begin{eqnarray*} S(m,n) = n^m - \sum_{k=1}^{n-1}~{n\choose k} * ( k^m - \sum_{l=1}^{k-1}~{k\choose l} * ( l^m - \sum_{p=1}^{l - 1}~{l\choose p} * ... )) \end{eqnarray*}$

zu meiner Formel oben ist noch ein gehöriger Weg: Du hast dir nämlich Doppelsummen $\begin{eqnarray*} \sum_{k=1}^{n-1}~\sum_{l=1}^{k-1} \end{eqnarray*}$ , Dreifachsummen $\begin{eqnarray*} \sum_{k=1}^{n-1}~\sum_{l=1}^{k-1}~\sum_{p=1}^{l - 1} \end{eqnarray*}$ usw. eingehandelt, die so einfach nicht aufzudröseln sind! Und genau das ist es, was ich oben gemeint habe mit dem "nicht einfach nur einsetzen". Hoffe, du weißt jetzt, was gemeint war.

Zu meinen Anmerkungen zur Siebformel: Das ist nur einfache Mengensymbolik, und das

$\begin{eqnarray*} (A_1\cup\ldots\cup A_n)^c = A_1^c\cap\ldots\cap A_n^c \end{eqnarray*}$

steht für die Menge aller Funktionen, die zu keiner der Mengen $\begin{eqnarray*} A_k \end{eqnarray*}$ gehören. Und so wie die $\begin{eqnarray*} A_k \end{eqnarray*}$ definiert wurden, sind das dann die Funktionen, wo alle $\begin{eqnarray*} n \end{eqnarray*}$ Werte aus $\begin{eqnarray*} N \end{eqnarray*}$ als Funktionswerte vorkommen. Oder einfacher ausgedrückt: die surjektiven Funktionen

EDIT: Ach ja, $\begin{eqnarray*} A^c \end{eqnarray*}$ steht einfach für die Komplementärmenge. D.h., bezogen auf eine Grundmenge $\begin{eqnarray*} \Omega \end{eqnarray*}$ (was im vorliegenden Fall die Menge aller Funktionen von $\begin{eqnarray*} M \end{eqnarray*}$ nach $\begin{eqnarray*} N \end{eqnarray*}$ ist) ist das einfach $\begin{eqnarray*} A^c:=\Omega \setminus A \end{eqnarray*}$

13.06.2006, 18:24

JochenX

Auf diesen Beitrag antworten »

Zitat:

Für den letzten Fall hätte ich als Vorschlag, kA, ob das zu was sinnvollem führt:

klingt das wirklich danach, als ob ich hier bereits großartig die Weltformel wüsste?

ich weiß nicht, wieso du meinst, ich würde sowas durchklingen lassen, ich habe einfach einen Vorschlag gemacht, dessen Idee ich für sinnvoll gehalten habe (ohne zu wissen, ob sie das auch ist)

15.06.2006, 11:51

violetter Halbritter

Auf diesen Beitrag antworten »

Mir ist gerade eingefallen:

Ist nicht:
$\begin{eqnarray*} |\{A \to B, surjektiv\}| = \frac{|\{B \to A, injektiv\}|*(|B|-|A|)^{|B|}*P}{S} \end{eqnarray*}$

mit P sei die Anzahl der Partitionen der Zahl der natürlichen Zahl |A| in |B| natürliche Zahlen (> 0)

und S sei die Summe der Produkte der Teile aller entprechenden Partitionen

Kann mir also jemand sagen ob das oben richtig ist oder wie man eine Formel für P oder S aufstellen kann?

15.06.2006, 12:07

Auf diesen Beitrag antworten »

Keine Ahnung, wie du auf diese Formel kommst, aber sie ist falsch: Gegenbeispiel |A|=3, |B|=1

Dann steht links 1 und rechts müsste P=1 und S=3 gelten, womit dort dann steht

3*(1-3)^1*1/3 = -2

Selbst eine Änderung von $\begin{eqnarray*} (|B|-|A|)^{|B|} \end{eqnarray*}$ zu $\begin{eqnarray*} (|A|-|B|)^{|B|} \end{eqnarray*}$ kann die Sache nicht retten.

15.06.2006, 12:50

violetter Halbritter

Auf diesen Beitrag antworten »

Sorry, an der besagten Stelle meinte ich:
$\begin{eqnarray*} |B|^{|A|-|B|} \end{eqnarray*}$

Hammer

15.06.2006, 12:59

violetter Halbritter

Auf diesen Beitrag antworten »

$\begin{eqnarray*} |\{A \to B, surjektiv\}| = \frac{|\{B \to A, injektiv\}|*|B|^{|A|-|B|}*P}{S} \end{eqnarray*}$
ist dann die Formel,
dann geht das auch bei diesem Fall

15.06.2006, 13:20

Auf diesen Beitrag antworten »

Ratespiel, oder was?
Warum erzählst du nicht gleich selbst, wie du auf die Formel kommst bzw. wo du sie her hastt? Und auch, inwieweit dir dieser Zusammenhang was bringt für die Berechnung dieser oder jener Größe?

15.06.2006, 13:36

violetter Halbritter

Auf diesen Beitrag antworten »

Das ist gar nicht so leicht das zu erklären wie ich auf die Formel gekommen bin.

Ich versuch's mal: Wenn man eine injektive Abbildung von A nach B "umdreht" so erhält eine "surjektive Zuordnung" für die es |B|^(|A|-|B|) Möglichkeiten gibt, diese zu einer surjektiven Abbildung zu erweitern. Leider kann man eine surjektive Abbildung auf diese Weise durch mehrere injektive umgekehrte Abbildungen erzeugen, die Anzahl entspricht dem Produkt der Anzahlen der Elemente die ein Element auf b abgebildet werden für alle b aus B. S/P soll jetzt der Durchschnitt dieser Anzahlen sein. Dadurch muss man dann teilen.

--
Ich mach mal ein neues Forum für die Formeln von P und S auf.

Neue Frage »

Antworten »

Anzahl surjektiver Funktionen

Verwandte Themen