Problem:
$\sigma$ and $\delta$ are non-crossing partitions of $(1,2,\cdots,n)$. They only differ only by a single transposition. In another words, $\sigma \delta^{-1}$ is a single transposition.
Let the number of pairs of $\sigma, \delta$ to be $a_n$. Find an analytic expression for $a_n$.
Example: When $n = 3$, we have 12 pairs: \begin{equation} \begin{aligned} \sigma &= \left\lbrace \begin{aligned} &(123)& \\ & I& \\ \end{aligned} \right. \delta = \left\lbrace \begin{aligned} (12) \\ (13) \\ (23) \end{aligned} \right. \end{aligned} + \text{interchange} \end{equation}
Numerics suggests a surprisingly simple result \begin{equation} a_n = 2{2n \choose n - 2 } \end{equation} which makes me believe there is a simple proof.
non-crossing partition
Let $\sigma$ be a permutation element which composes of cycles. We can draw it on a circle by connecting points within a circle. $\sigma$ is called a non-crossing partition if the resulting diagram has no intersection. See wikipedia for more about its precise definition and properties.
For example, $\sigma = (13)2(456)$ is drew on the circle below, and it is a non-crossing partition.
Attempt:
Since non-crossing partition has orders, we can count the case of $\sigma > \delta$ and multiply by 2. This means that $\delta$ is a finer partition than $\sigma$, i.e. it can only break cycles inside $\sigma$.
Suppose $\sigma$ has $k$ cycles $c_1, c_2, \cdots, c_k$. $\delta$ can be constructed by breaking any one of the cycles into two. Suppose cycle 1 has $|c_1| = m$ elements. Without loss of generality, let it be $(123\cdots m)$. There are ${m \choose 2 }$ ways for $\delta$ to break this cycle into two cycles, i.e. taking $1 \le i < j \le m$, $\delta = (ij) \sigma$. There are \begin{equation} \sum_{i=1}^k { |c_i| \choose 2 } \end{equation} ways to construct $\delta$ out of this $\sigma$. Hence \begin{equation} a_n = \sum_{\substack{\sigma \in \text{NC}\\ \sigma = \{c_1, c_2, \cdots, c_k \}}} \sum_{i=1}^k { |c_i| \choose 2 } \end{equation} I do not find a way to construct a recursive relation or generating function for $a_n $. It may be related to the free probability theory because it is a summation over the non-crossing partition lattice. But from what I know, the moment-cumulant relation in free probability is a summation over the product on the functions on each cycle, not a summation.
Edit 11/10/2017:
According to the article 1 and cited Kreweras's paper, there is a simple formula of counting the non-crossing partition according to cycle types.
Let $(r_1, r_2, \cdots, r_n )$ be a set of non-negative integers that satisfy \begin{equation} \sum_{m=1}^n m r_m = n \end{equation} We can then use $r_m$ to denote the number m-cycles. The number of non-crossing partitions that has $r_m$ m-cycles ($m = 1, \cdots, n$) is \begin{equation} \frac{n!}{(n - \sum_m r_m +1 )!} \prod_m \frac{1}{r_m!} = \frac{1}{n+1} { n+1 \choose r_1, r_2, \cdots, r_n } \end{equation}
Then \begin{equation} a_n = \sum_{\{r_i\}} \frac{1}{n+1} { n+1 \choose r_1, r_2, \cdots, r_n } \sum_{m=1}^{n} r_m { m \choose 2 } \end{equation} where the summation is performed over the constraint $\sum_{m=1}^n m r_m = n$.
1 Liaw, S.C.; Yeh, H.G.; Hwang, F.K.; Chang, G.J., A simple and direct derivation for the number of noncrossing partitions, Proc. Am. Math. Soc. 126, No.6, 1579-1581 (1998). ZBL0892.05007.
