Theorem - Parking Functions und der binomische Lehrsatz

• Involvierte Definitionen:
  • Parking Function
  • Binomischer Lehrsatz
• Veranstaltung: AlMa
• Referenz: Eigener Beweis

⠀

Theorem: Anzahl der Parking Functions durch rekursive Formel

Sei die Anzahl an Parking Functions der Ordnung . Dann gilt:

wobei .

Beweis

Sei eine beliebige Parking Function der Ordnung .
Seien die zu befüllenden Parkplätze.

Im Folgenden bezeichne die ID des letzten freien Parkplatzes. Wir beginnen unsere Betrachtung bei dem ersten Parkplatz, also .

Betrachtungen für Parkplatz

Angenommen also, es müsse nur noch das letzte Auto geparkt werden und nur noch der erste Parkplatz mit der ID stünde zur Verfügung.

• Welche Parkplatzpräferenzen sind gültig? Da der letzte freie Parkplatz ist, gibt es für das letzte Auto nur eine gültige Parkplatzpräferenz, nämlich den Parkplatz mit ID . Hätte eine Präferenz für den Parkplatz mit der ID , so wäre keine gültige PF mehr, denn der erste Parkplatz bliebe unbelegt.

  Da es nur eine gültige Präferenz gibt, zählen wir:
  .

• Welche Autos parken links des Parkplatzes ? Offensichtlich gibt es links des ersten Parkplatzes keine weiteren Parkplätze. Alle Autos (außer ) müssen also rechts von parken. Für die Verteilung der Autos haben wir daher nur eine einzige Wahl.

  Wir zählen:
  .

• Wie viele PF gibt es links des Parkplatzes ? Da es links des Parkplatzes überhaupt keine Parkplätze gibt, haben wir hier keine Wahlmöglichkeiten.

  Wir zählen:
  .

• Wie viele PF gibt es rechts des Parkplatzes ?

  Wir zählen:
  .

Besonders wichtig ist es, den Zusammenhang von zu erkennen und zu verstehen. Auf den ersten Blick mag es ausreichend erscheinen, nur zu zählen, wie viele gültige Parking Functions es links und rechts des letzten freien Parkplatzes gibt. Wir müssen darüber hinaus aber auch entscheiden, welche Autos wir den linken und rechten Parking Functions zuweisen. Haben wir eine Parking Function der Ordnung und ist der mittlere Parkplatz als einziger frei, so kann das erste Auto entweder links oder rechts des mittleren Parkplatzes parken. Entsprechend muss das zweite Auto rechts oder links des mittleren Parkplatzes parken. Es gibt also zwei Kombinationsmöglichkeiten. Das Zählen dieser Möglichkeiten muss

• ohne Beachtung der Reihenfolge (das übernehmen nämlich die Terme und )
• und ohne Zurücklegen (ein Auto kann schließlich nicht zweimal parken)

erfolgen.

Diese Betrachtungen sind ausreichend, um zu bestimmen, wie viele gültige Parking Functions es für den Sonderfall gibt, dass das letzte Auto auf dem ersten Platz parken muss.

Iterieren wir diese Betrachtung über alle Parkplätze, so erhalten wir die Anzahl der Parking Functions für den Fall,

• dass das letzte Auto auf dem ersten Parkplatz parkt;
• dass das letzte Auto auf dem zweiten Parkplatz parkt;
• dass das letzte Auto auf dem dritten Parkplatz parkt;
• …
• dass das letzte Auto auf dem -ten Parkplatz parkt

Da schließlich alle Autos geparkt werden müssen, ist jeder der Parkplätze ein gültiger Kandidat. Summieren wir über die Möglichkeiten für jeden dieser einzelnen Kandidaten, erhalten wir schließlich die Gesamtanzahl der Parking Functions der Ordnung , was zu zeigen war.

Beweis - alt und falsch

Sei eine beliebige Parking Function der Ordnung .

Sei die Präferenz des letzten Autos der PF, also .

Uns interessiert nun, wie viele Parking Functions

Um die Frage zu beantworten, wie viele Parking Functions der Ordnung es gibt, betrachten wir zunächst ein einfacheres Problem:

Sei gleich der Anzahl Autos, die auf den ersten Plätzen stehen.

Wie viele Parking Functions der Ordnung gibt es, bei denen das letzte (also das -te) Auto auf dem Platz parkt.

(Merke: Das bedeutet nicht, dass zwangsläufig . Es können auch weniger Autos auf den ersten Plätzen stehen.)

Um die Menge der gültigen Parking Functions für dieses einfachere Problem zu zählen, können wir jetzt mehrere Teilabschnitte betrachten:

• Die belegten Parkplätze:

  Wie viele Parkplatz-Kombinationen gibt es? Hier ziehen wir ohne Zurücklegen (jeder Parkplatz kann nur einmal belegt werden) und ohne Beachtung der Reihenfolge (wir möchten ja nicht wissen, welche Autos hier parken, sondern nur, welche Parkplätze belegt werden).

• **Die Anzahl **