2
$\begingroup$
  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!

  • 1
    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).2012-08-01
  • 2
    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$."2012-08-01
  • 1
    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.2012-08-01
  • 0
    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.2012-08-01
  • 0
    No, $e_1$ and $e_2$ are bijective, so any functions you want to compose to get them must be bijective, too.2012-08-01
  • 0
    I think the answer for $g_2$ is $g_2(2l+1,n)=1$ and $g_2(2l,n)=0$. I wonder why this is not correct. I check it with a simple program for some cases.2012-08-01
  • 0
    @user22867: It's hard to say why something isn't correct without knowing why you think it is -- if you tell us how you came up with that answer, we could perhaps tell you where you went wrong in your reasoning.2012-08-01
  • 0
    I realized my mistakes.2012-08-01

2 Answers 2

2

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$.

  • 0
    Thanks, I need some time to understand this!2012-08-01
  • 0
    @user22867: The argument is quite compact; do feel free to ask if you want me to spell out some of the details.2012-08-01
  • 0
    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".2012-08-01
  • 1
    @user22867: http://www.math.upenn.edu/~wilf/DownldGF.html2012-08-01
  • 1
    @user22867: I updated the answer with an example calculation for $g_1(3,n)$.2012-08-01
  • 0
    Thank you very much. I understand how to use this series. And thanks for "generatingfunctionology". Even more important than the solution, is what I learned about this method. Great!2012-08-01
  • 0
    @user22867: You're welcome!2012-08-01
2

The answer to question one is in this article.

http://www.jstor.org/discover/10.2307/2308456?uid=3739728&uid=2129&uid=2&uid=70&uid=4&uid=3739256&sid=21101125793667

  • 0
    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)$?2012-08-01
  • 0
    This article is just about $g_1$. Let me find the relevant formula.2012-08-01
  • 1
    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.2012-08-01
  • 0
    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$2012-08-01