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.

  • $\begingroup$ $T$ is not symmetric. Is it what you mean? $\endgroup$ – Włodzimierz Holsztyński Sep 24 '16 at 6:37
  • $\begingroup$ I mean one can replace $x$ by $xyz$ to symmetrize, but one of the numbers $x, y$ or $z$ suffices for the claim of integrality. $\endgroup$ – T. Amdeberhan Sep 24 '16 at 6:52
  • $\begingroup$ Alexander Borisov says in his article "Quotient Singularities, Integer Ratios of Factorials, and the Riemann Hypothesis" (IMRN'08, arxiv version) that no combinatorial interpretation of the "super Catalan numbers" is known. He also cites works of Landau (the method described by Ofir in an answer below) and Picon on the integrality criteria of the quotients of factorials. $\endgroup$ – Ivan Izmestiev Sep 24 '16 at 16:12
  • $\begingroup$ After re-reading Gessel's paper I realized that he did not give a combinatorial proof, so thanks for the pointers. $\endgroup$ – T. Amdeberhan Sep 24 '16 at 16:23
  • $\begingroup$ @T.Amdeberhan Gessel gave a recursion, and it is natural to ask whether a similar recurssion exists for $S$ and $T$. $\endgroup$ – Ofir Gorodetsky Sep 24 '16 at 18:36

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.

  • $\begingroup$ Although I gave the case $n=3$ in the question, I already had that generalization and a similar one for the one with denominator $x+y+z$. $\endgroup$ – T. Amdeberhan Sep 24 '16 at 20:03

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.

  • $\begingroup$ $\nu_p$ is the $p$-adic valuation. Since $\frac{(3x)!}{x!^3}=\binom{3x}{2x}\binom{2x}{x}\in\mathbb{N}$ and by Legendre's formula $\nu_p(n!)=\frac{n−s_p(n)}{p−1}$, the first quantity you wrote is non-negative. $\endgroup$ – T. Amdeberhan Sep 24 '16 at 16:18
  • $\begingroup$ Yes, but being non-negative is not enough. We need it to be large enough to cancel the factor $(x+y+z)$. $\endgroup$ – Jan-Christoph Schlage-Puchta Sep 24 '16 at 16:24
  • $\begingroup$ I don't mean a proof, but an alternative verification of your first line. $\endgroup$ – T. Amdeberhan Sep 24 '16 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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