Return to Answer

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.

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.

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 \ge \frac{2(a_1+a_2+a_3-1)}{3}.$$ If $a_1,a_2,a_3=0$ then $f(x_1,x_2,x_3)=0\ge 0$. If $a_1+a_2+a_3 \ge 2$ then the above bound implies $f(x_1,x_2,x_3) \ge 1$. The case $a_1+a_2+a_3 =1$ may be checked by hand, and it gives the following: $f(x_1,x_2,x_3)=1$ if $r_1+r_2+r_3 < \frac{2}{3}$, and that $f(x_1,x_2,x_3)=0$ otherwise.

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}) \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.

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.

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 \ge \frac{2(a_1+a_2+a_3-1)}{3}.$$ If $a_1,a_2,a_3=0$ then $f(x_1,x_2,x_3)=0\ge 0$, and otherwise $a_1+a_2+a_3 \ge 1$ which implies $f(x_1,x_2,x_3) \ge 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. By the calculations above, $f(x,y,z)=0$ iff $\{ x\}, \{ y \}, \{ z \} \in [0,\frac{1}{3})$. If we let $k$ equal the largest integer such that $3^{k-1} \mid x,y,z$, then $\frac{x}{3^k}, \frac{y}{3^k}, \frac{z}{3^k}$ can't simultaneously be of the form $\text{integer} + \varepsilon (\in [0,\frac{1}{3}) )$, 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.

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 \ge \frac{2(a_1+a_2+a_3-1)}{3}.$$ If $a_1,a_2,a_3=0$ then $f(x_1,x_2,x_3)=0\ge 0$. If $a_1+a_2+a_3 \ge 2$ then the above bound implies $f(x_1,x_2,x_3) \ge 1$. The case $a_1+a_2+a_3 =1$ may be checked by hand, and it gives the following: $f(x_1,x_2,x_3)=1$ if $r_1+r_2+r_3 < \frac{2}{3}$, and that $f(x_1,x_2,x_3)=0$ otherwise.

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}) \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.