\documentstyle{amsppt}   \magnification=\magstephalf
\NoRunningHeads \nologo  % \pageno=0\null\newpage  
\hsize=16.4 true cm \vsize=23 true cm  
\baselineskip 13.5pt plus .1pt\parskip 3pt plus 1pt  \parindent 23pt \TagsOnRight
\def\Sn{\frak S_N} \def\s{\text{sgn}} \def\Z{\Bbb Z} \def\ve{\varepsilon_g(n)}
\topmatter\title On the distribution of the number of cycles of elements in symmetric groups\endtitle
\author Don Zagier\endauthor
\affil Max-Planck-Institut f\"ur Mathematik, Bonn\\and Universiteit Utrecht\endaffil
\abstract  We give a formula for the number of elements in a fixed conjugacy class
of a symmetric group whose product with a cyclic permutation has a given number of
cycles.  A consequence is a very short proof of the formula for the number $\ve$ of ways
of obtaining a Riemann surface of given genus $g$ by identifying in pairs the sides of a $2n$-gon. 
This formula, originally proved by a considerably more difficult method in [1],  was the key 
combinatorial fact needed there for the calculation of the Euler characteristic of the moduli 
space of curves of genus $g$.  As a second application, we show that the number of ways of writing
an even permutation $\pi\in\Sn$ as a product of two $N$-cycles always lies between $2(N-1)!/(N-r+2)$ and
$2(N-1)!/(N-r+19/29)$, where $r$ is the number of fixed points of $\pi$, and that both constants ``2"
and ``19/29" are best possible. \endabstract \endtopmatter\document 
               % \hfill{\it Dedicated to Willem Kuyk on the occasion of his retirement}\bigskip
