Anzahl fixpunktfreier Inkluasionabbildungen endlicher Mengen

03.05.2011, 01:40	Limbo86	Auf diesen Beitrag antworten »
Anzahl fixpunktfreier Inkluasionabbildungen endlicher Mengen Meine Frage: Gegeben sein zwei endliche Mengen A und B, wobei \|A\|>\|B\| sei. Ich definiere drei Funktionen f:A->B surjektiv, g:B->A injektiv und h:=g kringel f. Nun suche ich die Anzahl der Abbildungen h die fixpunktfrei sind. Offensichtlich ist h eine Inklusionsabbildung, da h:A->C wobei C ein subset von A ist. Also suche ich nach der Anzahl der fixpunktfreien Inklusionsabbildungen endlicher Mengen. Ich bin für alle Hinweise/Links dankbar, mir fehlt jeglicher Ansatz wie ich das Problem anpacken kann. Mir hilft Alles, ich bin wirklich am Ende meines Lateins. Meine Ideen: Die Anzahl möglicher der surjektiven Abbildungen ist $\begin{eqnarray} \|B\|! \cdot S_{\|A\|,\|B\|} \end{eqnarray}$ . Wobei $\begin{eqnarray} S_{\|A\|,\|B\|} \end{eqnarray}$ die Stirlingzahlen zweiter Art bezeichnen. Die Anzahl möglicher injektiver Abbildungen ist $\begin{eqnarray} \frac{\|A\|!}{(\|A\|-\|B\|)!} \end{eqnarray}$ . Habe ich hier http://wiki.infostudium.de/wiki/Abbildung so gefunden. Da es aber die Elemente von B für die Abbildung h nicht interessieren, können diese beliebig permutiert werden ohne h zu affektieren. Also ist die Anzahl möglicher Injektionsabbildungen: $\begin{eqnarray} \frac{\|A\|!}{(\|A\|-\|B\|)!} \cdot S_{\|A\|,\|B\|} \end{eqnarray}$ Aber sobald die Fixpunkte ins Spiel kommen schlagen alle meine Ideen fehl. Ich habe das Problem auch schon für kleine Werte berechnet und in die OEIS-Datenbank eingegeben, leider ohne Erfolg.
03.05.2011, 11:42	René Gruber	Auf diesen Beitrag antworten »
Verzwicktes Problem, in der Tat. Ein (völlig unausgereifter) Gedanke: Es wird ja $\begin{eqnarray} h(A)=C \end{eqnarray}$ gefordert. Da könnte man sich vorstellen, beim Zählen eine Fallunterscheidung hinsichtlich aller nichtleeren Teilmengen $\begin{eqnarray} D \end{eqnarray}$ von $\begin{eqnarray} C \end{eqnarray}$ mit $\begin{eqnarray} h(C)=D \end{eqnarray}$ durchzuführen, und anschließend über all diese Fälle zu summieren: Man zählt also zu festem $\begin{eqnarray} D \end{eqnarray}$ zunächst, wieviel fixpunktfreie surjektive Abbildungen $\begin{eqnarray} h_1:\;C\to D \end{eqnarray}$ es gibt. () Anschließend multipliziert man das ganze mit der Anzahl der Abbildungen $\begin{eqnarray} h_2:\;A\setminus C\to C \end{eqnarray}$ mit der Eigenschaft $\begin{eqnarray} C\setminus D \subseteq h_2(A\setminus C) \end{eqnarray}$ . () () kann man mit Siebformel ausrechnen, da dürfte so eine Art "abgebrochene" Stirlingzahl herauskommen. () hingegen ist vom selben Typ wie unsere Ausgangsfragestellung, nur mit "kleineren" Mengen ( $\begin{eqnarray} (C,D) \end{eqnarray}$ statt $\begin{eqnarray} (A,C) \end{eqnarray}$ ). Diese Idee ermöglicht eine (allerdings monströse) Rekursion, mit der dir vermutlich nicht sehr geholfen ist.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »