Identity with Catalan numbers

Note: [2017-08-06] Answer corrected and considerably simplified.

It is convenient to use the coefficient of operator $[u^j]$ to denote the coefficient of $u^j$ in a series. This way we can write e.g. \begin{align*} \binom{n}{j}=[u^j](1+u)^n\qquad\text{and}\qquad j^n=n![u^n]e^{ju} \end{align*}

We obtain \begin{align*} &\color{blue}{\sum_{1\leq j < j^{\prime}\leq n}}\color{blue}{\prod_{{k=1}\atop{k\ne j,j^{\prime}}}^n\frac{(j+j^{\prime})^2}{(j-k)(j^{\prime}-k)}}\\ &\quad=\frac{1}{2}\sum_{1\leq j \ne j^{\prime}\leq n}(j+j^\prime)^{2n-4} \frac{(-1)^{n-j}(j-j^\prime)}{(j-1)!(n-j)!}\cdot \frac{(-1)^{n-j^\prime}(j^\prime-j)}{(j^\prime-1)!(n-j^\prime)!}\tag{1}\\ &\quad=\frac{1}{2{(n-1)!}^2}\sum_{j=1}^{n}\sum_{j^{\prime}=1}^{n}(-1)^{j+j^{\prime}+1} (j+j^\prime)^{2n-4}(j-j^\prime)^2\binom{n-1}{j-1}\binom{n-1}{j^{\prime}-1}\tag{2}\\ &\quad=\frac{1}{2{(n-1)!}^2}\sum_{j=0}^{n-1}\sum_{j^{\prime}=0}^{n-1}(-1)^{j+j^{\prime}+1} (j+j^\prime+2)^{2n-4}(j-j^\prime)^2\binom{n-1}{j}\binom{n-1}{j^{\prime}}\tag{3}\\ &\quad=\frac{1}{2{(n-1)!}^2}\sum_{j=0}^{\infty}\sum_{j^{\prime}=0}^{\infty}(-1)^{j+j^{\prime}+1} (2n-4)![u^{2n-4}]e^{(j+j^{\prime}+2)u}2![v^2]e^{(j-j^{\prime})v}\\ &\qquad\qquad\cdot[w^j](1+w)^{n-1}[z^{j^{\prime}}](1+z)^{n-1}\tag{4}\\ &\quad=-\frac{(2n-4)!}{(n-1)!^2}[u^{2n-4}]e^{2u}[v^2] \sum_{j=0}^\infty(-1)^j e^{j(u+v)}[w^j](1+w)^{n-1}\\ &\qquad\qquad\cdot\sum_{j^{\prime}=0}^\infty(-1)^j e^{j^{\prime}(u-v)}[z^{j^{\prime}}](1+z)^{n-1}\tag{5}\\ &\quad=-\frac{(2n-4)!}{(n-1)!^2}[u^{2n-4}]e^{2u}[v^2](1-e^{u+v})^{n-1}(1-e^{u-v})^{n-1}\tag{6}\\ &\quad=-\frac{(2n-4)!}{(n-1)!^2}[u^{2n-4}]e^{2u}[v^2](1-e^u(e^v+e^{-v})+e^{2u})^{n-1}\\ &\quad=-\frac{(2n-4)!}{(n-1)!^2}[u^{2n-4}]e^{2u}[v^2](1-e^u(2+v^2)+e^{2u})^{n-1}\tag{7}\\ &\quad=-\frac{(2n-4)!}{(n-1)!^2}[u^{2n-4}]e^{2u}[v^2]((1-e^u)^2-e^uv^2)^{n-1}\tag{8}\\ &\quad=-\frac{(2n-4)!}{(n-1)!^2}[u^{2n-4}]e^{2u}[v^2]\sum_{j=0}^{n-1}\binom{n-1}{j}(-e^uv^2)^j(1-e^u)^{2n-2-2j}\tag{9}\\ &\quad=-\frac{(2n-4)!}{(n-1)!^2}[u^{2n-4}]e^{2u}\binom{n-1}{1}(-e^u)(1-e^u)^{2n-4}\tag{10}\\ &\quad=\frac{1}{n-1}\binom{2n-4}{n-2}[u^{2n-4}]e^{3u}(1-e^u)^{2n-4}\tag{11}\\ &\quad\,\,\color{blue}{=\frac{1}{n-1}\binom{2n-4}{n-2}}\tag{12} \end{align*} and the claim follows.

