Proposition - Reihenfolge spielt für Parking Functions keine Rolle

• Bewiesen durch:
  • Parking Function als Mengenabschätzung
• Involvierte Definitionen:
  • Parking Function
  • Definition - Permutation
• Veranstaltung: AlMa
• Referenz: Eigener Beweis

⠀

Proposition: Reihenfolge spielt für Parking Functions keine Rolle

Sei eine Parking Function.

Sei eine Permutation der Zahlen bis . Dann ist auch

eine Parking Function.

Beweis

In Aufgabe E1.3 (b) haben wir festgestellt, dass es sich bei einem Tupel genau dann um eine PF handelt, wenn

Die Einträge des Tupels finden hier Eingang durch die Menge

Da Mengen grundsätzlich unsortiert sind, gilt

und damit:

was zu zeigen war.