Proposition - Anzahl aller injektiven Funktionsvorschriften

• Bewiesen durch:
  • Rückbezug auf Anzahl aller Funktionsvorschriften
  • Anzahl aller k-Permutationen ohne Wiederholung
• Involvierte Definitionen:
  • Funktion
  • Abbildung
  • Injektivität
  • Permutation
  • Fakultät
• Veranstaltung: AlMa
• Referenz:
  • } AlgoMathe KE1 - Abbildungen, Permutationen, Fakultät

⠀

Proposition: Anzahl aller injektiven Funktionsvorschriften

Sie eine injektive Abbildung. Seien und .

Dann gibt es insgesamt

mögliche Funktionsvorschriften.

Beweis

Beweis per k-Permutation ohne Wiederholung

Vorbetrachtungen

Seien
Seien .

In dem Beweis über die Anzahl aller Funktionsvorschriften per k-Permutation mit Wiederholung haben wir bereits gezeigt, dass wir eine Funktionsvorschrift wie folgt konstruieren können:

Sei der Index der Variablen .
Sei der Index der Variablen .

Dann können wir als Tupelmenge

interpretieren. Also: .

Transfer zu injektiven Funktionen

Wie in der Proposition über die Anzahl aller Funktionsvorschriften können wir als einzelnes Tupel

darstellen. Da injektiv ist, gilt .

Die Menge aller injektiven Funktionsvorschriften ist also:

Die Kardinalität dieser Menge ist nur noch von den abhängig, denn enthält genau so viele Tupel wie es Kombinationen von gibt mit . Wir können daher auch schreiben:

Wobei der letzte Schritt mithilfe der Proposition über die Anzahl aller k-Permutationen ohne Wiederholung folgt.

Beweis per vollständiger Induktion

Sei

• eine surjektive Funktion.

Es ist zu zeigen, dass die Anzahl der möglichen Funktionsvorschriften

ist.

Induktionsanfang

Sei , also .

So gibt es eine mögliche Abbildung: die leere Funktion und es gilt

Der Anfang hält, da das leere Produkt 1 ist.

Induktionsannahme

Für ein mit gelte:

Induktionsschluss

Es ist zu zeigen, dass für weiterhin

Sei . Wir können wieder zwei Teilfunktionen splitten:

Für gibt es nun Möglichkeiten. Für gibt es nun Möglichkeiten.

Möchten wir beide zusammenführen, ist die Injektivität so jedoch nicht mehr gewahrt.

Daher müssen wir das in genutzte Element aus der Zielmenge entfernen.

Das tun wir und wird daher zu:

(wir schreiben hier , weil wir die Anzahl möglicher Ziel-Elemente um verringert haben)

Das entspricht bereits fast dem zu zeigenden Term, lediglich der Startindex ist noch falsch.

Jetzt können wir wieder die Menge

bilden.

Und für die Mächtigkeit dieser Menge gilt:

wir haben hiermit den Startindex wieder auf gesetzt und erhalten, was zu zeigen war.