%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%           FPSAC/SFCA '94, May 23-27, 1994   at DIMACS
%                     Problem Session
%   LaTeX file of problem  #3  submitted by David Jackson (May 24, 1994)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[12pt]{article}
\textwidth6.0truein
\textheight8.0truein
\topmargin-.5truein
\oddsidemargin+0truein
\evensidemargin+0truein
\baselineskip0.20truein
\parskip0.20truein

\begin{document}
\begin{center}
{FPSAC/SFCA '94}\\
{PROBLEM SESSION}\\
{Submission received May 24, 1994}\\[.2in]
{\bf AN IDENTITY FOR PERMUTATIONS}\\[.1in]
David M. Jackson\\[.2in]
\end{center}
A permutation is {\em dotted} if each element in the cycles of the
permutation has associated with it at most one dot. A permutation
is {\em strictly} dotted if none of its cycles has all of its elements
bearing a dot, and a dotted permutation has weight $m$ if it has a total
of $m$ dots.
An {\em ordered partition permutation} of weight $m$ is a partitioning
of the cycles of a permutation into $m$ nonempty ordered blocks.
Let $\cal{C}_\gamma$ denote the conjugacy class of the symmetric group on $N$
letters associated with the partition $\gamma$ of $N.$ Let
$\omega_N$ denote the full cycle $(1,2,\ldots,N).$

Prove combinatorially that  the number of
ordered partition permutations of weight $m$ associated with the
permutations in
$\omega_N\cal{C}_\gamma$ is equal to the number of strictly
dotted permutations of weight $m-1$ in $\cal{C}_\gamma$ for $m\ge1.$
\noindent See {\em Trans.\ Amer.\ Math.\ Soc.}\ {\bf 299} (1987), 785--801.
The result is stated on p.\ 799.

It may be that a combinatorial
proof may lead to information that helps with the bijection associated
with quadrangulations (see my previous problem), since a monopole is
a special class of maps.

This problem is equivalent to finding a combinatorial proof of the
3-term recurrence equation of Harer and Zagier ({\em Invent.\ Math.},
{\bf85} (1986), 457--485) for monopoles. This recurrence is stated
on p.\ 796 (Lemma~6.1) of the above TAMS paper.
\end{document}


