In a recent paper involving entanglement in linear optics, we came across some summations involving Catalan numbers and permutations. In particular, these sums arise when doing integration over the unitary group $\mathrm U(n)$ in the limit that $n\to\infty$. When doing this, we encounter the asymptotic form of the Weingarten function, which is the origin of the sums over the Catalan numbers. One of these sums that is of most interest to us seems to surprisingly simplify dramatically, which makes us curious to understand why.


Let $\delta$ be the Kronecker delta defined as $\delta_{a,b} = 1$ if $a=b$ and $0$ otherwise. Let $C_n$ be the $n^{\rm th}$ Catalan number $C_n := \frac{1}{n+1}\binom{2n}{n}$.

Let $S_{2\ell}$ denote the permutation group on $2\ell$ elements. For $\tau \in S_{2\ell}$, define $\#(\tau)$ to be the number of cycles in the disjoint cycle decomposition of $\tau$. Indeed let $\{c_i^{(\tau)} \mid i\in \{1,\dots, \#(\tau)\}\}$ be the cycle decomposition, and define $|c_i^{(\tau)}|$ to be the length of the $i^{\rm th}$ cycle. Let $|\tau|$ be the minimum number of transpositions needed to generate the permutation $\tau$, and note that $|\tau| = 2\ell - \#(\tau)$.

Define $\xi^{(\ell)}\colon S_{2\ell} \to \{1,2,\dots, \ell \}$ as

$$ \xi^{(\ell)}(\tau)= \log_2\sum_{j_1,\dots,j_\ell=1}^2 \delta_{j_{\lceil\tau(2\ell)/2\rceil},j_{\lceil\tau(1)/2\rceil} }\delta_{j_{\lceil\tau(2)/2\rceil},j_{\lceil\tau(3)/2\rceil}} \dots \delta_{j_{\lceil\tau(2\ell-2)/2\rceil},j_{\lceil\tau(2\ell-1)/2\rceil}}. $$

For $\ell \in \mathbb N$ and $\kappa \in \mathbb Z$, define $a^{(\ell)}_{\kappa} \in \mathbb Z$ as

