Die folgende Aufgabe ist eine Variante einer Aufgabe aus einer Vorrunde der Mathematikolympiade des Schuljahres 1994/95.
Der Weg eines Wachmannes führt jeden Tag an der Front eines langgestreckten Gebäudes entlang. Am Ende des Gebäudes setzt er eine Meldung ab, und dann geht er seinen Weg genau wieder zurück. Er hat an der Front des Gebäudes drei Türen A,B,C jeweils genau einmal zu kontrollieren. Dabei ist es ihm freigestellt, ob er sie auf dem Hinweg zum Meldepunkt oder aber auf dem Rückweg kontrolliert. Zwei Kontrollgänge gelten als gleich, wenn er jeweils die gleichen Türen auf dem Hinweg kontrolliert hat; sonst gelten sie als verschieden.
Wie viele verschiedene Kontrollgänge gibt es?
Wie viele verschiedene Kontrollgänge gäbe es, wenn er 4 Türen zu überprüfen hätte?
Wie viele verschiedene Kontrollgänge gäbe es, wenn er n Türen zu überprüfen hätte?