# Coincidences between average Catalan tableaux

There are Catalan number $$C_n$$ of standard Young tableaux of shape $$(n,n)$$, which we view as $$2\times n$$ matrices. Denote by $$P_n$$ the average of these matrices: $$P_n \, := \, \frac{1}{C_n} \, \sum_{A \, \in \, \text{SYT}(n,n)} A$$ Note that $$P_n=(p_{ij})$$ is a rational matrix with entries monotone increasing in rows and columns. Also, by the 180$$^\circ$$ rotational symmetry, $$p_{ij} + p_{3-i,n+1-j} = 2n+1$$. For example, $$p_{11}=1$$, $$p_{2n}=2n$$.

The asymptotic density of $$P_n$$ as $$n\to \infty$$ is easy to obtain by a direct calculation or via the Brownian excursion (see e.g. here or there), but my question is different.

Question. Let $$\beta(n):= \min_{(ij)\ne (kl)} |p_{ij}-p_{kl}|$$. Is it true that $$\beta(n) = o(1)$$?

It would be cool if there was an easy way to see this. I really want a generalization of this result to all large partitions, but at the moment even this is confounding.

UPDATE (May 18, 2019):
Let me explain the motivation behind the question. Recall the 1/3-2/3 conjecture that every poset $$\mathcal P=(X,\prec)$$ that is not a linear order contains two elements $$x,y\in X$$ such that $$\frac13 \le P(x\prec y) \le \frac23$$ For width 2 posets this was shown by Linial in this paper, but I thought that for shapes $$(n,n)$$ one can improve $$1/3$$ to perhaps $$(1/2-\varepsilon)$$, since we know so much about Catalan numbers (including the average of Catalan objects). Linial's proof cannot be easily improved, unfortunately. Now, a beautiful Kahn-Linial proof of the weaker $$1/2e$$ bound starts with the average LE of $$\mathcal P$$. If $$\beta(n)=o(1)$$, their argument plus the (earlier) Grünbaum Theorem implies the $$(1/e-\varepsilon)$$ bound, already a nice result.

Now, Richard's calculaitons give $$p_{17} \to 9949/1024 \approx 9.7158$$, $$p_{23} \to 9.75$$. This means that taking $$x=(1,7)$$ and $$y=(2,3)$$ in $$(n,n)$$ gives $$0.3553 < \frac1e \left(1-\frac{35}{1024}\right) < P(x\prec y) < \frac2e \left(1+\frac{35}{1024}\right) < 0.6447$$ for $$n$$ large enough (unless I miscalculated). This improvement over $$1/3$$ bound is good to know, but surely one can do better.

• Another trivial observation that might be useful is that $p_{i,j} \geq p_{i-1,j} + 1$ and $p_{i,j} \geq p_{i,j-1} + 1$. – Sam Hopkins May 15 at 15:48
• Observation 1: for $n \leq 12$: the minimum is obtained at a unique pair $(i,j) \neq (k,l)$ and its 180°-rotation counterpart. – Christian Stump May 15 at 16:07
• Observation 2: $|p_{14} - p_{22}| \leq 1$ and $|p_{12}-p_{21}| \leq 2$ for all $4 \leq n \leq 13$, so either of these pairs might be a candidate for a witness for an affirmative answer to your question. – Christian Stump May 15 at 16:08
• @ChristianStump: I seriously doubt $(p_{12},p_{21})$ could work. – Sam Hopkins May 15 at 16:20
• @ChristianStump: $a_{12}$ will be greater than $a_{21}$ (by only 1) about $1/4$ of the time, because there are $C_{n-1}$ tableaux where the first column is $1,2$. But $a_{21}$ will be greater than $a_{12}$ by at least 1, and in fact sometimes much more, about $3/4$ of the time. So $p_{21}-p_{12}$ is gonna be at least $1/2$, not $o(1)$. – Sam Hopkins May 15 at 16:39

## 1 Answer

This is not a solution, but rather a long comment. Let $$f^{a,b}$$ denote the number of standard Young tableaux (SYT) of shape $$(a,b)$$. The number of SYT $$T$$ of shape $$(n,n)$$ with $$T_{1d}=k$$ is $$f^{d-1,k-d}f^{n-k+d,n-d}$$. Hence $$p_{1d} = \frac{1}{C_n}\sum_{k=d}^{2d-1} kf^{d-1,k-d}f^{n-k+d,n-d}.$$ There is a similar formula for $$p_{2,d}$$, though the number of terms in the sum increases as $$n\to\infty$$. In particular, $$\begin{eqnarray*} p_{12} & = & \frac{1}{C_n}\left( 2f^{n,n-2}+3f^{n-1,n-2}\right)\\ & = & \frac{1}{C_n}\left( \frac{2\cdot 3(2n-2)!}{(n+1)!(n-2)!} +\frac{3\cdot (2n-2)!}{n!(n-1)!}\right)\\ & = & \frac{3(3n-1)}{2(2n-1)}. \end{eqnarray*}$$ Write $$\bar{p}_{ij}=\lim_{n\to\infty}p_{ij}$$ (assuming this limit exists, which I believe is always the case). Thus $$\bar{p}_{12}=\frac 94$$.

