# Another extension of Catalan: divisibility

The classical Catalan numbers are given by $C_n=\frac1{n+1}\binom{2n}n$, for which there is a plethora of generalizations of interpretations in the literature. Still, let us consider one more such: $$C_n(k):=\binom{kn}{n,\dots,n}\prod_{j=0}^{k-1}\frac1{jn+1};$$ where the multinomial coefficient is simply $\frac{(kn)!}{n!^k}$.

Note. $C_n(2)=C_n$.

The following has been rediscovered many times and it is easy to prove: $C_n$ is odd iff $n=2^m-1$ for some $m$ (for example, see this paper by Postnikov and Sagan).

Such considerations prompted me to ask:

Question. Fix a prime $p$. Is this characterization valid? $$\text{C_n(p) is not divisible by p iff n=1+p+\cdots+p^m for some m}.$$

UPDATE. Both solutions are great, in particular, I appreciated the variation of techniques that went into them.

Here's a slightly different way to look at this. We have $$C_n(k)=\prod_{j=1}^{k}\left(\frac{1}{(j-1)n+1}\binom{jn}{n}\right).$$ And each factor $$\frac{1}{(j-1)n+1}\binom{jn}{n}=\binom{jn}{n}-(j-1)\binom{jn}{n-1}$$ is an integer. For $C_n(p)$ let us look at the last factor $\frac{1}{(p-1)n+1}\binom{pn}{n}$. Since $\binom{pn}{n}$ is always divisible by $p$ we can say that if $C_n(p)$ is not divisible by $p$ then $p$ must divide $(p-1)n+1$, or in other words $n$ must be $1\pmod{p}$. If $n$ is written as $a_r\cdots a_1a_0$ in base $p$ then we have $a_0=1$ and by Lucas's theorem $$\binom{pn}{n-1}\equiv \prod_{i=1}^{r}\binom{a_{i-1}}{a_{i}}\pmod{p}$$ Therefore in order for $\frac{1}{(p-1)n+1}\binom{pn}{n}$ not to be divisible by $p$ we must have $\binom{a_{i-1}}{a_{i}}\neq 0 \pmod{p}$. Therefore $1=a_0\geq a_1\geq \cdots \geq a_r$ which implies that all $a_i=1$. This is equivalent to saying $n=1+p+\cdots+p^r$ for some $r$. This also takes care of the other factors since for such $n$ we have $$\binom{jn}{n}\equiv j^r\neq 0 \pmod{p}.$$

The answer to your question is positive. Fix a prime $p$. Let $n$ be a positive integer. Let $T_1(n) = \binom{np}{n,\cdots,n}$, $T_2(n) = \prod_{j=0}^{p-1} (jn+1)$. You study $C_n(p)=\frac{T_1(n)}{T_2(n)}$.

Case 1: $p \mid n$. In this case, we have: $p \nmid T_2(n)$, since $jn+1 \equiv 1 \bmod p$. Moreover, $T_1(n) = \binom{np}{n} \binom{np-n}{n,\cdots,n} = \frac{np}{n} \binom{np-1}{n-1} \binom{np-n}{n, \cdots ,n}$ is divisible by $p$. Thus, $\frac{T_1(n)}{T_2(n)}$ is divisible by $p$.

Before the next main case, I prove a simple lemma.

Lemma: Let $p$ be a prime and let $a \in \{1,2,\cdots,p-1\}$. Then each $p$-adic digit of $-\frac{1}{a}$ is non-zero.

Proof of Lemma: If the $i$'th right-most digit is $0$, i.e. $$-\frac{1}{a} \equiv \overline{0 a_{i-2}\cdots a_0}_p \bmod {p^i},$$ then we have, after multiplying both sides by $a$, $$\overline{(p-1)(p-1)\cdots (p-1)}_p \equiv a \cdot \overline{0 a_{i-2}\cdots a_0}_p \bmod {p^i},$$ and we reach a contradiction as the RHS is smaller than the LHS. $\blacksquare$

Case 2: $p \nmid n$. We compute the $p$-adic valuation of $T_1(n)$, $T_2(n)$. It is well known that $v_p(n!) = \frac{n-S_p(n)}{p-1}$ where $S_p(n)$ is the sum-of-digits of $n$ in base $p$. Thus $$v_p(T_1(n)) = v_p((np)!) - p \cdot v_p(n!) = \frac{np-S_p(np)}{p-1} - p\frac{n-S_p(n)}{p-1} =$$ $$= \frac{p \cdot S_p(n) - S_p(np)}{p-1} = S_p(n).$$

Since $p\nmid n$, exactly one of the $p$ factors in $T_2(n)$ is divisible by $p$. Namely, if $n_0$ is the last digit of $n$ (i.e. $n\equiv n_0 \bmod p$, $n_0 \in \{1,2,\cdots, p-1\}$) and $m_0 \in \{ 1,\cdots,p-1\}$ satisfies $$n_0 m_0 = -1 \bmod p,$$ then $$v_p(T_2(n)) = v_p(m_0 n+1).$$ Hence, the problem reduces to the following assertion: $$S_p(n) \ge v_p (m_0 n+1), \text{ and equality holds iff }\exists k: n = \frac{p^k-1}{p-1}.$$ If $v_p(m_0 n+1)=j$ then $n \equiv \frac{-1}{m_0} \bmod {p^j}$. Let $y \in \{1,2,\cdots,p^j-1\}$ such that $y \equiv \frac{-1}{m_0} \bmod p^j$. We also denote it $\overline{\frac{-1}{m_0}}_{\bmod {p^j}}$. Since $S_p(n) \ge S_p( \overline{\frac{-1}{m_0}}_{\bmod {p^j}})$ with equality iff $n=\overline{\frac{-1}{m_0}}_{\bmod {p^j}}$, we have to prove that $$(*) \forall m_0 \in \{1,2,\cdots, p-1\}: S_p( \overline{\frac{-1}{m_0}}_{\bmod {p^j}} ) \ge j, \text{ and equality holds iff }m_0=p-1.$$ (Note that the $p$-adic expansion of $\frac{-1}{p-1}$ is all ones, and in particular is the $p$-adic limit of $\frac{p^k-1}{p-1}$.)

To prove $(*)$ note that the last digit is $\overline{\frac{-1}{m_0}}_{\bmod {p}} \ge 1$ (equality for $m_0=p-1$) and that all $p$-adic digits of $\frac{-1}{m_0}$ are non-zero by the Lemma.

Not an answer. This is experimentally true for $=3, 5, 7$ and $n\leq 10000.$