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!

  • 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
    @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
    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