Similarly, $$p_{21} = \frac{1}{C_n}\left( \sum_{k=2}^{n+1} kf^{n-1,n-k+1}\right).$$ Now $$\begin{eqnarray*} \frac{f^{n-1,n-k+1}}{C_n} & = & \frac{(2n-k)!(k-1)n!(n+1)!}{n!(n-k+1)!(2n)!}\\ & \to & \frac{k-1}{2^k}. \end{eqnarray*}$$ Thus (assuming we can interchange a limit and an infinite sum) $$\bar{p}_{21} = \sum_{k\geq 2}\frac{k(k-1)}{2^{k-1}} = 4$$ (modulo computational error). In general, $$\bar{p}_{1d}$$ will be given by a finite sum, and $$\bar{p}_{2d}$$ by an infinite series.

Addendum. I worked out $$\bar{p}_{1d}$$ in general, namely, $$\begin{eqnarray*} \bar{p}_{1d} & = & \sum_{k=d}^{2d-1} k(2d-k+1)f^{d-1,k-d}2^{-k}\\ & = & 2^{-2d+1}(d+1)\left(4^d-{2d+1\choose d}\right). \end{eqnarray*}$$ Beginning with $$d=2$$, the numbers are $$\frac 94,\ \frac{29}{8},\ \frac{325}{64},\ \frac{843}{128},\ \frac{4165}{512},\ \frac{9949}{1024},\ \frac{185517}{16384},\dots.$$ We can also write $$\bar{p}_{1,d-1} =2d-\frac{d{2d\choose d}}{4^{d-1}}.$$

Addendum #2. I worked out $$\bar{p}_{2d}$$. If my computation is correct, then $$\bar{p}_{2d} = 2d+\frac{d{2d\choose d}}{4^{d-1}}.$$ Compare with the formula for $$\bar{p}_{1,d-1}$$ above.

Is there a less computational reason for such simple formulas? Do they extend to shapes other than $$n(1,1)$$, e.g., $$n(1,1,1)$$ or $$n(2,1)$$?

• Richard, nope - I had a completely different thought. It is quite likely that for some number theoretic reason you don't have a coincidence of the kind you are describing. Rather, when looking at $(p_{1j} - 2j)$ and scaling everything to $[0,1]$ interval you get density given by the semicircle projection. Same for $(p_{2j} - 2j)$ but the semicircle is concave, not convex. Instead of looking at the beginning $j=O(1)$ as you suggest, look at the middle range. There is no obvious relation between two sets of values, so one would guess that $\beta(n) = O(1/\log n)$. – Igor Pak May 16 at 6:02
• One more thing - if you make denominators $4^n$, the numerator sequence is known and computed rather far: oeis.org/A018218 If the other sequence is also known, more values can be checked. – Igor Pak May 16 at 6:39
• Echoing what Igor is saying, it seems conceivable that $\beta(n) = o(1)$ without having $\overline{p}_{ij}=\overline{p}_{kl}$ for any $ij, kl$ because there could be e.g. a sequence $(a_n,b_n)$ of indices depending on $n$ with $|p_{1a_{n}} - p_{2b_n}| = o(1)$. – Sam Hopkins May 16 at 15:48
• Asymptotically, Richard's formulas give $2d\pm c\sqrt{d}$ formula which look exactly right from the semicircle POV. – Igor Pak yesterday
• @SamHopkins: Indeed, let $n\to \infty$. Let $a(d) := \overline p_{1d}$, $b(d):=\overline p_{2,d}$. Then $a(d) = 2d-c\sqrt{d} - c' + O(1/\sqrt{d})$, $b(d) = 2d+c/\sqrt{d} + c' + O(1/\sqrt{d})$, for some explicit $c,c'$. Then one should be looking at the fractional part of $a(d+\sqrt{d})-b(d) = 2c\sqrt{d} +c'' + O(1/\sqrt{d})$. It seems, $\sqrt{n}$ mod 1 is ergodic and rates of convergence are relatively well understood arxiv.org/abs/1311.6387 Thus, if one is careful one can possibly derive $\beta(n) = o(1)$ from here. – Igor Pak yesterday