Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Induktion: Anzahl injektiver Abbildungen

Induktion: Anzahl injektiver Abbildungen

Universität / Fachhochschule

Tags: Abbildung, injektiv, Vollständig Induktion

LisaTPunkt aktiv_icon

17:21 Uhr, 06.02.2012

Seien A und B endliche Mengen, mit k := Anzahl Elementen von A kleiner gleich n:= Anzahl Elementen von B. Zeigen Sie mit Hilfe der Induktion, dass die Menge {f: A->B : f injektiv} der injektiven Abbildung von A ->B genau $\frac{n!}{(n - k)!}$ Elemente enthält.

Als ich die Aufgabe zuerst gelesen habe stand ich total auf dem schlau. Ich habe jetzt ein paar Überlegungen gemacht.
Fü den Induktionsanfang habe ich k und n= 1 gesetzt.
Wenn im Definitionsbereich und Wertebereich sich nur ein Element befinde, dann gibt es auch nur eine mögliche injektive abbilung. Der Anfang ist richtig. Aber mit dem nächsten Schritt komme ich nicht weiter. Vielleicht kann mir ja einer helfen?

hagman aktiv_icon

23:01 Uhr, 07.02.2012

Problem: Sollte man Induktion nach

k

oder Induktion nach

n

machen?
Und zählt bei euch

\emptyset

etwa nicht zu den endlichen Mengen?

Ich halte es für einfacher, Induktion nach

k

zu betreiben:
Anfang:

k = 0 :

Dann ist

A = \emptyset

und es gibt genau eine Abbildung

A \to B

(und die ist injektiv).
Induktionsvoraussetzung: Es gelte, dass

{f : A \to B | f

injektiv

}

genau

\frac{n!}{(n - k)!}

Elemente enthält sofern

| A | = k

und

| B | = n \geq k

Seien jetzt

A, B

Mengen mit

| A | = k + 1, | B | = n \geq k + 1

.
Zu zeigen ist, dass es

\frac{n!}{(n - k - 1)!}

injektive Abbildungen

A \to

gibt.
Wegen

k + 1 > 0

ist

A \neq \emptyset

. Sei

a_{0} \in A

ein beliebiges Element. Setze

A' = A \ {a_{0}}

.
Nach Induktionsvoraussetzung gibt es genau

\frac{n!}{(n - k)!}

injektive Abbildungen

A' \to B

.
Wir können jedem injektiven

f : A \to B

die Einschränkung auf

A'

zuordnen, also eine injektive Abbildung

g : A' \to B

.
Hierbei wird jedes injektive

g : A' \to B

genau

(n - k)

Mal getroffen, da zu gegebenem

g

ein

f

durch Angabe von

f (a_{0}) \in B \ g (A')

bestimmt wird.
Somit gilt

| {f : A \to B | f

injektiv

} | = (n - k) \cdot | {g : A' \to B | g

injektiv

} |

= (n - k) \cdot \frac{n!}{(n - k)! = \frac{n!}{(n - k - 1)!}}

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

971688

971214

	Status: nicht eingeloggt	Noch nicht registriert?