9
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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}.$$

$\endgroup$
0
8
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
0

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.