Extending the discussion on "super Catalan" numbers

Question

Ira Gessel "dubbed" the name super Catalan to $$S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}$$ and offers a combinatorial proof in his paper

Note. The numbers $\frac12S(m,n)$ are also integers.

I would like to extend the discussion by asking for a proof that the following numbers, which I call super super Catalan numbers type 1, are integers $$S(x,y,z)=\frac13\frac{(3x)!(3y)!(3z)!}{x!^2y!^2z!^2(x+y+z)!}$$ and the same question of integrality about the numbers, which I call super super Catalan numbers of type 2, $$T(x,y,z)=\frac{x}3\frac{(3x)!(3y)!(3z)!}{x!^3y!^3z!^3(x+y+z)}$$ provided that $x, y, z$ are non-negative integers (plus $x+y+z>0$ for the latter).

Remark. It is evident that $\frac{(3x)!(3y)!(3z)!}{x!^3y!^3z!^3}$ are integral; the extra factor $x$ in the numerator of $T(x,y,z)$ is necessary, although $y$ or $z$ would do.

I don't have a proof to these claims, but I am convinced of their truth. Even a generating function method is acceptable, yet a combinatorial proof is much desirable.

Answer 1

I have a somewhat more algebraic proof than Jan-Christoph Schlage-Puchta's carry-based proof. I believe the idea goes back to Landau.

Let's start with your super super Catalan numbers type 1. A rational number $a$ is integer iff $v_p(a)\ge 0$ for all primes $p$. Hence, to prove integrality of those numbers, it suffices to show that $$(*) \forall p: v_p( \frac13\frac{(3x)!(3y)!(3z)!}{x!^2y!^2z!^2(x+y+z)!} ) \ge 0 .$$ Define the following function $f:\mathbb{R}^3 \to \mathbb{Z}$: $$ f(x_1,x_2,x_3) = \lfloor 3x_1 \rfloor + \lfloor 3x_2 \rfloor + \lfloor 3x_3 \rfloor - 2\left( \lfloor x_1 \rfloor + \lfloor x_2 \rfloor + \lfloor x_3 \rfloor \right) - \lfloor x_1+x_2+x_3 \rfloor.$$ Legendre has shown that $$v_p(n!) = \sum_{ k \ge1} \lfloor \frac{n}{p^k} \rfloor,$$ which implies that $$(**) v_p( \frac13\frac{(3x)!(3y)!(3z)!}{x!^2y!^2z!^2(x+y+z)!} ) = \sum_{k \ge 1} f(\frac{x}{p^k}, \frac{y}{p^k}, \frac{z}{p^k}) - \delta_{p=3}.$$ Hence, to establish $(*)$, at least for $p \neq 3$, it suffices to show that $f$ is always non-negative. Note that $f$ has period 1 in each of its variables. Hence, WLOG we may assume that $0\le x_i <1$, in which case $$(***) f(x_1,x_2,x_3) = \lfloor 3x_1 \rfloor + \lfloor 3x_2 \rfloor + \lfloor 3x_3 \rfloor - \lfloor x_1+x_2+x_3 \rfloor.$$ Write $x_i$ as $\frac{a_i}{3}+r_i$, where $a_i \in \{0,1,2\}$ and $0 \le r_i < \frac{1}{3}$. Then $(***)$ becomes $$f(x_1,x_2,x_3) = a_1+a_2+a_3 - \lfloor \frac{a_1+a_2+a_3}{3} + (r_1+r_2+r_3) \rfloor,$$ which is non-negative since $$\frac{a_1+a_2+a_3}{3} + (r_1+r_2+r_3) < \frac{a_1+a_2+a_3}{3} + 1 \le a_1+a_2+a_3 + 1.$$

---

What about $p=3$? Because of the extra term $-\delta_{p=3}=-1$ in $(**)$, we must show that at least one of the summands in $(**)$ is positive. If we let $k$ equal the largest integer such that $3^{k-1} \mid x,y,z$, and write the fractional values of $\frac{x}{3^k}, \frac{y}{3^k}, \frac{z}{3^k}$ as $\frac{a_1}{3} + r_1, \frac{a_2}{3}+r_2, \frac{a_3}{3} + r_3$, then: $$r_1=r_2=r_3=0, a_i \in \{0,1,2\}, a_1+a_2+a_3 \ge 1.$$ Hence, the calculations above imply that $$f(\frac{x}{3^k}, \frac{y}{3^k}, \frac{z}{3^k}) = a_1+a_2+a_3 -\lfloor \frac{a_1 + a_2+a_3}{3} \rfloor \ge 1, $$ which implies that the $k$'th summand in $(**)$ is positive.

---

As for the super super Catalan numbers of type 2, note that $$T(x,y,z) = S(x,y,z) \binom{x+y+z-1}{x-1,y,z},$$ so it is integer as a product of two integers.

---

Remark: The same method shows that $C_m(a_1,\cdots,a_n)=\frac{\prod_{i=1}^{n} (m \cdot a_i)!}{\prod_{i=1}^{n} a_i!^{m-1} (\sum a_i)!}$ is integer for all positive integers $a_1,\cdots,a_n,m$, and that $\frac{C_m}{m}$ is integer whenever $m$ is prime. Although I'm not sure that this is the "right" generalization of the super Catalan numbers.

Answer 2

Let $p\neq 3$ be a prime. Then \begin{eqnarray*} \nu_p\left(\frac{(3x)!}{x!^3}\right) & = & \sum_k \left[\frac{3x}{p^k}\right]-3\left[\frac{x}{p^k}\right]\\ & = & \sum_k 3\left\{\frac{x}{p^k}\right\} - \left\{\frac{3x}{p^k}\right\}\\ & = & \frac{3s_p(x)-s_p(3x)}{p-1}, \end{eqnarray*} where $s_p$ denotes sum of digits to base $p$. The last quantity equals the number of carries in the multiplication $3\cdot x$ and is certainly non-negative. We have to show that if $p^k|\frac{x+y+z}{(x,y,z)}$, then there are at least $k$ carries in the multiplications $3\cdot x$, $3\cdot y$, $3\cdot z$. We may assume that $(x,y,z)=1$. Now $x+y+z\equiv 0\pmod{p}$, but not all of $x,y,z$ are divisible by $p$, hence $x+y+z=\nu p$, $1\leq\nu\leq 2$, thus one of them is $>\nu p/3$, which implies there are at least $\nu$ carries at the last position. If $k=1$, we are done, otherwise let $x_2,y_2,z_2$ be the second to last digits of $x,y,z$. We have $x_2+y_2+z_2+\nu\equiv 0\pmod{p}$, thus one of $x_2,y_2,z_2$ is larger than $\frac{\mu p-\nu}{3}$, $1\leq\mu\leq 2$, together with the contribution $\nu$ coming from the carry in the last position we get $\mu$ carries here. Continuing in this way we find that the number of carries is at least $k$, hence $\nu_p\left(\frac{(x,y,z)(3x)!(3y)!(3z)!}{x!^3y!^3z!^3(x+y+z)}\right)$ is non-negative.

One could probably deal with $p=3$ in a similar way using the fact that to base 3, $3\cdot x$ automatically has a carry at the last position, although the details would become a little lengthy.