Anzahl der Abbildungen

Question

Hi,

ich beschäftige mich momentan mit folgender Aufgabe:

Sei k ∈ ℕ > 0. Bestimmen Sie die Anzahl der Abbildungen f:{1,..2k} -> {1,...,k} für die gilt, dass es ein 1 ≤ y ≤ k gibt, s.d. Ιf-1(y)| > 2.

Leider finde ich bisher keinen guten Ansatz für das Thema. Bisher ist mir nur gedanke bekommen das man ja sehr viele Möglichenkeiten wenn nicht gar unendlich viele hat.

mfG

Comments

Es sind definitiv nicht endlich viele Möglichkeiten, denn es gibt genau $$|M|^|N|$$ Abbildungen f:M -> N. Was genau soll denn f-1(y) in |f-1(y)|>2 heißen? Ist das (f-1)(y), und wenn ja welche Abbildung ist 1?(Konstante Abb.?)

---

Damit ist die Kardinalität der Urbildmenge gemeint. Diese muss über 2 sein.

---

Also $$|f^{-1} (y) |$$? Wenn noch möglich besser das bitte aus, das kann man aus deinem Post kaum rausraten.

Answer 1

Es ist hier wohl das einfachste des Komplement zu berechnen. Das sind gerade die two-to-one Abbildungen, also alle Abbildungen, bei denen die Urbildmenge jeden Elements genau 2 Elemente hat. Von diesen gibt es k!/2^k Stück. Also gibt es k^{2k} - k!/2^k Abbildungen, die die gewünschte Eigenschaft haben.