Funksiyaların Kommutasiyası

İki funksiya $\mathbf{f}$ və $\mathbf{g}$ (\mathbf{f}, \mathbf{g}: \mathbf{X} \rightarrow \mathbf{X}) yalnız və yalnız hər bir $\mathbf{x}$ üçün \mathbf{f}(\mathbf{g}(x)) = \mathbf{g}(\mathbf{f}(x)) bərabərliyi ödənərsə, kommutativ adlanır. Məsələn, \mathbf{f}(x) = x+1 və \mathbf{g}(x) = x-2 funksiyaları kommutativdir, amma \mathbf{f}(x) = x+1 və \mathbf{g}(x) = 2x funksiyaları kommutativ deyil.

Hər bir $\mathbf{h}$ funksiyası (\mathbf{h}: N_n \rightarrow N_n, burada N_n = \{1, 2, \ldots, n\} və $n$ müsbət tam ədəddir) qiymət siyahısı ilə ifadə oluna bilər—burada siyahının $i$-ci elementi $\mathbf{h}(i)$-yə bərabərdir. Məsələn, \mathbf{h}(x) = \lfloor x/2 \rfloor funksiyası üçün N_5-dən N_5-ə qiymət siyahısı [1, 1, 2, 2, 3] olur.

Qiymət siyahıları leksikoqrafik qaydada sıralanır: [a_1, \ldots, a_n] siyahısı yalnız və yalnız elə bir $k$ indeksi mövcud olduqda [b_1, \ldots, b_n]-dən kiçik sayılır ki, a_k < b_k və bütün l < k üçün a_l = b_l.

$\mathbf{f}$ (\mathbf{f}: X \rightarrow X) funksiyası yalnız və yalnız $X$-də hər bir $y$ üçün dəqiq bir $x$ tapılıb \mathbf{f}(x) = y bərabərliyi ödənərsə, bijektiv adlanır.

Verilmiş bir bijektiv funksiya $\mathbf{f}$ üçün (\mathbf{f}: N_n \rightarrow N_n, burada $n$ müsbət tam ədəddir), $\mathbf{f}$ ilə kommutasiya edən və qiymət siyahısı leksikoqrafik olaraq ən kiçik olan bir $\mathbf{g}$ funksiyasını tapın.