Comment:

• In (1) we use the symmetry of $S_n$ with respect to $j$ and $j^\prime$ and consider the index range with $j\ne j^\prime$ instead of $j<j^\prime$. We also write the factors of the product with factorials.

• In (2) we introduce binomial coefficients.

• In (3) we change the index range and start with $j=j^\prime=0$.

• In (4) we apply the coefficient of operator four times and we set the upper limit of the series to $\infty$ without changing anything, since we are adding zeros only.

• In (5) we use the linearity of the coefficient of operator, do some rearrangements and use the rule \begin{align*} [z^{p-q}]A(z)=[z^p]z^qA(z) \end{align*}

• In (6) we apply the substitution rule of the coefficient of operator with $w:=-e^{u+v}$ \begin{align*} A(z)=\sum_{j=0}^\infty a_j z^k=\sum_{j=0}^\infty a^j [w^j]A(w) \end{align*} to the first series and do it similarly with the second series.

• In (7) we expand $e^v+e^{-v}$ up to terms of $v^2$ since terms with higher powers do not contribute to $[v^2]$.

• In (8) we do a rearrangement to isolate $v^2$.

• In (9) we apply the binomial theorem.

• In (10) we select the coefficient of $v^2$.

• In (11) we do some simplifications.

• In (12) we observe $(1-e^u)^{2n-4}=u^{2n-4}+\cdots$ and conclude $$[u^{2n-4}]e^{3u}(1-e^u)^{2n-4}=[u^{2n-4}]e^{3u}u^{2n-4}=[u^0]e^{3u}=1$$

Start by encoding the sum call it $S_n$ using residues. We have by inspection that $$S_n = \frac{1}{2}\sum_{1\ \leq\ j,\ j'\ \leq\ n \atop j\ne j'}\ \prod_{k\ \neq\ j,\,j'}^{n} {\left(\, j + j'\,\right)^{2} \over \left(\, j - k\,\right)\left(\, j' - k\,\right)} = \frac{1}{2} \sum_{q=1}^n \mathrm{Res} \left(f(z); z=q\right)$$ where $$f(z) = \prod_{p=1}^n\frac{1}{z-p} \sum_{j=1}^n (z-j)\times \frac{(-1)^{n-1-j} (z-j)(z+j)^{2n-4}}{(j-1)!(n-j)!}.$$

This is because

$$\prod_{k\ne j, j'}^n \frac{(j+j')^2}{(j-k)(j'-k)} = (j+j')^{2n-4} \prod_{k\ne j, j'}^n \frac{1}{j-k} \prod_{k\ne j, j'}^n \frac{1}{j'-k}$$

and we get from the residue at $z=j'$ from $f(z)$ for $j\ne j'$ the contribution

$$(j'-j) \prod_{p\ne j'}^n \frac{1}{j'-p} \times (j'-j) (-1)^{n-1-j} \frac{1}{(j-1)! (n-j)!} \times (j+j')^{2n-4}$$

and we have

$$(j'-j) \prod_{p\ne j'}^n \frac{1}{j'-p} = \prod_{p\ne j,j'}^n \frac{1}{j'-p}$$

and

$$(j'-j) (-1)^{n-1-j} \frac{1}{(j-1)! (n-j)!} = \prod_{p\ne j,j'}^n \frac{1}{j-p}.$$

There is a zero contribution when $j=j'$ because the factor $(z-j)^2$ cancels the pole.

We can therefore collect $S_n$ by integrating $f(z)$ around a contour that encloses the $n$ poles. We will then use the residue at infinity to evaluate the sum of the residues inside the contour.

Simplify $f(z)$ to obtain $$f(z) = \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{z-p} \sum_{j=1}^n {n-1\choose j-1} (-1)^{n-1-j} (z-j)^2(z+j)^{2n-4}$$ which is $$f(z) = \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{z-p} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (z-j-1)^2(z+j+1)^{2n-4}.$$

Now the residue at infinity of $f(z)$ is given by $$\mathrm{Res} \left(-\frac{1}{z^2} f\left(\frac{1}{z}\right); z=0\right).$$ The functional term becomes $$-\frac{1}{z^2} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1/z-p} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (1/z-j-1)^2(1/z+j+1)^{2n-4}.$$

This is $$-\frac{1}{z^2} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{z}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} \frac{(1-(j+1)z)^2}{z^2} \frac{(1+(j+1)z)^{2n-4}}{z^{2n-4}}$$ which becomes $$-\frac{z^n}{z^2\times z^2\times z^{2n-4}} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (1-(j+1)z)^2 (1+(j+1)z)^{2n-4}.$$

Drop the minus sign (residues sum to zero) to obtain $$S_n = \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (1-(j+1)z)^2 (1+(j+1)z)^{2n-4}; z=0\right).$$

Using $$(1-(j+1)z)^2 = 1 - 2(j+1)z + (j+1)^2z^2$$ we get three pieces from this, call them $A_n, B_n$ and $C_n.$ We will evaluate these making use of the disappearance of terms from formal power series in residue calculations and the fact that Stirling numbers of the second kind vanish when partitioning into more subsets than there are elements.

We have $$A_n = \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} \sum_{q=0}^{2n-4} {2n-4\choose q} (j+1)^q z^q; z=0\right).$$

