Proposition - Anzahl aller Funktionsvorschriften

• Bewiesen durch:
  • Anzahl aller k-Permutationen mit Wiederholung
• Konstrukte/Folgerungen:
  • Anzahl aller Strategien
• Involvierte Definitionen:
  • Funktion
• Veranstaltung: AlMa
• Referenz: } AlgoMathe KE1 - Abbildungen und Mengen

⠀

Proposition: Anzahl aller Funktionsvorschriften

Sei eine Abbildung.
Seien und .

Dann gibt es genau mögliche Funktionsvorschriften.

Beweis

Beweis per k-Permutation mit Wiederholung

Sei also eine Abbildung. Nach der Definition gilt:

Und weiter

Uns interessiert nun, wie viele Funktionen es geben kann.

Angenommen seien alle unterschiedlich. Dann können wir für jedes (mit ) und (wobei eine Permutation der Zahlen bis sei) eine Funktionsvorschrift konstruieren, sodass:

Die Funktion besteht also aus den Tupeln:

Wir können jetzt auch als einziges -Tupel darstellen (wobei das der -te Stelle dem Wert zugeordnet wird):

Da jedes ist, handelt es sich um eine -Permutationen mit Wiederholung.

Die Menge aller Funktionen entspricht damit (nach der Proposition über die Anzahl aller k-Permutationen mit Wiederholung):

was zu zeigen war.

Beweis per vollständiger Induktion

Seien

• eine Menge mit
• eine Menge mit

Dann entspricht der Anzahl aller Abbildungen

Induktionsanfang

Sei , also .
Dann gilt: .

Das ist tatsächlich korrekt, es handelt sich hierbei um die leere Funktion.

(Im Kontext des Urnenexperiments bedeutet das: Wir ziehen kein einziges Mal, aber nicht zu ziehen ist schließlich auch ein Ausgang.)

Induktionsannahme

Wir nehmen an, dass der Anzahl aller Abbildungen entspricht, wobei und .

Induktionsschritt

Es ist zu zeigen, dass der Anzahl aller Abbildungen entspricht, wobei und .

Sei fest. (Im Kontext des Urnenexperiments nehmen wir uns einen Zug heraus)

Wir erstellen uns nun zwei eingeschränkte Abbildungen:

Nach Induktionsannahme gilt:

• hat genau Funktionsvorschriften
• hat genau Funktionsvorschriften

Die Menge aller Funktionsvorschriften können wir nun wie folgt schreiben:

Wobei die Disjunkte Vereinigung bezeichnet.

Für die Mächtigkeit dieser Menge gilt:

was zu zeigen war.