\documentclass[12pt,reqno]{amsart} \usepackage{amsmath,epsfig,amssymb,amsfonts,latexsym} \usepackage[all]{xy} \setlength{\textwidth}{6.3in} \setlength{\oddsidemargin}{0pt} \setlength{\evensidemargin}{0pt} \newtheorem{thm}{Theorem} \newtheorem{prop}[thm]{Proposition} \newtheorem{property}[thm]{Property} \newtheorem{cor}[thm]{Corollary} \newtheorem{defn}[thm]{Definition} \newtheorem{lem}[thm]{Lemma} \newtheorem{conj}[thm]{Conjecture} \newtheorem{problem}[thm]{Problem} \newtheorem{exam}{Example} \def\qbinom#1#2{\begin{bmatrix}#1\\#2 \end{bmatrix}} \def\inv{{\rm inv}} \def\Cinv{{\rm Cinv}} \def\rn{{\rm rn}}%restricted nesting \def\rc{\mathrm{rc}}%restricted crossing \def\bloc{\mathrm{block}} \def\nes{\mathrm{nes}} \def\sg{\mathrm{sg}} \def\d{{\rm d}} \def\fix{{\rm fix}} \def\cyc{{\rm cyc}} \def\id{{\rm id}} \def\la{\lambda} \def\L{\mathcal L} \def\Z{\mathbb{Z}} \def\pf{\noindent {\it Proof.} } \numberwithin{equation}{section} \begin{document} \title{The Combinatorics of the Al-Salam-Chihara $q$-Charlier Polynomials} \author{Dongsu Kim}~\thanks{The first author was partially supported by KRF grant R05-2004-000-11511-0.} \address{Department of Mathematics, KAIST, Daejeon 305-701, Korea} \email{dskim@math.kaist.ac.kr} \author{Dennis Stanton}~\thanks{The second author was partially supported by NSF grant DMS-0503660.} \address{School of Mathematics\\ University of Minnesota\\ Minneapolis, MN 55455} \email{stanton@math.umn.edu} \author{Jiang Zeng} \address{Institut Camille Jordan, Universit\'e Claude Bernard (Lyon I)\\ F-69622, Villeurbanne} \email{zeng@math.univ-lyon1.fr} \dedicatory{Dedicated to Xavier Viennot on the occasion of his sixtieth birthday} \begin{abstract} We describe various aspects of the Al-Salam-Chihara $q$-Charlier polynomials. These include combinatorial descriptions of the polynomials, the moments, the orthogonality relation and a combinatorial proof of Anshelevich's recent result on the linearization coefficients. \end{abstract} \maketitle %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 54 \rms (2006), Article~B54i\hfill} \def\thepage{} % % \section{Introduction} The classical Charlier polynomials $C_n^a(x)$ have been studied combinatorially by several authors~\cite{De, Ge, Ze}. Recall~\cite{Chi} that these polynomials are defined by \begin{equation} \label{charrr} C_n^a(x)=\sum_{k=0}^n{\binom n k}(-a)^{n-k}x(x-1)\cdots (x-(k-1)) \end{equation} and satisfy the three term-recurrence relation \begin{equation}\label{eq:recur} C_{n+1}^a(x)=(x-a-n)\,C_n^a(x)-an\,C_{n-1}^a(x),\quad n\geq 0, \end{equation} where $C_0^a(x)=1$, $C_{-1}^a(x)=0$. A $q$-version $C_n^a(x;q)$ of these polynomials was studied in \cite{MSW}. The three-term recurrence relation was $$ C_{n+1}^a(x;q)=(x-aq^n-[n]_q)\,C_n^a(x;q)-aq^{n-1}[n]_q\, C_{n-1}^a(x;q), $$ where $[n]_q=1+q+\cdots+q^{n-1}$, $C_0^a(x;q)=1$, $C_{-1}^a(x;q)=0$. The explicit formula analogous to \eqref{charrr} is given by $$ C_n^a(x;q)=\sum_{k=0}^n {\qbinom n k}_q(-a)^{n-k} q^{\binom {n-k} 2} \prod_{i=0}^{k-1} (x-[i]_q). $$ The linearization coefficients for the Charlier polynomials are given by quotients of factorials (see \eqref{eq:lincoef}). The combinatorial study of the $q$-analogues $C_n^a(x;q)$ in \cite{MSW} included finding their linearization coefficients, which were given by a double sum, not quotients of factorials, and as a polynomial in $q$ and $a$ did not have positive coefficients (see \cite[Theorem 3]{MSW}). Anshelevich~\cite{Ans} has recently considered a $q$-analogue of the three-term recurrence \eqref{eq:recur} for $C_n^a(x+a,a)$ and proved that the linearization coefficients of the corresponding polynomials are polynomials of $a$ and $q$ with positive integer coefficients (see Theorem~6). The aim of this paper is to study the combinatorial aspects of a new $q$-analogue of Charlier polynomials, which is a re-scaled version of Anshelevich's $q$-polynomials and turns out to be a special re-scaled version of the Al-Salam-Chihara polynomials. We shall give a combinatorial proof of Anshelevich's result by using the combinatorial interpretations of the polynomials and their moments. It is inspired by the beautiful proofs for other classical orthogonal polynomials in \cite{CV,ISV}. %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} \markboth{\SMALL DONGSU KIM, DENNIS STANTON, AND JIANG ZENG}{\SMALL THE COMBINATORICS OF THE AL-SALAM-CHIHARA $q$-CHARLIER POLYNOMIALS} % % This paper is organized as follows: in the next two sections we give the definitions and combinatorial interpretations of the new $q$-Charlier polynomials and their moments, Corollary~\ref{mainpolycomb} and Theorem~\ref{mainmomcomb}. The explicit linearization coefficients are given in \S4 in Corollary~\ref{maincor}. We then give the killing involution in \S5. We present a variation $\hat C_n(x|q)$ of the polynomials $C_n(x,a;q)$ in \S6, which has the advantage to include the $q$-Hermite polynomials in \cite{ISV} as a special case. We collect here some well-known facts about Charlier polynomials. The generating function is \begin{equation}\label{eq:gen} \sum_{n=0}^\infty C_n^a(x)\frac{t^n}{n!}=e^{-at}(1+at)^x. \end{equation} The moment sequence $\mu_n$ is given by the following formula: \begin{equation}\label{eq:moment} \mu_n=\L(x^n)=\sum_{x=0}^\infty x^n e^{-a}\frac{a^x}{x!} =\sum_{k=1}^nS(n,k)a^k, \end{equation} where $S(n,k)$ denotes the Stirling number of the second kind. The orthogonality reads: \[ \L(C_m^a(x)C_n^a(x))=\sum_{k=0}^\infty C_m^a(k)C_n^a(k)\frac{e^{-a}a^k}{k!}= n!a^n\delta_{mn}. \] The linearization coefficient $c_{n_1n_2}^{n_3}$ is defined by: $$ C_{n_1}^a(x)C_{n_2}^a(x)=\sum_{n_3}c_{n_1n_2}^{n_3}C_{n_3}^a(x). $$ By orthogonality we have $c_{n_1n_2}^{n_3}=\L(C_{n_1}^a(x)C_{n_2}^a(x)C_{n_3}^a(x)) /\L(C_{n_3}^a(x)C_{n_3}^a(x))$. For Charlier polynomials it is easy to derive from \eqref{eq:gen} and \eqref{eq:moment} that $$ \sum_{n_1,\ldots,n_k=0}^{\infty}\L(C_{n_1}^a(x)\ldots C_{n_k}^a(x))\frac{t_1^{n_1}}{n_1!} \ldots\frac{t_k^{n_k}}{n_k!}= e^{a(e_2(t_1,\ldots,t_k)+\ldots +e_k(t_1,\ldots,t_k))}, $$ where $e_i$ is the elementary symmetric function of degree $i$. It follows that \begin{equation}\label{eq:lincoef} \L(C_{n_1}^a(x)C_{n_2}^a(x)C_{n_3}^a(x))= \sum_{l}\frac{n_1!n_2!n_3!a^{l+n_3}}{l!(n_3-n_1+l)!(n_3-n_2+l)!(n_1+n_2-n_3-2l)!}. \end{equation} In the general case the above generating function implies that $\L(C_{n_1}^a(x)\ldots C_{n_k}^a(x))$ ($k\geq 1$) is a polynomial in $a$ with positive integer coefficients; a combinatorial interpretation of this coefficient has been given~\cite{Ge,Ze}. \section{The new $q$-Charlier polynomials} We define the new $q$-Charlier polynomials $C_n(x,a;q)$ by \begin{equation}\label{eq:three-term} C_{n+1}(x,a;q)=(x-a-[n]_q)\,C_n(x,a;q)-a[n]_q\,C_{n-1}(x,a;q). \end{equation} The first values of these polynomials are \begin{align*} C_1(x,a;q)&=x-a,\\ C_2(x,a;q)&= {x}^{2}-(2\,a+1)x+{a}^{2},\\ C_3(x,a;q)&={x}^{3}-(q+3\,a+2){x}^{2}+(aq+3\,{a}^{2}+2\,a+q+1)x-{a}^{3}. \end{align*} The explicit formula which is analogous to \eqref{charrr} is \begin{equation}\label{eq:explicit} C_n(x,a;q)=\sum_{k=0}^n{\qbinom n k}_qq^{k(k-n)}(-a)^{n-k}\prod_{i=0}^{k-1}\left(x-[i]_q+a(q^{-i}-1)\right). \end{equation} This is a re-scaled version of the Al-Salam-Chihara polynomials $Q_n(x,\alpha,\beta;q)$~\cite[p. 80--81]{KS}: $$ C_n(x,a;q)=\left(\frac{a}{1-q}\right)^{n/2}Q_n \left(\frac{1}{2}\sqrt{\frac{1-q}{a}}\left(x- a-\frac{1}{1-q}\right),\frac{-1}{\sqrt{a(1-q)}}, 0;q\right). $$ Since the generating function of the Al-Salam-Chihara polynomials is known, we derive that $$ \sum_{n=0}^\infty C_n(x,a;q)\frac{t^n}{n!_q}=\frac{(-t;q)_\infty}{(\sqrt{a(1-q)}te^{i\theta}, \sqrt{a(1-q)}te^{-i\theta};q)_\infty}, $$ where $n!_q=[n]_q[n-1]_q\ldots [2]_q[1]_q$ and $$ \cos\theta=\frac{1}{2}\sqrt{\frac{1-q}{a}}\left(x-a-\frac{1}{1-q}\right). $$ We can give a combinatorial interpretation for the $q$-Charlier polynomials from a result due to Simion and Stanton~\cite{SS}. Consider a subset $B$ of $[n]$ and a permutation $\sigma$ on $[n]\setminus B$. Then $\sigma$ consists of fixed points and cycles of length $>1$: $$ C=(k_0, k_1, k_2, \ldots, k_s), \quad {\text{where }} k_s>max\{k_0,k_1,\cdots k_{s-1}\}. $$ For any $k\in [n]\setminus B$, let $w(k)=0$ if $k$ is the maximum of its cycle, otherwise $k=k_j$ is on a cycle $C$ as above, then \begin{equation*} w(k)=k-1-|\{i: jk_s}(\# {\text{ of points on Q less than k}}). \end{equation*} Let $w(B,\sigma)=\sum_{k \in [n]\setminus B} w(k)$ and let $\cyc(\sigma)$ be the number of cycles of $\sigma$. \begin{exam} Let $n=9$, $B=\{2,9\}$ and $\sigma=(6)(4\,7)(3\,5\,1\,8)$ (in cycle notation with maximum at last). Then we have $\cyc(\sigma)=3$ and $$ w(B,\sigma)=(3-1-1)+(5-1-1)+(1-1)+(4-1-2)=5. $$ \end{exam} \begin{thm}\label{thm:C_n} We have $$ C_n(x,a;q)=\sum_{(B, \sigma)}(-1)^{n-\cyc (\sigma)}a^{|B|}x^{\cyc(\sigma)}q^{w(B,\sigma)}. $$ where $B\subset [n]$ and $\sigma$ is a permutation on $[n]\setminus B$. \end{thm} \begin{proof} This is the $r=1$, $s=0$, $t=q$, $u=1$ special case of the quadrabasic Laguerre polynomials \cite[p.313]{SS}. \end{proof} We now assume that each permutation $\pi$ of $[n]$ is represented as a product of disjoint cycles, $\pi=\sigma_1\sigma_2\cdots\sigma_k$, where the cycles are written in the descending order of their maxima and each $\sigma_i$ has its maximum at the first position. A pair $(i,j)$, $i>j$, is called a {\em Charlier-inversion} in $\pi=\sigma_1\sigma_2\cdots\sigma_k$ if $i$ is not a maxima of any cycles of $\pi$ and $i$ appears to the left of $j$ in $\pi$. For instance, $(6,2)$, $(6,4)$, $(6,5)$, $(6,1)$, $(6,3)$, $(2,1)$, $(4,1)$ and $(4,3)$ are all Charlier-inversions in $\pi=(8\,6\,2)(7\,4)(5\,1\,3)$. Let $\Cinv(\pi)$ denote the number of Charlier-inversions in $\pi$. \begin{defn}(Charlier-labeling of permutations) A Charlier-labeling of a permutation $\pi=\sigma_1\sigma_2\cdots\sigma_k$ is a labeling of integers and cycles in $\pi$ satisfying the following rules: \begin{itemize} \item Each integer in $\pi$ is labeled $-1$. \item Each cycle of length $1$ is labeled either $-x$ or $a$. \item Each cycle of length $>1$ is labeled $-x$. \end{itemize} A permutation with a Charlier-labeling is called a {\em Charlier-permutation.} \end{defn} Let $\tau$ denote a Charlier-permutation with underlying permutation $\pi$. Identify $\Cinv(\tau)$ with $\Cinv(\pi)$. Define the weight of $\tau$, $w(\tau)$, to be the product of $q^{\Cinv(\tau)}$ and all the labels of integers and of cycles in $\tau$. Since only $1$-cycles are allowed two different choices for a label, if $\pi$ has $f$ fixed points, there are $2^f$ distinct Charlier-permutations with $\pi$ as an underlying permutation. We represent each cycle in a permutation as a sequence starting with the maximum, enclosed with a pair of parentheses. The cycles in a Charlier-permutation are represented in the same way except that 1-cycles with label $a$ are enclosed with a pair of brackets. For each pair $(B,\sigma)$ in Theorem~1, where $B\subset [n]$ and $\sigma$ a permutation of $[n]\setminus B$, one can associate a Charlier-permutation $\tau$ of $[n]$ as follows: each element of $B$ gives rise a 1-cycle with brackets, each cycle $(a_1a_2\ldots a_l)$ of $\sigma$ gives rise a cycle $(a_la_{l-1}\ldots a_1)$ of $\tau$ with reverse order and the maximal element at the first position. It is not hard to see that $w(B,\sigma)=\Cinv(\tau)$. For instance, the Charlier-permutation corresponding to the pair $(B,\sigma)$ in the above example is $\tau=[9](8\,1\,5\,3)(7\,4)(6)[2]$ with weight $$ (-1)^9(-x)^3a^2q^{0+3+1+1}=a^2q^5x^3, $$ because there are nine integers of label $-1$, three cycles of label $-x$, two cycles of label $a$, five Charlier-inversions, i.e. $(5,3),(5,4),(5,2),(3,2),(4,2)$. One can restate Theorem~\ref{thm:C_n} as follows. \begin{cor}\label{mainpolycomb} The $q$-Charlier polynomial $C_n(x,a;q)$ is the generating function of Charlier-permutations of $[n]$: $$ C_n(x,a;q)=\sum_{\tau}w(\tau), $$ where $\tau$ runs through all permutations of $[n]$. \end{cor} \section{The moments} For the Charlier polynomials $C_n^a(x)$, the $n^{th}$ moment $\mu_n$ is the generating function for set partitions of $\{1,2,\cdots, n\}$ according to the number of blocks (see \eqref{eq:moment}). There is a natural $q$-analogue for the polynomials $C_n^a(x;q)$ \cite[Eq. (3.1)]{MSW}, whose $n^{th}$ moment is $$ \mu_n=\sum_{k=1}^n S_q(n,k) a^k. $$ Note that $S_q(n,k)$ is the most natural $q$-analogue of the Stirling numbers of the second kind, and may also be interpreted as a generating function for set partitions with $k$ blocks according to a $q$-statistic. It has a remarkably simple expression as a single sum \cite[Eq. (3.3)]{MSW}. In this section we identify an appropriate $q$-statistic on set partitions which yields the $n^{th}$ moment $\mu_n$ for $C_n(x,a;q)$, and give an explicit formula for it. Recall that if $\pi$ is a partition of $M=\{1,\ldots, m\}$, then a \emph{crossing} of $\pi$ is a quadruple $(a,b,c,d)$ of elements of $M$ such that $a[Fo]{13}\ar@{-}[r]&*+<7pt>{11}\ar@{-}@/^8mm/[rrrr] &*+<3pt>[Fo]{12}\ar@{-}[r]&*+<7pt>{9}\ar@{-}@/^10mm/[rrrrrr]&*+<3pt>[Fo]{10}& *+<7pt>[Fo]{8}\ar@{-}[r]&*+<7pt>{4}\ar@{-}[r]&*+<7pt>{6}\ar@{-}@/^7mm/[rrr] &*+[F]{7}&*+<7pt>[Fo]{5}\ar@{-}@/^7mm/[rrr]&*+<7pt>[Fo]{3}\ar@{-}[r]& *+<7pt>{1}&*+<7pt>[Fo]{2}. } $$ \end{exam} \subsection{Involution} The weight function in Equation~(\ref{eqn:linearization}) has many cancelations. We will give a combinatorial weight-preserving sign-reversing involution $\phi$ with fixed set $\Pi(n_1,n_2,\dots,n_k)$ defined on the set of all Charlier-partitions of type $\mathbf{n}$. Let $(\tau,\nu)$ be a Charlier-partition of $\mathbf{n}$. The involution $\phi$ will be defined depending on three different cases of $(\tau,\nu)$. \medskip \noindent\textsc{Case 1.} If $(\tau,\nu)$ has a circled 1-cycle in a block by itself or a boxed 1-cycle, then define $\phi(\tau,\nu)$ by picking up the smallest 1-cycle and switching its box to circle or vice versa. Since a boxed 1-cycle contributes $-a$ and a circled 1-cycle $a$, $\phi$ is weight-preserving sign-reversing in this case. \medskip \noindent\textsc{Case 2.} We now assume that $(\tau,\nu)$ has no 1-cycles, boxed or circled in a block by itself. Find the rightmost integer $\alpha$, if it exists, in $\tau$, say in $\tau_i$, such that it has a neighbor $\beta$ in $\tau_i$, along the straight edge or an arc, to its right. \noindent\textsc{Case 2.1.} Assume that $\alpha$ and $\beta$ are in the same cycle $\sigma$ ending with $\alpha\,\beta$, i.e. $\sigma=(\cdots\alpha\,\beta)$. Since $\alpha$ is the penultimate entry in $\sigma$, $\beta$ is not the maximum in $\sigma$. Suppose the contribution of $\beta$ to $\Cinv(\tau_i)$ is~$j$. Then $\tau_i$ is of the form $$\tau_i=(\cdots)\cdots(\cdots\alpha\,\beta)(t_m)(t_{m-1})\cdots(t_{j+2})(t_{j})\cdots(t_1)$$ with $t_1[Fo]{11}\ar@{.}@/^10mm/[rrrrrr]^(.96){2}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrrr]^(.95){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]& *+<7pt>[Fo]{8}\ar@{-}[r]^(.85){0}&{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{-}@/^10mm/[rrrr]& *+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}\ar@{<.>}@/^5mm/[d] \\ *+<3pt>[Fo]{11}\ar@{.}@/^10mm/[rrrrr]^(.95){2}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrr]^(.93){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]& *+<7pt>[Fo]{8}\ar@{-}@/^10mm/[rrrr]^(.95){0}&*+<7pt>[Fo]{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{-}@/^10mm/[rrrr]& *+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1} \\ *+<3pt>[Fo]{11}\ar@{.}@/^10mm/[rrrrrrr]^(.97){3}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrrr]^(.95){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]& *+<7pt>[Fo]{8}\ar@{-}[r]^(.85){0}&{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{.}@/^10mm/[rrrr]^(.05){2}& *+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}\ar@{<.>}@/^5mm/[d] \\ *+<3pt>[Fo]{11}\ar@{.}@/^10mm/[rrrrrr]^(.97){3}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrr]^(.93){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]& *+<7pt>[Fo]{8}\ar@{-}@/^10mm/[rrrr]^(.95){0}&*+<7pt>[Fo]{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}\ar@{.}@/^10mm/[rrrrr]^(.04){2}&*+<7pt>[Fo]{5}& *+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1} \\ *+<3pt>[Fo]{11}\ar@{-}@/^7mm/[rr]&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrrr]^(.95){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]& *+<7pt>[Fo]{8}\ar@{-}[r]^(.85){0}&{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{.}@/^10mm/[rrrr]^(.05){2}& *+<7pt>[Fo]{4}\ar@{.}@/^5mm/[r]^(.2){3}&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}\ar@{<.>}@/^5mm/[d] \\ *+<3pt>[Fo]{11}\ar@{-}@/^7mm/[rr]&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrr]^(.93){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]& *+<7pt>[Fo]{8}\ar@{-}@/^10mm/[rrrr]^(.95){0}&*+<7pt>[Fo]{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}\ar@{.}@/^10mm/[rrrrr]^(.04){2}& *+<7pt>[Fo]{5}\ar@{.}@/^7mm/[rr]^(.1){3}&*+<7pt>[Fo]{4}&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1} } $$ \mbox{Three sets of $(\tau,\nu)$ and $(\tau',\nu')$ of type $\mathbf{n}=(3,6,2)$ with $\alpha=8$.} \end{center} \bigskip \noindent\textsc{Case 2.2.} We now assume that $\alpha$ and $\beta$ are in different cycles. Clearly $\beta$ forms a 1-cycle and adjoins $\alpha$ by an arc. Moreover, all integers to the right of $\alpha$ in $\tau_i$ form 1-cycles and are in descending order. Suppose there are exactly $j$ integers between $\alpha$ and $\beta$. Then $\tau_i$ is of the form $\tau_i=(\cdots)\cdots(\cdots\alpha)(t_m)(t_{m-1})\cdots(t_1)$ with $t_1