Catalan number and Cayley distance inequality in permutation group

Question

Problem statement

This is the part that I think is analytically tractable.

The Cayley distance of element $g_1$ to $g_2$ is the smallest number of transposition that transforms $g_1$ to $g_2$. It is left and right invariant, so \begin{equation} d( g_1, g_2) = d( I, g_1^{-1} g_2 ) = d( I, g_2 g_1^{-1} ) \end{equation} The distance to the identity element is just $ n$ minus the number of cycles in the cycle notation.

By definition, the distance satisfies triangle inequality \begin{equation} d( g_1, g_2 ) + d( g_1, g_3 ) \ge d( g_2, g_3 ) \end{equation} In particular, \begin{equation} d( I, g ) + d( I, \tau g ) \ge d( g, \tau g ) = d( I, \tau) \end{equation}

Now for a fixed element $\tau = (123\cdots n )$, I want to find the number of elements $a_n$(in terms of $n$) that saturate the triangle inequality, \begin{equation} a_n = \text{Cardinality}\{ g \in S_n | d( I, g) + d( I, \tau g ) = d( I, \tau) = n - 1 \} \end{equation}

For the first few $n$, $a_{2} = 2, a_3 = 5, a_4 = 14$.

UPDATE

As @san pointed out, $a_n$ is likely to be the Catalan number. So I checked it numerically using sage: up to $n = 10$ $a_n$ agrees with the Catalan number!

\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}

Moreover, its derivative is the wanted $\frac{1}{2}$, \begin{equation} \partial_n \frac{2n!}{n!(n+1)!}\Big|_{n = 1} = \partial_n \frac{1}{n(n+1) B( n, n+ 1)}\Big|_{n = 1} = \frac{1}{2} \end{equation}

So I think this is should be an accurate guess, and we shall seek for a proof.

@san suggested to prove \begin{equation} a_{n, n-k} = \text{Cardinality}\{g \in S_n | d( I, g ) = n-k, d( I, \tau g ) = k - 1 \} = \frac{1}{k} {n \choose k - 1 } {n - 1 \choose k-1} \end{equation}

such that \begin{equation} a_n = \sum_{k=1}^n a_{n, n-k} = \sum_{k=1}^n \frac{1}{k} {n \choose k - 1 } {n - 1 \choose k-1} = \frac{2n!}{n! (n+1)!} = C_n \end{equation}

Perhaps a recursive route to prove \begin{equation} a_n = \sum_{i=0}^{n-1} a_{i} a_{n-1-i} \end{equation} is possible.

If $g$ can be decomposed as a permutation of the first $k$ elements $g_1$ and permutation of the rest $n-k$ elements $g_2$, then set $\tau_1$ and $\tau_2$ to be the shift operation in these corresponding smaller permutation groups, we have \begin{equation} d(I, g ) + d(I, \tau g ) = d(I, g_1) + d( I, \tau_1 g_1) + d(I, g_2) + d(I, \tau_2 g_2 ) + 1 \le k-1 + n-k-1 + 1 = n-1 \end{equation} The only way to saturate the bound is that both $g_1$ and $g_2$ staturate the bound in the smaller permutation group, hence in for these $g$ the top coefficient is $a_k a_{n-k}$.

But obviously chosing different pivot $k$ overcounts, so I still can not construct a recursive formula relating $a_n$ and $\sum_k a_k a_{n-k}$.

---

Original post: a more general problem

I was looking for the analytic expression(need to take derivative latter) of following polynomial \begin{equation} f_n(x, y) = \sum_{g \in S_n} x^{\chi(g)} y^{\chi( \tau g )} \end{equation} where $g$ is taken from the permutation group $S_n$, the exponent $\chi(g)$ are number of cycles in the cycle notation of $g$, and $\tau$ is a fixed element in $S_n$: $\tau = (123\cdots n )$, i.e. it puts $1$ in the end and shift each letter forward.

Maybe it should not be called generating function but I don't have a proper name for it. A few example will clarity the definition. When $n = 4$, taking $g = (12)(3)(4)$, there are 3 cycles(including the cycle of length 1), so $\chi( g ) = 3$. On the other hand, \begin{equation} \tau g = (1234) \cdot (12) (3)(4) = (134)(2) \end{equation} so $\chi( \tau g ) = 2$, the corresponding monomial of $g$ is $x^3 y^2$. Summing over the monomials of all the elements of $S_n$ gives $f_n(x, y)$.

I have computed the case of $n = 2,3,4$, the results are \begin{equation} \begin{aligned} f_2(x,y) &= x^2 y + x y^2 \\ f_3(x,y) &= x^3 y + 3x^2 y^2 + x y^3 + xy \\ f_4(x,y) &= x^4 y + 6 x^3 y^2 + 6x^2 y^3 + x y^4 + 5 x^2 y + 5 x y^2 \end{aligned} \end{equation}

It would be ideal to have the analytic expression of all the coefficients, but I'm mostly interested in the coefficient of highest power of $f_n(x,x)$ \begin{equation} f_n(x,x) = a_{n} x^{n+1} + \cdots \end{equation} I'd like to obtain the analytic expression of $a_n$, which is the same $a_n$ in the problem statement.

---

$\chi(g)$ and Cayley distance

I read a relevant post about number of cycles and learned that the function $\chi(g)$ is related to the Cayley distance \begin{equation} d( I, g ) = n - \chi( g ) \end{equation}

The power of $x$ in $f_n(x,x)$ is \begin{equation} \begin{aligned} \chi( g) + \chi(\tau g ) &= 2n - d( I, g ) - d( I, \tau g ) \\ &\le 2n - d( g, \tau g ) = 2n - d( I, g^{-1} \tau g ) \\ &= 2n - d(I, \tau) = n + \chi(\tau) = n +1 \end{aligned} \end{equation} so the coefficients $a_n$ is just the number of elements that saturate the Cayley distance triangle inequality \begin{equation} d( I, g ) + d( I , \tau g ) = d( I, g^{-1} \tau g ) = n - 1 \end{equation}

---

Generating function

From this MO post, there is a nice formula for $f_n( x, 1 )$, which is \begin{equation} f_n( x, 1 ) = \sum_{g\in S_n} x^{\chi(g )} = \prod_{k=1}^{n-1} (x + k ) \end{equation} and there is a nice bijective proof here

EDIT

I obtained through an independent non-rigorous approach that $\partial_n a_n\Big|_{n=1} = \frac{1}{2}$, but I still do no know the analytic expression for $a_n$

Answer 1

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

118. 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:

118. 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.