$$ a^{(\ell)}_\kappa := \sum_{\substack{\tau\in S_{2\ell} \text{ s.t.}\\\xi^{(\ell)}(\tau) = |\tau|+\kappa}} (-1)^{\#(\tau)} \prod_{i=1}^{\#(\tau)} C_{|c_i^{(\tau)}| - 1}. $$

Example: $\ell = 1$ and $\kappa = 0$

  • When $\ell = 1$, $\xi^{(1)}(\tau) = 1$ for both permutations (the identity and the swap) because $\lceil1/2\rceil = \lceil 2/2\rceil = 1$.
  • When $\tau$ is the identity permutation, $|\tau| = 0$, so it does not contribute to the sum in $a^{(\ell=1)}_{\kappa=0}$.
  • When $\tau$ is the swap, $|\tau| = 1 = \xi^{(1)}(\tau)$, so it does contribute. The swap permutation has one cycle of length 2. Therefore,

$$ a_{\kappa=0}^{(\ell=1)} = (-1)^{2-1}C_{2-1} = -C_1 = -1. $$


In a very roundabout way, we proved in our paper that

$$ a_{\kappa=1}^{(\ell)} = \frac{(-1)^{\ell +1}}{2 \ell -1} \binom{2 \ell -1}{\ell -1}. $$


For all $\ell \in \mathbb N$, $a_{\kappa=0}^{(\ell)} = (-1)^\ell 4^{\ell-1}$.

Evidence for the conjecture: the conjecture is true for $\ell \leq 5$. We generate the following table for $\kappa = 0$ in Mathematica by iterating through all permutations.

$\ell$ $a_{\kappa=0}^{(\ell)}$
$1$ $-C_1$ $= -1$
$2$ $-4 C_0^2 C_1+4 C_0 C_2$ $=4$
$3$ $-9 C_0^4 C_1+15 C_0^2 C_1^2-C_1^3+18 C_0^3 C_2-6 C_0 C_1 C_2-9 C_0^2 C_3$ $=-16$
$4$ $-16 C_0^6 C_1+80 C_0^4 C_1^2-40 C_0^2 C_1^3+48 C_0^5 C_2-112 C_0^3 C_1 C_2 +16 C_0 C_1^2 C_2+8 C_0^2 C_2^2-48 C_0^4 C_3+24 C_0^2 C_1 C_3+16 C_0^3 C_4$ $=64$
$5$ $-25 C_0^8 C_1+250 C_0^6 C_1^2-380 C_0^4 C_1^3+80 C_0^2 C_1^4-C_1^5+100 C_0^7 C_2 -600 C_0^5 C_1 C_2+440 C_0^3 C_1^2 C_2-20 C_0 C_1^3 C_2 + 130 C_0^4 C_2^2 -50 C_0^2 C_1 C_2^2 -150 C_0^6 C_3+320 C_0^4 C_1 C_3-60 C_0^2 C_1^2 C_3-40 C_0^3 C_2 C_3 +100 C_0^5 C_4-60 C_0^3 C_1 C_4-25 C_0^4 C_5$ $=-256$


Can one find a closed form for $a_{\kappa}^{(\ell)}$ for all $\kappa$ and $\ell$? Of particular interest for us is when $\kappa = 0$; how does one prove or disprove our conjecture that $a_{\kappa=0}^{(\ell)} = (-1)^\ell 4^{\ell-1}$? If our conjecture is indeed true, is there any insight as to why the seemingly complicated expression simplifies so dramatically?

Unfortunately, it does not seem that the roundabout way which helped us solve the $\kappa = 1$ case works for the $\kappa = 0$ case. We imagine that a first step to answering these questions is to simplify $\xi^{(\ell)}$, probably using some properties of permutations. Is there any nice interpretation of what $\xi^{(\ell)}(\tau)$ is representing about the permutation $\tau$? We spent some time and came up with a few graphical and combinatorial ways of understanding $\xi^{(\ell)}$, but nothing we’ve been able to use to make any real progress.


  • 5
    $\begingroup$ I don't know whether it's helpful (maybe at least for calculation purposes), but there's a combinatorial interpretation of $\xi^{(\ell)}(\tau)$. Consider the graph on vertices $v_1, v_2, \ldots, v_{2\ell}$ with edges $v_1 - v_2$, $v_3 - v_4$, $\ldots, v_{2\ell-1} - v_{2\ell}$ and $v_{\tau(2)} - v_{\tau(3)}$, $v_{\tau(4)} - v_{\tau(5)}$, $\ldots$, $v_{\tau(2\ell)} - v_{\tau(1)}$. Then every connected component of the graph is a cycle, and $\xi^{(\ell)}(\tau)$ counts them. $\endgroup$ Commented Sep 29, 2022 at 10:03
  • 5
    $\begingroup$ Counts for the first five values of $\ell$ suggest that the number of permutations contributing to $a_{\kappa=1}^{(\ell)}$ is A001764 and the number contributing to $a_{\kappa=0}^{(\ell)}$ is A062236. $\endgroup$ Commented Sep 29, 2022 at 13:35
  • 1
    $\begingroup$ I've managed to verify the conjecture for $\ell = 6$. Code and more detailed results $\endgroup$ Commented Sep 29, 2022 at 16:24
  • 1
    $\begingroup$ Thanks @PeterTaylor! Yes we had also been thinking about this graphical interpretation of xi, but we weren't sure how to use it to make progress on the conjecture. Thanks for the code! I wonder how long does the code run to verify $\ell=6$? $\endgroup$ Commented Sep 29, 2022 at 17:27
  • 2
    $\begingroup$ Let $\alpha=(1\,2)(3\,4)\cdots$ and $\beta=(2l\,1)(2\,3)\cdots$. Color the edges in the first list in Peter Taylor's graph red and the edges in the second list blue, so each cycle alternates blue and red. Following a red edge and then a blue edge takes you from $v_i$ to $v_{(\tau\beta\tau^{-1}\alpha)(i)}$, which implies $\xi^{(l)}(\tau)=\#(\tau\beta\tau^{-1}\alpha)/2$. The triangle inequality for the Cayley metric gives $2(l-\kappa)=|\tau\beta\tau^{-1}\alpha|+2|\tau|\ge|\beta\alpha|=2(l-1)$, so $\kappa\le 1$ and $\kappa$ measures how far this is from equality. $\endgroup$
    – MTyson
    Commented Sep 29, 2022 at 19:18

1 Answer 1


The problem naturally fits in the framework of breakpoint graphs (per Peter Taylor's observation), which makes it possible to obtain a differential equation for the generating function $$H(x,u,s_1,s_2,\dots) := \sum_{\ell\geq 0} x^{2\ell} \sum_{\tau\in S_{2\ell}} u^{\xi^{(\ell)}(\tau)} \prod_{i=1}^{\#(\tau)} s_{|c_i^{(\tau)}|}$$ by modification of the proof of Lemma 3.2 in my paper https://arxiv.org/abs/1503.05285 similarly how it was done for function $G(x,u,s_1,s_2,\dots)$ in Theorem 4.1. In fact, $H$ represents an analog of function $G$, with just a minor complication that it runs only over even $n=2\ell$.

Then it may be possible to obtain an explicit expression for $H$ and/or derive the anticipated identity directly from the differential equation. This approach can potentially be extended to other values of $\kappa$. Please let me know if you are interested to collaborate on working out details in this direction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.