Consider the following combinatorial problem.  Let $C$ be a conjugacy class in the symmetric
group $\Sn$ on $N$ letters, and let  $\sigma\in\Sn$ denote a cyclic permutation.  For $1\le m\le N$ set
$$p_m(C)=\frac1{\#C}\cdot\#\{\pi\in C\mid\pi\sigma\text{ has $m$ cycles}\}\,,$$
so that $\sum\limits_{m=1}^N p_m(C)=1$. The problem is to give a closed formula for the numbers $p_m(C)$.
\proclaim{Theorem 1} The numbers $p_m(C)$ are determined by
$$\sum\limits_{m=1}^Np_m(C)\,\Phi_m(X)=\frac{\chi(C,X)}{(1-X)^{N+2}}\,,\tag1$$
where $\chi(C,X)=\det(1-\pi X,\,V)$ is the characteristic polynomial of an element $\pi\in C$ acting
on the permutation representation $V=\Bbb C^N$ of $\Sn$ and 
$$\Phi_1(X)=\frac1{(1-X)^2}\,,\quad\Phi_2(X)=\frac{1+X}{(1-X)^3}\,,\quad\Phi_3(X)=\frac{1+4X+X^2}{(1-X)^4}\,,\;\dots$$
are the  polynomials in $\dfrac1{1-X}$ defined by $\Phi_m(X)=\sum\limits_{k=1}^\infty k^mX^{k-1}\in\Z[[X]]$.\endproclaim

Before giving the proof of this theorem, we mention a few of its consequences.

\noindent{\bf Application 1.} For $\pi\in\Sn$ denote by $N_i(\pi)$ ($1\le i\le N$) and $N(\pi)$ the number of $i$-cycles
and the total number of cycles, respectively, so that $\sum iN_i(\pi)=N$, $\;\sum N_i(\pi)=N(\pi)$.  Since these are 
conjugacy class invariants, we also denote them $N_i(C)$ and $N(C)$, where $C=C(\pi)$ is the conjugacy class of $\pi$.  Then
$$ \chi(C,X)=\prod_{i=1}^N (1-X^i)^{N_i(C)}\tag2$$
is divisible exactly by $(1-X)^{N(C)}$, so the right-hand side of (1) has a pole of order $N+2-N(C)$
at $X=1$.  Since $\Phi_m(X)$ is a polynomial of degree $m+1$ in $(1-X)^{-1}$, it follows from (1) that 
$$\text{Max}\{m\mid p_m(C)\ne0\}=N+1-N(C)\,,$$
and in particular, that $N(\pi)+N(\pi\sigma)\le N+1$ for every $\pi\in\Sn$. This is a special case of the easily
proved inequality $N(g_1)+N(g_2)\le N(g_1g_2)+N$, valid for all $g_1,\,g_2\in\Sn$.


\noindent{\bf Application 2.} Another easy consequence of (1) is that $p_m(C)=0$ unless $\,\s(\pi)=(-1)^{m-1}$ 
($\pi\in C$).  This is of course trivial anyway since $p_m(C)\ne0$ implies that
$$(-1)^{N-m}=(-1)^{N-N(\pi\sigma)}=\s(\pi\sigma)=\s(\sigma)\,\s(\pi)=(-1)^{N-1}\,\s(\pi)$$
for some $\pi\in C$, but it also follows from (1) and (2) together with the observation that 
$X\Phi_m(X)$ is $(-1)^{m-1}$-symmetric under $X\mapsto1/X$.

\noindent{\bf Application 3.} In the special case when  $\pi\in C$ is cyclic, the number $p_m(C)$ is the 
probability that a product of two cyclic permutations in $\Sn$ has exactly $m$ cycles, and (1) says that this number
equals $\dfrac{1+(-1)^{N-m}}{(N+1)!}$ times the coefficient of $x^m$ in $x(x+1)\cdots(x+N)$.
For example, for $N$ odd the probability that the product of two random cyclic permutations in $\Sn$
is cyclic is  $2/(N+1)$, as opposed to the probability $2/N$ that a random even element of $\Sn$ is cyclic.

\noindent{\bf Application 4.} The most interesting special case of (1), however, and the main reason for this note,
is the case when $N=2n$ and $C$ is the conjugacy class of free involutions, i.e., any $\pi\in C$ has $n$ cycles of
length 2.  Here $p_m(C)=0$ if $m>n+1$ or $n+1-m$ is odd, by the observations in ``Application 1" and
``Application 2."  The number $p_{n+1-2g}(C)$ equals $\ve/(2n-1)!!$, where
$(2n-1)!!=|C|=1\times3\times\cdots\times(2n-1)$ and $\ve$ is the number of ways of identifying
in pairs the sides of a $2n$-gon to obtain an oriented surface of genus $g$.   (This is because any 
orientation-reversing pairwise gluing $\pi$ of the sides gives an oriented surface of {\it some} genus $g$,
and the resulting surface is triangulated with $N(\pi\sigma)$ vertices, $n$ edges, and one 2-simplex,
so that $2-2g=N(\pi\sigma)-n+1$ by Euler's formula.)  On the other hand, $\chi(C,X)=(1-X^2)^n$ by (2), so
(1) becomes $$\frac1{(2n-1)!!}\;\sum_{0\le g\le n/2}\ve\,\Phi_{n+1-2g}(X)=\frac{(1+X)^n}{(1-X)^{n+2}}\tag3$$ 
or, comparing the coefficients of $X^{k-1}$ on both sides,
$$\frac1{(2n-1)!!}\;\sum_{0\le g\le n/2}\ve\,k^{n+1-2g}
=\text{Coeff}_{X^{k-1}}\biggl[\frac{(1+X)^n}{(1-X)^{n+2}}\biggr]
=\text{Coeff}_{T^{n+1}}\biggl[\frac12\,\bigl(\frac{1+T}{1-T}\bigr)^k\biggr]\,,\tag4$$
where the last equality follows from the residue theorem or by computing in two ways the coefficient of $X^{k-1}T^{n+1}$ in $(1+T)/(1-T-X-XT)$.

Formula (4) was proved by a considerably more complicated method in [1] and was the main combinatorial ingredient 
in the calculation given there of the Euler characteristic of the moduli space of curves of genus $g$.  Actually,
the formula was used there in the form 
$$\ve =\frac{2^{n-2g}\,(2n-1)!!}{(n+1-2g)!}\,\text{Coeff}_{u^{2g}}\biggl[\biggl(\frac u{\sinh u}\biggr)^2\biggl(\frac u{\tanh u}\biggr)^n\,\biggr]\,,$$
which can be obtained from (4) either by susbstituting $T=\tanh u$ and applying the residue theorem or else directly from (3) by observing that
$$e^{-x}\,\Phi_m\bigl(e^{-x}\bigr) = (-1)^m\,\frac{d^m}{dx^m}\biggl(\frac1{e^x-1}\biggr)=\frac{m!}{x^{m+1}}+\text O(1)\qquad(x\to0)$$
and then comparing coefficients of $u^{2g-2-n}$ in both sides of (3) with $X=e^{-2u}$.  The same method applies to the general case and
leads to the following equivalent form of the main theorem:
$$p_m(C)=\frac1{m!}\,\text{Coeff}_{x^{N+1-m}}\biggl[\biggl(\frac x{1-e^{-x}}\biggr)^{\!N+2}e^{-x}\,\chi\bigl(C,e^{-x}\bigr)\biggr]\,.\tag5$$
\noindent{\bf Application 5.}  It is well-known that every even permutation $\pi\in\Sn$ is the product of two $N$-cycles.  Let $R(\pi)$ 
be the number of such representations.  It is easy to see that      $$ R(\pi)=(N-1)!\;p^{\phantom j}_1(\pi)\;.\tag6$$
On the other hand, it is also easy to verify that the average of $p_m(\pi)$ over all $\pi\in\Sn$ for any $m\ge1$ is just the coefficient
of $y^m$ in the polynomial $\binom{y+N-1}N$.  For $m=1$ this is $1/N$, so (6) gives
$$\align\text{Average}&\bigl\{R(\pi)\mid\pi\in\Sn,\;\pi\text{ even}\bigr\}\;=\;\frac{2\,(N-1)!}N\;.\\ \intertext{We will show that}
\text{Min}&\bigl\{R(\pi)\mid\pi\in\Sn,\;\pi\text{ even}\bigr\}\;\ge\;\frac{2\,(N-1)!}{N+2}\;,\endalign$$
so that the minimum value of $R(\pi)$ is only slightly less than its average value.  In fact, we will prove the following stronger
and rather amusing result.
\proclaim{Theorem 2} Let $\pi\in\Sn$ be an even permutation with $r$ fixed points, $0\le r\le N$.  Then
$$\frac{2\,(N-1)!}{N\,-\,r\,+\,2}\;\le\;R(\pi)\;\le\;\frac{2\,(N-1)!}{N\,-\,r\,+\,\frac{19}{29}}\tag7$$
and the constants $2$ and $\frac{19}{29}$ appearing in the denominators are both best possible.\endproclaim

We now give the proofs of the two theorems.  

\medskip\noindent{\bf Proof of Theorem 1.} 
A well-known formula, valid for any finite group $G$ and conjugacy classes $A$, $B$, $C\subseteq G$, says that
$$\#\bigl\{(a,b,c)\in A\times B\times C\mid abc=1\bigr\}
=\frac{|A|\,|B|\,|C|}{|G|}\,\sum_{\chi\in\widehat G}\frac{\chi(A)\chi(B)\chi(C)}{\chi(1)}$$
(sum over the characters of the irreducible representations of $G$). An equivalent form of this is
$$\frac1{|C|}\,\sum_{c\in C} F(bc)=\sum_{\chi\in\widehat G}\frac{\chi(b)\chi(C)}{\chi(1)}\,
\biggl(\frac1{|G|}\,\sum_A\,|A|\,\chi(A)\,F(A^{-1})\biggr)\tag8$$
for any $b\in G$ and any class invariant $F:G\to\Bbb C$.  We apply it to $G=\Sn$, $b=\sigma$, and $F(\pi)=\Phi_{N(\pi)}(X)$. 
Let $V_0$ denote the irreducible $(N-1)$-dimensional subrepresentation of $V=\Bbb C^N$ and $\chi_r$ 
($0\le r\le N-1$) the character of the irreducible representation $\Lambda^r(V_0)$. Clearly 
$$\sum_{r=0}^{N-1}\chi_r(\pi)\,(-T)^r=\det(1-\pi\,T,\,V_0)=\frac{\chi(\pi,T)}{1-T}\qquad(\forall \pi\in G).\tag9$$
In particular, $\chi_r(\sigma)=(-1)^r$ since $\chi(\sigma,T)=1-T^N$ by (2). Hence
$$\sum_{r=0}^{N-1}|\chi_r(\sigma)|^2=N=\frac{|G|}{|C(\sigma)|}=\sum_{\chi\in\widehat G}|\chi(\sigma)|^2$$
(orthogonality relation for characters!), so $\chi(\sigma)=0$ for all $\chi\not\in\{\chi_0,\ldots,\chi_{N-1}\}$
and (8) becomes 
$$\frac1{|C|}\sum_{\pi\in C}\Phi_{N(\pi\sigma)}(X)=\sum_{r=0}^{N-1}
\frac{(-1)^r\,\chi_r(C)}{\binom{N-1}r}\,\biggl(\frac1{N!}\sum_A|A|\,\chi_r(A)\,\Phi_{N(A)}(X)\biggr)\,.\tag10$$
But by formulas (9) and (2) we have
$$\align\sum_{r=0}^{N-1}\biggl(\frac1{N!}\sum_A|A|&\,\chi_r(A)\,k^{N(A)}\biggr)\,(-T)^r=\sum_{N_1+2N_2+\cdots=N}
\frac{k^{N_1+N_2+\cdots}\,(1-T)^{N_1}(1-T^2)^{N_2}\cdots}{1^{N_1}2^{N_2}\cdots\,N_1!N_2!\cdots\,
(1-T)}\\
&=\frac1{1-T}\,\text{Coeff}_{u^N}\biggl[\prod_{j=1}^\infty\sum_{n=0}^\infty\frac{k^n(1-T^j)^nu^{nj}}{j^n\,n!}\biggr]
=\frac1{1-T}\,\text{Coeff}_{u^N}\biggl[\biggl(\frac{1-uT}{1-u}\biggr)^k\biggl]\,.\endalign$$ 
Multiplying by $X^{k-1}$ and summing over all $k\ge1$, we find
$$\sum_{r=0}^{N-1}\biggl(\frac1{N!}\sum_A|A|\,\chi_r(A)\,\Phi_{N(A)}(X)\biggr)\,(-T)^r
 =\frac1{1-T}\,\text{Coeff}_{u^N}\biggl[\frac{1-uT}{1-u-X+uXT}\biggl]=\frac{(1-XT)^{N-1}}{(1-X)^{N+1}}$$
or, comparing the coefficients of $(-T)^r$ on both sides,
$$\frac1{N!}\sum_A|A|\,\chi_r(A)\,\Phi_{N(A)}(X)=\binom{N-1}r\,\frac{X^r}{(1-X)^{N+1}}\,.$$
Substituting this into (10) and using (9) again, we obtain the desired formula (1).  
\medskip\noindent{\bf Proof of Theorem 2.}   Write $N_i$ for $N_i(\pi)$, so that $r=N_1$, and denote by $f_\pi(k)$ the polynomial
$\sum_{m=1}^Np_m(\pi)k^m$.  Theorem 1 can be expressed in terms of $f_\pi$ by the generating function
$$\phi_\pi(y)=\sum_{k=1}^\infty f_\pi(k)\,y^{k-1}=\frac{\chi(\pi,y)}{(1-y)^{N+2}} = \frac1{(1-y)^{N+2}}\,\prod_{i=1}^N\,(1-y^i)^{N_i}\tag11$$
and we want to compute $p_1^{\phantom j}(\pi)=f_\pi'(0)$.  For this we use:
\proclaim{Lemma} Let $f(k)$ be a polynomial with $f(0)=0$ and $\phi(y)=\sum_{k=1}^\infty f(k)y^{k-1}\in\Bbb C\bigl[\frac1{1-y}\bigr]$.  Then  
  $$f'(0)=\int_0^\infty\phi(-t)\,dt\;.$$     \endproclaim
\demo{Proof} We may assume $f(k)=\binom{k+r-1}r$ for some $r\ge1$, since any polynomial with zero constant term is a linear
combination of these.  Then $\int_0^\infty\phi(-t)dt=\int_0^\infty(1+t)^{-r-1}dt=1/r=f'(0)$.\enddemo

Applying the lemma to the polynomial $f=f_\pi$, we find
$$p^{\phantom j}_1(\pi)=f_\pi'(0)= \int_0^\infty\phi_\pi(-t)\,dt=2\,\int_0^1\phi_\pi(-t)\,dt\;,$$
where the last identity follows from the fact that $y\phi_\pi(y)$ is invariant under $y\mapsto1/y$ since $\pi$ is even
(cf\. ``Application 3" above).  Now substitute $t=x/(1-x)$ and use (11) to get
$$p^{\phantom j}_1(\pi)=2\,\int_0^{1/2}\phi_\pi\bigl(\frac{-x}{1-x}\bigr)\,\frac{dx}{(1-x)^2}
    =2\,\int_0^{1/2}\,\prod_{i=2}^N\,\bigl[(1-x)^i-(-x)^i\bigr]^{N_i}\,dx\;.\tag12$$
The lower bound in the theorem follows easily.  Indeed, for $i\ge2$ we have
$$(1-x)^i-(-x)^i\;\ge\;\bigl[(1-2x)+x^2\bigr]^{i/2}-(x^2)^{i/2}\;\ge\;(1-2x)^{i/2}\;,$$  so
$$p^{\phantom j}_1(\pi)\;\ge\;2\int_0^{1/2}(1-2x)^{(N-N_1)/2}\,dx\;=\;\frac2{N-N_1+2}$$ with equality if $N=N_1+2N_2$,
and in view of (6) this is equivalent to the lower bound in equation~(7).  (Recall that $r=N_1$.)  For the other direction, we use the estimates
$$\align (1-3x+3x^2)^{2/3}&=\bigl[(1-2x)^3+2(2x^2-x)^2+(x^2-x)^2\bigr]^{1/3}\,\ge\,1-2x\,=\,(1-x)^2-x^2\\
    (1-3x+3x^2)^{i/3}&=[(1-x)^3+x^3]^{i/3}\,\ge\,(1-x)^i+x^i\,\ge\,(1-x)^i-(-x)^i\qquad\text{if}\quad i\ge3\endalign$$
to get      $$p^{\phantom j}_1(\pi)\;\le\;2\int_0^{1/2}(1-3x+3x^2)^{(N-N_1)/3}\,dx\;=:\;A(N-N_1)\;.$$
An easy analysis shows that $A(k)=2/(k+c_k)$ where $c_k$ decreases monotonically from $c_2=1.24409\dots$ to $c_8=0.64164\dots$ 
and then increases monotonically to a limiting value of 1 as $k\to\infty$, with $c_9=\frac{19}{29}$ and $c_k\ge\frac{19}{29}$ for all $k$ except 7 and 8.
This proves the second inequality in (7) for all cases except $N=N_1+7$ or $N=N_1+8$ and shows also that it is best possible.
(Take $\pi$ with $r=N-9$ fixed points and three 3-cycles; then (12) shows that $p_1(\pi)=A(9)=2/(N-r+\frac{19}{29})$.)
Finally, for the two cases where $k=N-r$ has the value 7 or 8 we must look at the finite list of partitions of $k$ as $\sum_{i\ge2}iN_i$
and for each one check that the value of the integral in (12) is $\le2/(k+\frac{19}{29})$. (The integrand in (12) is a polynomial, so the ten integrals
in question are easy to compute). This completes the proof of the theorem.
\medskip \noindent
{\bf Remarks.} The author would like to thank Professor T\.A\. Springer for helpful conversations and
in particular for the observation that only the characters $\chi_r$ contribute to the calculation
of $p_m(C)$.  The observation that the combinatorial result in [1] could in principle also be
obtained by calculating the numbers $p_m(C)$ for the conjugacy class of free involutions in $\frak S_{2n}$
was made to me shortly after [1] appeared by A\. Odlyzko, and an explicit calculation
along these lines is given in the paper [3] by D.M\. Jackson, but with a longer derivation than the one here.
Another proof of the combinatorial formula in question was given by Itzykson and Zuber [2], and a completely 
different proof of the Euler characteristic formula, not relying on a triangulation of the moduli space, by Kontsevich~[4]. 

\heading References\endheading
\noindent [1] J\. Harer and D\. Zagier, {\it The Euler characteristic of the moduli space of
curves}, Invent\. math\. {\bf 85} (1986) 457--485

\noindent [2] C\. Itzykson and J-B\. Zuber, {\it Matrix integration and combinatorics of modular groups}, Comm\. Math\. Phys\. {\bf 134} (1990) 197--207

\noindent [3]   D.M\. Jackson, {\it Counting cycles in permutations by group characters, with an
application to a topological problem}, Trans\. AMS {\bf 299} (1987) 785--801

\noindent [4] M\. Kontsevich, {\it Intersection theory on the moduli space of curves and the matrix Airy function}, 
   Comm\. Math\. Phys\. {\bf 147} (1992) 1--23
\end

PARI program to for the estimates at the end of the last proof:

c(k)= 1/intnum(x=0,.5,(1-3*x+3*x^2)^(k/3))-k
c(2) :     %17 = 1.244092523603851146621775424
c(3) :     %18 = 1.000000000000000000000000000
c(4) :     %19 = 0.8316311075397904799010909102
c(5) :     %20 = 0.7252794218873626342585469841
c(6) :     %21 = 0.6666666666666666666666666665
c(7) :     %22 = 0.6425342145561409312485786008
c(8) :     %23 = 0.6416434573483804714382628373
c(9) :     %24 = 0.6551724137931034482758620686
c(10) :    %25 = 0.6766525845811168697719963757
c(11) :    %26 = 0.7016381212877428327766101276
19/29. :   %27 = 0.6551724137931034482758620689

log(1-3*x+3*x^2)/3  +  O(x)^7)
%42 = -x - 1/2*x^2 + 3/4*x^4 + 9/5*x^5 + 3*x^6 + O(x^7)
exp(k*(%+x))
%43 = 1 - 1/2*k*x^2 + (1/8*k^2 + 3/4*k)*x^4 + 9/5*k*x^5 + (-1/48*k^3 - 3/8*k^2 + 3*k)*x^6 + O(x^7)
  ==>   (1-3x+3x^2)^{k/3}  =  e^{-kx} (1 - (k/2) x^2 + (k^2/8+3k/4) x^4 + O(k x^5) + O(k^3 x^6) + ...
  ==>   A(k)/2  =  1/k  - (k/2)*2!/k^3 + (k^2/8+3k/4)*4!/k^5  +  O(1/k^4)  + O(1/k^3) + ...  
                =  1/k  -  1/k^2  + O(k^3)  =  1/(k + 1 + o(1))

f2(x)= (1-x)^2-x^2
f3(x)= (1-x)^3+x^3
f4(x)= (1-x)^4-x^4
f5(x)= (1-x)^5+x^5
f6(x)= (1-x)^6-x^6
f7(x)= (1-x)^7+x^7
f8(x)= (1-x)^8-x^8
 -7 + 1/intnum(x=0,1/2,f7(x)) :           %28 = 0.9999999999999999999999999997
 -7 + 1/intnum(x=0,1/2,f2(x)*f5(x)) :     %29 = 1.347826086956521739130434782
 -7 + 1/intnum(x=0,1/2,f3(x)*f4(x)) :     %30 = 1.000000000000000000000000000
 -7 + 1/intnum(x=0,1/2,f2(x)^2*f3(x)) :   %31 = 1.571428571428571428571428571
 -8 + 1/intnum(x=0,1/2,f8(x)) :           %32 = 1.035294117647058823529411764
 -8 + 1/intnum(x=0,1/2,f2(x)*f6(x)) :     %33 = 1.333333333333333333333333333
 -8 + 1/intnum(x=0,1/2,f3(x)*f5(x)) :     %34 = 0.8421052631578947368421052628
 -8 + 1/intnum(x=0,1/2,f4(x)^2) :         %35 = 1.130434782608695652173913043
 -8 + 1/intnum(x=0,1/2,f2(x)^2*f4(x)) :   %36 = 1.599999999999999999999999999
 -8 + 1/intnum(x=0,1/2,f2(x)*f3(x)^2) :   %37 = 1.142857142857142857142857142
 -9 + 1/intnum(x=0,1/2,f3(x)^3) :         %38 = 0.6551724137931034482758620686


PARI program to check that the number  2*8!/(9 + 19/29)  for the permutation  \pi = 3+3+3:

t=0;w6=vector(10,n,0);\
for(a=2,5,for(b=a+1,6,v0=[1,a,b,0,0,0];m=4;\
    for(c=2,6,if((c-a)*(c-b),v0[m]=c;m=m+1,));t=t+1;w6[t]=v0))
    
s=0;w=vector(280,n,0);\
for(a=2,8,for(b=a+1,9,v=vector(6,m,0);m=1;\
    for(c=2,9,if((c-a)*(c-b),v[m]=c;m=m+1,));\
    for(m=1,10,s=s+1;z=w6[m];print1(s);\
      w[s]=concat([1,a,b],vector(6,n,v[z[n]])))))

v=vector(9,n,0);h=0;for(s=1,280,u=w[s];\
   for(p=1,2,x=u[2];u[2]=u[3];u[3]=x;\
   for(q=1,2,y=u[5];u[5]=u[6];u[6]=y;\
   for(r=1,2,z=u[8];u[8]=u[9];u[9]=z;\
   forstep(k=1,7,3,v[u[k]]=u[k+1];v[u[k+1]]=u[k+2];v[u[k+2]]=u[k]);\
     t=9;k=0;while(t,t=v[t]-1;k=k+1); if(k<9,,h=h+1)))));h

EXPLANATION:
w6 = [1,a,b,c,d,e] =perm. of [6],  1 -> a -> b -> 1,  c -> d -> e -> c
w = similar list of the 280 perms of [9],  [1,a,b;c,d,e;e,f,g]
   (but ordered with a<b, c<d<e, e<f<g,  so only 1/8th of all ways)
The p,q,r list inverts a/b, d/e, f/g  to get all 2240 perms 3+3+3
The corresponding permutations are computed as "v"
"h" counts how many of the 2240  v's have  "t --> v[t]-1"  cyclic
OUTPUT = 464 = 2*(2240)/(9+19/29)
