The answer is the Catalan number
I keep a record here for later retrieval.
Program Verification
The following SageMath program gives me the first 10 values of $a_n$
n = 3
SG = SymmetricGroup(n)
def Cayley_distance( g ):
d = 0
for c in g.cycle_tuples():
d = d + len( c ) - 1
return d
tau = SG( range( 2, n + 1 ) + [1] )
count = 0
for g in SG:
h = tau * g
dh = Cayley_distance( h )
dg = Cayley_distance( g )
if dg + dh == n - 1:
count = count + 1
print( count )
\begin{equation}
\begin{aligned}
a_2 &= 2,\quad a_3 = 5, \quad a_4 = 14,\quad a_5 = 42,\quad a_6 = 132, \\
a_7 &= 429, \quad a_8 = 1430,\quad a_9 = 4862,\quad a_{10} = 16796
\end{aligned}
\end{equation}
As suggested also by @san, this coincides with the Catalan number $C_n = \frac{2n!}{(n+1)!n!}$.
Catalan Number by Richard P. Stanley
You can download the online version and solution from the author's Enumerative Combinatorics course page if you do not have access to the book; the relevant entry is item (hh).
In Chapter 2 Bijective Exercises of the book, the author gives various combinatorial interpretations of Catalan number. In exercise (118), one is required to show that the Catalan number is the number of
- Permutations $u$ of [$n$] such that $u$ and $u(1,2,3, \cdots n)$ have a total of $n+1$ cycles, the largest possible (the permutations u are called permutations of genus 0)
(1)(2)(3), (1,2)(3), (1,3)(2), (1)(2,3), (1,3,2)
Notice that the order of the product doesn't matter, because the number of cycles $\chi(g)$ is a class function (only depend on the conjugacy class)
\begin{equation}
\chi( \tau g ) = \chi( \tau^{-1} \tau g \tau ) = \chi( g \tau )
\end{equation}
Therefore this is exactly what I'm looking for.
In Chapter 3 Bijective Solutions of the book, the author gives the proof:
- A coding of planar maps due to R. Cori, Ast'risque 27 (1975), e 169 pp., when restricted to plane trees, sets up a bijection with item 6. We can also set up a bijection with noncrossing partitions $\pi$ (item 159) by letting the cycles of $u$ be the blocks of $\pi$ with elements written in decreasing order. See S. Dulucq and R. Simion, J. Algebraic Comb. 8 (1998), 169–191.
I can't find R. Cori, Ast'risque 27 (1975). The alternative route is to show that $u$ can be bijectively mapped to noncrossing partitions. And the set of $u$ has genus zero. And I explored a little bit.
Genus of Permutation
(I rewrite the notations to be consistent with mine.)
I read the introduction in S. Dulucq and R. Simion, J. Algebraic Comb. 8 (1998), 169–191., which gives a definition of permutation statistics "genus" $g_{\tau} $of a pair of elements $(g,\tau)$:
\begin{equation}
\chi( \tau) + \chi( g) + \chi( g^{-1} \tau ) = n+ 2 - 2 \text{genus}_{\tau}( g)
\end{equation}
The authors then specialize $\tau$ to be one in my problem to define the genus of a permutation element $\text{genus}( g)$. The element $u$ then has genus $0$.
And so $f_n(x,x)$ is the genus generating function of $S_n$! Namely, the coefficients $a_{n - 2i } $ is the number of elements with genus $i$.
The following lemma establishes the connection between genus 0 and noncrossing partition.
Lemma 2.1 Let $\alpha \in S_n$. Then $\text{genus}(\alpha) = 0$ if and only if the cycle decomposition of $g$ gives a noncrossing partition of $n$, and each cycle of $\alpha$ is increasing.
The proof in the text is however very succinct
Saying that an m-cycle of $\alpha$ is increasing means that its elements are expressible as $h < \alpha(h) < \alpha^2(h) < \cdots $. The reader familiar with [15] will recognize that, in the language of Kreweras’ paper, a genus zero permutation $\alpha$ is the "trace" of the corresponding noncrossing partition, with respect to the N-cycle $\tau$. Thus, the number of permutations in $s_n$ whose genus is zero is the nth Catalan number.
Krewera's paper(Reference 15) is written in French and I can't read it.
Noncrossing Partition
I want to at least understand what is noncrossing partition so I read R. Simion, Noncrossing partitions, Discrete Math. 217 (2000) 367–409.
Figure 2 in this paper is very explanatory, and I paste two pieces here for illustrative purposes.
(a) gives a representation of the permutation (146)(23)(5). Specifically, one can convert the cycle notation to connecting lines between transposed elements and noncrossing partition means this is no crossing for those lines. (f) is the Catalan path corresponding to (a). The number of Catalan path is the one of the definition of Catalan number.
In the beginning of section 3.1, the paper gives a nice bijective proof of (a) to (f).
The enumeration of noncrossing partitions in the guise of Catalan paths (see
Fig. 2(f)) provides one of the basic illustrations of the DSV method. A Catalan path is a lattice path in the plane, starting at the origin and ending at the point $(n,n)$, whose steps are $(1,0)$ (East) or $(0,1)$ (North), and which does not go above the line $x= y$. Each such path corresponds bijectively to a partition in $NC_n$(noncrossing partition) as follows. Traverse the path from the origin to $(n,n)$ and label the East steps $(1,2,\cdots, n)$ in the order in which they are encountered. The steps of the path can be put in pairs, by treating East steps as left parentheses and North steps as right parentheses, and pairing two steps if the corresponding parentheses are matched. Give each North step the label of the East step with which it is matched. Then the labels on contiguous North steps constitute the blocks of a partition of $[n]$ and this partition is noncrossing. Figs. 2(a) and (f) show a noncrossing partition and its corresponding Catalan path.
Repeating the process from (a) to (f) convinces me that it is the Catalan number.
Genus 0 $\leftrightarrow$ Noncrossing Partition
In this MO post Philippe Nadeau gives the explicit bijection.
Let me elaborate his proof.
Suppose $g$ is a permutation that has $k$ cycles, and $\theta$ is a transposition. Then $g \theta$ has $k + 1$ cycles if and only if elements exchanged by $\theta$ are in the same cycle of $g$.
Proof:
Without loss of generality, let $\theta$ exchange $1,2$. If $1$ and $2$ are in the same cycle, then it breaks into two cycles:
\begin{equation}
1 \rightarrow g( 2 ) \rightarrow \cdots\rightarrow g^{-1}(1) \rightarrow 1 , \quad 2 \rightarrow g(1) \rightarrow \cdots\rightarrow g^{-1}(2) \rightarrow 2
\end{equation}
On the other hand, if they belong to different cycles, then $\theta$ will combine them
\begin{equation}
1 \rightarrow g(2) \rightarrow \cdots \rightarrow 2 \rightarrow g( 1 ) \rightarrow \cdots \rightarrow 1
\end{equation}
$\square$
Let the Cayley distance of $g$ to be $d(g)$, then $\chi(g) = n - d$. $\tau = (1,2,3,\cdots, n )$ has only 1 cycle. The composition $g \tau$ can at most have $d + 1$ cycles. So the maximal number of cycles $n - d + d+ 1 = n + 1$ can only be reached if the transpositions of $g$ break the cycles of $\tau$ each time applied to it. The resulting $g\tau$ will have noncrossing partition patterns. Counting $g$ is equivalent of counting $g$, so we have the desired bijection.
Best Answer
As the question observes, each Dyck word decomposes uniquely as a concatenation of nontrivial irreducible Dyck words; say that a concatenation of $\ell$ irreducible Dyck words has $\ell - 1$ returns. $xc(x)$ is the gf for irreducible Dyck words. $c(x) - 1$ is the gf for nontrivial Dyck words. $(c(x) - 1)^k$ is the gf for concatenations of $k$ Dyck words. Therefore, each a Dyck word $D$ with exactly $m$ returns is counted in $(c(x) - 1)^k$ precisely $\binom{m}{k - 1}$ times. Taking the signs into account, this means $D$ is counted $\sum_k (-1)^k \binom{m}{k - 1}$ times on the right side of (11); this is $0$ if $m > 0$ and is $1$ if $m = 0$, i.e., if $D$ is irreducible.
(None of this has anything to do with the fact that $c(x)$ is the GF for Dyck words specifically; the same combinatorics governs the behavior of (4) and (5) in general, where $y$ is the gf for irreducibles and $z$ is the gf for concatenations of irreducibles.)