Iteracje z nierównością

[mol_ksiazkowy]

Niech \(\displaystyle{ X =\{ 1,…,n \}}\) oraz \(\displaystyle{ k \leq n}\). Udowodnić, że ilość funkcji \(\displaystyle{ f : X \mapsto X}\) takich że dla dowolnego \(\displaystyle{ x \in X}\) istnieje \(\displaystyle{ j \geq 0}\) takie, że \(\displaystyle{ f^{j}(x) \leq k}\) ( j- ta iteracja \(\displaystyle{ f}\)) jest równa \(\displaystyle{ k n^{n-1}}\)

[leg14]

Ze wzoru Cayley'a wiemy, że ilość etykietowanych lasów (złożonych z \(\displaystyle{ k}\) drzew) na \(\displaystyle{ n}\) wierzchołkach takich,że \(\displaystyle{ 1,...,k}\) naelżą do różych drzew wynosi \(\displaystyle{ k n^{n-1-k}}\). Drzewa te orietnujemy w następujący sposób:
krawędź \(\displaystyle{ (a,b)}\) dostaje orientację \(\displaystyle{ a----->b}\) jeśli b jest bliżej wierzchołka o etykiecie ze zbioru \(\displaystyle{ 1,..,k}\) niż \(\displaystyle{ a}\).

krawędź \(\displaystyle{ (a,b)}\) zorientowaną \(\displaystyle{ a---->b}\) interpretujemy jako \(\displaystyle{ f(a) =b}\) . Widać, że pozostało nam zdefiniowanie \(\displaystyle{ f(i)}\) dla \(\displaystyle{ i =1,..,k}\). Można to zrobić na \(\displaystyle{ n^k}\) sposobów.