Jak zaparkować samochód?

Rozważmy następujący

Problem. Na pewnym parkingu znajduje się $\text{[math]}$ miejsc, ustawionych w rzędzie, ponumerowanych liczbami naturalnymi $\text{[math]}$ . Każdy z parkujących tam $\text{[math]}$ kierowców ma swoje ulubione miejsce: dla $\text{[math]}$ -tego kierowcy niech będzie to miejsce o numerze $\text{[math]}$ , przy czym dla różnych kierowców miejsca te nie muszą być różne. Kierowcy przyjeżdżają kolejno na parking: kiedy $\text{[math]}$ -ty kierowca wjeżdża na parking, jedzie aż do swojego ulubionego miejsca, a następnie, jeśli jest wolne, parkuje tam, jeśli zaś jest zajęte, parkuje na następnym wolnym miejscu. Jeśli wszystkie następne miejsca są zajęte, odjeżdża. Spróbujemy określić liczbę wszystkich takich ciągów preferencji $\text{[math]}$ , że wszystkim kierowcom uda się zaparkować swoje samochody.

Ciąg $\text{[math]}$ o wyrazach w zbiorze $\text{[math]}$ będziemy nazywać funkcją parkingową długości $\text{[math]}$ , jeśli wszystkim kierowcom uda się zaparkować samochody.

Na początek zobaczmy, ile wynosi liczba funkcji parkingowych długości $\text{[math]}$ dla $\text{[math]}$ i $\text{[math]}$ . Mamy mianowicie:

(1): dla $\text{[math]}$ trzy takie ciągi: 11, 12, 21,
(2): dla $\text{[math]}$ szesnaście takich ciągów: 111, 112, 121, 211, 113, 131, 311, 122, 212, 221, 123, 132, 213, 231, 312, 321.

Problem wyznaczenia wszystkich funkcji parkingowych długości $\text{[math]}$ został rozwiązany przez Pyke’a w 1959 roku oraz niezależnie przez Konheima i Weissa w 1966 roku. Okazuje się mianowicie, że zachodzi następujące

Twierdzenie. Liczba wszystkich funkcji parkingowych długości $\text{[math]}$ wynosi $\text{[math]}$

Dowód. Zmodyfikujmy nieco nasz problem: na początku parkingu (tj. przed miejscem o numerze $\text{[math]}$ ) dodajemy miejsce o numerze $\text{[math]}$ . Ponadto pozwalamy kierowcom, którym nie udało się zaparkować zgodnie ze starymi regułami, przejechać przez parking po raz drugi, począwszy od miejsca $\text{[math]}$ , aż do pierwszego wolnego miejsca.

Oczywiście, teraz wszystkim kierowcom uda się zaparkować samochody, a jedno miejsce pozostanie wolne. Łatwo zauważyć, że ciąg $\text{[math]}$ jest funkcją parkingową wtedy i tylko wtedy, gdy po zaparkowaniu samochodów przez wszystkich kierowców miejsce $\text{[math]}$ pozostanie wolne.

Niech $\text{[math]}$ będzie dowolnym ciągiem o wyrazach w zbiorze $\text{[math]}$ . Jeśli zgodnie z tym ciągiem $\text{[math]}$ -ty kierowca zaparkuje na miejscu $\text{[math]}$ , to (dla $\text{[math]}$ ) zgodnie z ciągiem

display-math

(oczywiście modulo $\text{[math]}$ ) zaparkuje na miejscu $\text{[math]}$ .

Dla każdego ciągu $\text{[math]}$ o wyrazach ze zbioru od 1 do $\text{[math]}$ rozważmy zbiór:

display-math

Każdy taki ciąg wyznacza $\text{[math]}$ -elementowy podzbiór zbioru $\text{[math]}$ – zbiór tych miejsc, na których zaparkują kierowcy. Odwrotnie: każdy taki podzbiór jest wyznaczony przez pewien ciąg postaci $\text{[math]}$ . Oczywiście, tylko jeden $\text{[math]}$ -elementowy podzbiór zbioru $\text{[math]}$ nie zawiera liczby $\text{[math]}$ , a zatem tylko jeden ciąg z powyższego zbioru jest funkcją parkingową.

Suma wszystkich zbiorów $\text{[math]}$ jest zbiorem wszystkich ciągów długości $\text{[math]}$ o wyrazach ze zbioru $\text{[math]}$ . Liczba takich ciągów wynosi $\text{[math]}$ . Zatem liczba funkcji parkingowych długości $\text{[math]}$ musi być równa

display-math

Funkcje parkingowe, o których mowa w powyższym twierdzeniu, znalazły szereg zastosowań w kombinatoryce, a w szczególności w teorii grafów. Jako przykład można przytoczyć twierdzenie Sylvestera, Borchardta i Cayleya mówiące o tym, że liczba wszystkich lasów ukorzenionych o $\text{[math]}$ ponumerowanych wierzchołkach jest równa liczbie funkcji parkingowych długości $\text{[math]}$ .

Czytelnik może w charakterze prostego ćwiczenia spróbować wykazać, że liczba niemalejących funkcji parkingowych wynosi dokładnie

display-math

Na koniec powiedzmy, że liczby tej postaci, zwane liczbami Catalana, występują w wielu miejscach w bardzo różnych dziedzinach matematyki. Kombinatorycznie liczby Catalana można zdefiniować na ponad $\text{[math]}$ różnych sposobów. Dla przykładu, liczby Catalana to: liczba poprawnych nawiasowań przy użyciu $\text{[math]}$ par nawiasów, liczba ciągów zero-jedynkowych zdominowanych przez $\text{[math]}$ , liczba triangulacji $\text{[math]}$ -kąta wypukłego. Ale to już zupełnie inna opowieść.