This becomes $$A_n = \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{q=0}^{2n-4} {2n-4\choose q} z^q \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (j+1)^q; z=0\right)$$ which is $$A_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{2n-4} {2n-4\choose q} {q+1\brace n} z^q; z=0\right).$$ which simplifies to (powers $z^q$ with $q\ge n$ do not contribute to the residue) $$A_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{n-1} {2n-4\choose q} {q+1\brace n} z^q; z=0\right)$$ which is (the Stirling number vanishes when $q+1 < n$) $$A_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times {2n-4\choose n-1} {n\brace n}z^{n-1};z=0\right) = -\frac{1}{2} {2n-4\choose n-1}.$$

For $B_n$ we obtain $$B_n = \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{2n-4} {2n-4\choose q} {q+2\brace n} z^{q+1}; z=0\right)$$ which simplifies to $$B_n = \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{n-2} {2n-4\choose q} {q+2\brace n} z^{q+1}; z=0\right)$$ which is $$B_n = \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times {2n-4\choose n-2} {n\brace n}z^{n-1};z=0\right) = {2n-4\choose n-2}.$$

For $C_n$ we obtain $$C_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{2n-4} {2n-4\choose q} {q+3\brace n} z^{q+2}; z=0\right)$$ which simplifies to $$C_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{n-3} {2n-4\choose q} {q+3\brace n} z^{q+2}; z=0\right)$$ which is $$C_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times {2n-4\choose n-3} {n\brace n}z^{n-1};z=0\right) = - \frac{1}{2} {2n-4\choose n-3}.$$

Finally collecting the contributions from $A_n, B_n$ and $C_n$ we obtain $$-\frac{1}{2} {2n-4\choose n-1} + {2n-4\choose n-2} - \frac{1}{2} {2n-4\choose n-3} \\ = \left(-\frac{1}{2} \frac{n-2}{n-1} + 1 - \frac{1}{2} \frac{n-2}{n-1} \right) {2n-4\choose n-2} = \frac{1}{n-1} {2n-4\choose n-2} = C_{n-2}.$$

Addendum. Here we have used the basic Stirling number identity $$\sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (j+1)^q = - (n-1)! {q+1\brace n}.$$

To prove this consider the generating function $$- \sum_{q\ge 0} \frac{z^q}{q!} \frac{1}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (j+1)^q \\= \frac{1}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-1-j} \sum_{q\ge 0} \frac{z^q}{q!} (j+1)^q \\= \frac{1}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-1-j} \exp((j+1)z) \\= \frac{\exp(z)}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-1-j} \exp(jz) \\= \frac{\exp(z)}{(n-1)!} (\exp(z)-1)^{n-1}.$$

