# Set of all functions from a finite set to a finite set

1. We consider the set $\mathbb{J}$ of all functions $f_i: \{1,2,...,n \} \to \{1,2,...,n \}$, where $n \in \mathbb{N}, i \in \{1,2,...,n^n \}$.

2. We define two functions: $e_1(k)=k$; $e_2(k)=n-k+1$; here $k \in \{1,2,...,n \}$.

3. Let $f^{(m)}=f \circ f \circ ... \circ f$ is a composition of $m$ functions $f$. For example $f^{(4)}=f\circ f\circ f\circ f$.

4. Let $g_1 (m,n)$ is a number of different functions $f_p \in \mathbb{J}$ for which composition $f^{(m)}_p$ is equal to $e_1(k)$. And $g_2 (m,n)$ is a number of different functions $f_q \in \mathbb{J}$ for which composition $f^{(m)}_q=e_2(k)$. Here $k \in \{1,2,...,n \}$.

5. $g_{1,2}(m,n) - ?$.

Upd. Thanks Joriki and Countinghaus!

-
Cool question. Your $g_1(m, n)$ is the number of elements in the group $S_n$ of exponent $m$. This is the number of elements whose cycle type consists entirely of integers dividing $m$. I'm sure combinatorists know a general formula for this, but I don't. (For any particular $m$ you can write it down straightforwardly, though). –  user29743 Aug 1 '12 at 16:33
The notation might be simplified if you wrote $f^{(4)}$ when you mean "iterate $f$ four times", since powers and derivatives don't make sense in this context. I also wouldn't use $e^{-1}$ since that sounds like "the inverse function of $e$." –  user29743 Aug 1 '12 at 16:34
The entire setup is a bit distracting in that you start out with all functions including non-bijective ones, but in the end you're only interested in counts of bijective ones, i.e. permutations, so you could have phrased the entire problem in terms of permutations in the first place. –  joriki Aug 1 '12 at 16:37
One of my answer: $g_2(3,n)=1$ for any n, is not correct. So i think may be i should include non-bijective functions too. –  Mike Aug 1 '12 at 16:45
No, $e_1$ and $e_2$ are bijective, so any functions you want to compose to get them must be bijective, too. –  joriki Aug 1 '12 at 16:46

I see from a comment under another answer that you're $16$ – so I'm guessing you may not have encountered generating functions yet – feel free to ask about anything in this answer!

The exponential generating function for the number $n!$ of permutations of $n$ objects is

$$\sum_{n=0}^\infty n!\frac{x^n}{n!}=\sum_{n=0}^\infty x^n=\frac1{1-x}\;.$$

This can be factored according to cycles as

$$\prod_{k=1}^\infty\exp\left(\frac{x^k}k\right)=\exp\left(\sum_{k=1}^\infty\frac{x^k}k\right)=\exp(-\log(1-x))=\frac1{1-x}\;,$$

where the $k$-th factor accounts for cycles of length $k$.

Now if the $m$-th power of a permutation is the identity, then the lengths of all its cycles must divide $m$. Thus the exponential generating function for the number of such permutations is

$$\sum_{n=0}^\infty g_1(m,n)\frac{x^n}{n!}=\prod_{k\mid m}\exp\left(\frac{x^k}k\right)\;.$$

To calculate a particular $g_1(m,n)$, you need to expand the right-hand side up to $x^n$.

If the $m$-th power of a permutation is $e_2$, consider first the case of even $n$. Then the permutation must consist of cycles of even lengths $2l$ such that $m$ is an odd multiple of $l$. The elements of $\{1,\dotsc,n\}$ must appear in pairs at opposite points of the cycles, which leads to a factor $\exp((2x)^l/(2l))$. Thus the exponential generating function for even $n=2j$ is

$$\sum_{j=0}^\infty g_2(m,2j)\frac{x^j}{j!}=\prod_{{\scriptstyle l\mid m}\atop{\scriptstyle2l\nmid m}}\exp\left(\frac{(2x)^l}{2l}\right)\;.$$

For odd $n=2j+1$, since $e_2$ maps $(n+1)/2$ to itself, the permutation also has to map $(n+1)/2$ to itself, so $g_2(m,2j+1)=g_2(m,2j)$.

Since you found $g_1(3,n)$ from the article in countinghaus' answer, I'll illustrate how to get those same numbers from the exponential generating function. For $m=3$, there are only two divisors, $k=1$ and $k=3$, so we have

\begin{align} \sum_{n=0}^\infty g_1(3,n)\frac{x^n}{n!} &=\mathrm e^x\mathrm e^{x^3/3}\\ &=(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dotso)(1+\frac{x^3}3+\frac{x^6}{3^2\cdot2!}+\frac{x^9}{3^3\cdot3!}+\dotso)\\ &=1+x+\frac{x^2}2+\frac{x^3}2+\frac{3 x^4}8+\frac{7 x^5}{40}+\frac{9 x^6}{80}+\frac{39 x^7}{560}+\frac{137 x^8}{4480}+\frac{641 x^9}{40320}+\dotso \end{align}

(computation). Then multiplying each coefficient by $n!$ yields $g_1(3,n)=1,1,1,3,9,21,81,351,1233,5769$ for $n=1,\dotsc,9$.

-
Thanks, I need some time to understand this! –  Mike Aug 1 '12 at 18:08
@user22867: The argument is quite compact; do feel free to ask if you want me to spell out some of the details. –  joriki Aug 1 '12 at 18:09
Ok, I will. Very powerfull and nice method (using generating function), i'm impressed. The only question in my head right know is "I want to know and read more about this. Give me a reference to a books". –  Mike Aug 1 '12 at 18:26
@user22867: math.upenn.edu/~wilf/DownldGF.html –  joriki Aug 1 '12 at 18:38
@user22867: I updated the answer with an example calculation for $g_1(3,n)$. –  joriki Aug 1 '12 at 18:56

Very interesting article, I will try to understand it. I'am 16 years old. Can you explain me, which formula from this article give us answer for example, in a case $g_2 (3,n)$? –  Mike Aug 1 '12 at 17:12
This article is just about $g_1$. Let me find the relevant formula. –  user29743 Aug 1 '12 at 17:20
What you want is what he calls $M(k, r)$ (his variables are in the opposite order of yours). He just gives a recursive formula (the one labeled (3)), so you could compute it with a computer but it's not in closed form. –  user29743 Aug 1 '12 at 17:24
I think I understand it. $g_1(3,n) = {3, 9, 21, 81, 351, 1233,5769}$ for $n=(3,4,5,6,7,8,9)$ so, $g_1(3,n)=g_1(3,n-1)+(n-1)*(n-2)*g(3,n-3)$. This formula realy works for $g_1$. Thank you! But I still have proble with $g_2$ –  Mike Aug 1 '12 at 17:45