Artykuł źródłowy w wersji do druku [application/pdf]: (71 KB)
Funkcje są określone wzorami
Dla każdej liczby naturalnej ustalić, ile jest funkcji dających się wyrazić jako złożenia skończenie wielu odwzorowań, z których każde jest jedną z funkcji [Dopuszczamy również złożenie puste (zero egzemplarzy funkcji ), przyjmując zwykłą umowę, że daje ono w wyniku odwzorowanie tożsamościowe ]
Rozwiązanie
Funkcja jest reprezentowana przez jej wykres - w tym przypadku układ kropek na "planszy"
(to zbiór punktów kratowych w kwadracie ), po jednej kropce na każdej linii pionowej. Stosując do takiego układu funkcję uzyskujemy przesunięcie wszystkich kropek o jednostkę w dół, z wyjątkiem tych, które już były na dolnej krawędzi; one nie zmieniają położenia. Działanie funkcji jest podobne (ruch w górę; blokada na górnej krawędzi).
Niech będą dwoma różnymi punktami zbioru takimi, że odcinek jest równoległy do przekątnej kwadratu, przy czym punkt leży na prawo i w górę od Dla takiej pary punktów niech oznacza funkcję, której wykres składa się z punktów kratowych, położonych na odcinku poziomym od lewego skraja planszy do na odcinku i na odcinku od do prawego skraja planszy (rysunek obok). Złożenie takiej funkcji z dowolną z operacji daje w wyniku znów funkcję takiej postaci lub funkcję stałą (o wykresie: wszystkie kropki na krawędzi górnej lub dolnej). Złożenie funkcji stałej z lub daje oczywiście także funkcję stałą.
Wniosek: startując od odwzorowania tożsamościowego i stosując skończenie wiele razy operacje (w dowolnej kolejności) możemy uzyskać tylko funkcje typu oraz funkcje stałe. Co ważne, każdą taką funkcję da się w ten sposób uzyskać (przykładową ewolucję przedstawia rysunek poniżej).
Pozostaje zliczyć funkcje - czyli możliwe pary punktów - oraz doliczyć funkcje stałe. Punkty mogą leżeć na przekątnej (przechodzącej przez punktów kratowych), na jednej z dwóch linii (po punktów kratowych), na jednej z dwóch linii (po punktów kratowych), itd. Liczba możliwych do uzyskania funkcji (więc funkcji stałych oraz wszystkich funkcji ) wynosi zatem