Now observe the exponential generating function $$\sum_{q\ge 0} {q+1\brace n} \frac{z^q}{q!} = \left(\sum_{q\ge 0} {q\brace n} \frac{z^q}{q!}\right)'$$ which is $$ \left(\frac{1}{n!} (\exp(z)-1)^n\right)' = \frac{1}{n!} \times n \times (\exp(z)-1)^{n-1} \exp(z) \\ = \frac{1}{(n-1)!} (\exp(z)-1)^{n-1} \exp(z).$$

The two generating functions are the same, fin. Here we have used the bivariate generating function $$G(z, u) = \exp(u(\exp(z)-1))$$ of the Stirling numbers of the second kind which follows from the combinatorial class specification

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\mathcal{U}\times\textsc{SET}_{\ge 1}(\mathcal{Z})).$$

I am leaving this proofless for now; one day I hope to get the time.

Let $\mathbb{N}$ be the set $\left\{ 0,1,2,\ldots\right\} $. If $n\in\mathbb{N}$, then I shall use the notation $\left[ n\right] $ for the set $\left\{ 1,2,\ldots,n\right\} $.

Let $\mathbb{K}$ be a commutative ring. Fix $k\in\mathbb{N}$. Consider the polynomial ring $\mathbb{K}\left[ y_{1},y_{2},\ldots,y_{k}\right] $ in $k$ indeterminates $y_{1},y_{2},\ldots,y_{k}$ over $\mathbb{K}$. A polynomial $P\in\mathbb{K}\left[ y_{1},y_{2},\ldots,y_{k}\right] $ is said to be symmetric if any permutation of the indeterminates $y_{1},y_{2},\ldots ,y_{k}$ leaves it unchanged (that is, $P\left( x_{\sigma\left( 1\right) },x_{\sigma\left( 2\right) },\ldots,x_{\sigma\left( k\right) }\right) =P$ for each permutation $\sigma$ of $\left[ k\right] $).

Definition 1. Let $P\in\mathbb{K}\left[ y_{1},y_{2},\ldots,y_{k}\right] $ be a symmetric polynomial. Let $S$ be a $k$-element set. Let $\left( x_{h}\right) _{h\in S}$ be a family of $k$ elements in some commutative $\mathbb{K}$-algebra $\mathbb{L}$. Then, we define the value $P\left( \left( x_{h}\right) _{h\in S}\right) \in\mathbb{L}$ as follows: Choose any list $\left( h_{1},h_{2},\ldots,h_{k}\right) $ containing each element of $S$ exactly once, and set $P\left( \left( x_{h}\right) _{h\in S}\right) =P\left( x_{h_{1}},x_{h_{2}},\ldots,x_{h_{k}}\right) $. This does not depend on the list $\left( h_{1},h_{2},\ldots,h_{k}\right) $, since $P$ is symmetric (and since any two such lists $\left( h_{1},h_{2},\ldots ,h_{k}\right) $ are permutations of each other). Roughly speaking, $P\left( \left( x_{h}\right) _{h\in S}\right) $ means the result of substituting the $k$ values $x_{h}$ with $h\in S$ into $P$, in any order.

Theorem 2. Let $n\in\mathbb{N}$ and $k\in\left\{ 0,1,\ldots,n\right\} $. Let $x_{1},x_{2},\ldots,x_{n}$ be $n$ elements of $\mathbb{K}$. Assume that for any two distinct elements $i$ and $j$ of $\left[ n\right] $, the element $x_{i}-x_{j}$ of $\mathbb{K}$ is invertible. Let $P\in\mathbb{K}\left[ y_{1},y_{2},\ldots,y_{k}\right] $ be a symmetric polynomial such that $\deg P<k\left( n-k\right) $. Then, \begin{equation} \sum_{\substack{S\subseteq\left[ n\right] ;\\\left\vert S\right\vert =k}}P\left( \left( x_{h}\right) _{h\in S}\right) \prod_{\substack{i\in \left[ n\right] \setminus S;\\j\in S}}\dfrac{1}{x_{j}-x_{i}}=0. \end{equation}

For the next theorem, we need more notations.

Definition 3. In the following, the word "$k$-part partition" will mean an integer partition with at most $k$ parts. If $\lambda$ is a $k$-part partition, then we let $s_{\lambda}$ be the Schur polynomial in $\mathbb{K} \left[ y_{1},y_{2},\ldots,y_{k}\right] $ corresponding to $\lambda$. It is well-known that the family of the $s_{\lambda}$ (where $\lambda$ ranges over all $k$-part partitions) is a basis of the $\mathbb{K}$-module of symmetric polynomials in $\mathbb{K}\left[ y_{1},y_{2},\ldots,y_{k}\right] $. This basis is called the Schur basis. If $\mu$ is any $k$-part partition, and if $P$ is a symmetric polynomial in $\mathbb{K}\left[ y_{1},y_{2},\ldots ,y_{k}\right] $, then $\left[ s_{\mu}\right] P$ shall mean the coefficient of $s_{\mu}$ in the expansion of $P$ in this Schur basis.

Now, we can state the following extension of Theorem 2:

Theorem 4. Let $P\in\mathbb{K}\left[ y_{1},y_{2},\ldots,y_{k}\right] $ be a symmetric polynomial such that $\deg P\leq k\left( n-k\right) $. Let $\square$ denote the rectangular partition $\left( \underbrace{n-k,n-k,\ldots ,n-k}_{k\text{ entries}}\right) $. Then, \begin{equation} \sum_{\substack{S\subseteq\left[ n\right] ;\\\left\vert S\right\vert =k}}P\left( \left( x_{h}\right) _{h\in S}\right) \prod_{\substack{i\in \left[ n\right] \setminus S;\\j\in S}}\dfrac{1}{x_{j}-x_{i}}=\left[ s_{\square}\right] P. \end{equation}

[EDIT: Theorem 4 is essentially Theorem 2 in Ömer Egecioglu, On Böttcher's mysterious identity, Australasian Journal of Combinatorics 43, 2009, pp. 307--316. I am saying "essentially" because Egecioglu only states it for symmetric polynomials $P$ that are homogeneous of degree $k\left( n-k\right)$, but the proof applies in the general case.

Also, Theorem 4 is essentially Theorem 1 in Dang Tuan Hiep, Identities involving (doubly) symmetric polynomials and integrals over Grassmannians, arXiv:1607.04850v3. This time, I'm saying "essentially" because Hiep never mentions Schur polynomials and, instead of $\left[ s_{\square}\right] P$, uses the coefficient of $y_1^{n-1} y_2^{n-2} \cdots y_k^{n-k}$ in the polynomial $P \cdot \prod_{i<j} \left(y_i-y_j\right)$ (modulo typos in his paper); but it follows easily from the alternant definition of Schur polynomials that this latter coefficient is precisely $\left[ s_{\square}\right] P$.]

Theorem 4 has the following consequence:

Corollary 5. The sum \begin{equation} \sum_{\substack{S\subseteq\left[ n\right] ;\\\left\vert S\right\vert =k}}\prod_{\substack{i\in\left[ n\right] \setminus S;\\j\in S}}\dfrac {\sum_{h\in S}x_{h}}{x_{j}-x_{i}} \end{equation} is the number of standard Young tableaux of rectangular shape $\left( \underbrace{n-k,n-k,\ldots,n-k}_{k\text{ entries} }\right) $.

My proof of Theorem 4 uses Vandermonde determinants and the alternant definition of Schur functions (see John R. Stembridge, A Concise Proof of the Littlewood-Richardson Rule for all you need to know). Corollary 5 is obtained from Theorem 4 by setting $P = \left(y_1 + y_2 + \cdots + y_k\right)^{k\left(n-k\right)}$, because of the well-known fact that every $m \in \mathbb{N}$ satisfies \begin{align} & \left(y_1 + y_2 + \cdots + y_k\right)^m \\ &= \sum_{\lambda \text{ is a } k\text{-part partition of } m} \left(\text{number of standard tableaux of shape } \lambda\right) s_{\lambda} . \end{align}

If you set $k=2$, $\mathbb{K}=\mathbb{Q}$ and $x_{i}=i$ in Corollary 5, you recover the original question, since the number of standard Young tableaux of rectangular shape $\left( n-2,n-2\right) $ is $C_{n-2}$ (indeed, these tableaux are in bijection with Dyck paths with $n-2$ upsteps and $n-2$ downsteps).