\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{mathrsfs}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}

\begin{center}
\vskip 1cm{\Large\bf 
Primes and Perfect Powers in the Catalan Triangle
}
\end{center}
\vskip 1cm

\begin{minipage}[t]{0.42\textwidth}
\begin{center}
Nathaniel Benjamin\\
Department of Mathematics \\
Iowa State University\\
Carver Hall,
411 Morrill Road \\
Ames, IA 50011 \\
USA\\ 
\href{mailto:nbenj582@iastate.edu}{\tt nbenj582@iastate.edu} \\
\ \\
Eugene Fiorini\\
Department of Mathematics \\
Muhlenberg College\\
2400 Chew Street \\
Allentown, PA 18104 \\
USA\\ 
\href{mailto:eugenefiorini@muhlenberg.edu}{\tt eugenefiorini@muhlenberg.edu} \\
\ \\
Eric Jovinelly\\
Department of Mathematics \\
Notre Dame University\\
255 Hurley \\
Notre Dame, IN 46556 \\
USA\\ 
\href{mailto:ejovinel@nd.edu}{\tt ejovinel@nd.edu} 
\end{center}
\end{minipage}
\begin{minipage}[t]{0.45\textwidth}
\begin{center}
Grant Fickes\\
Department of Mathematics \\
Kutztown University of Pennsylvania\\
15200 Kutztown Road \\
Kutztown, PA 19530 \\
USA\\ 
\href{mailto:gfick710@live.kutztown.edu}{\tt gfick710@live.kutztown.edu}\\
\ \\
Edgar Jaramillo Rodriguez\\
Department of Mathematics \\
University of California, Davis\\
1 Shields Avenue \\
Davis, CA 95616 \\
USA\\ 
\href{mailto:edgarjr@math.ucdavis.edu}{\tt edgarjr@math.ucdavis.edu} \\
\ \\
Tony W. H. Wong\\
Department of Mathematics \\
Kutztown University of Pennsylvania\\
15200 Kutztown Road \\
Kutztown, PA 19530\\
USA\\ 
\href{mailto:wong@kutztown.edu}{\tt wong@kutztown.edu}
\end{center}
\end{minipage}

\vskip .15in

\begin{abstract}
The Catalan triangle is an infinite lower-triangular matrix that generalizes the Catalan numbers. The entries of the Catalan triangle, denoted by $c_{n,k}$, count the number of shortest lattice paths from $(0,0)$ to $(n,k)$ that do not go above the main diagonal. This paper studies the occurrence of primes and perfect powers in the Catalan triangle. We prove that no prime powers except $2$, $5$, $9$, and $27$ appear in the Catalan triangle when $k\geq2$. We further prove that $c_{n,k}$ are not perfect semiprime powers when $k\geq3$. Finally, by assuming the $abc$ conjecture, we prove that aside from perfect squares when $k=2$, there are at most finitely many perfect powers among $c_{n,k}$ when $k\geq2$.
\end{abstract}


\section{Introduction}

A well-known theorem, first proved by Sylvester \cite{sylvester} and again by Erd\H{o}s \cite{erdos1934}, states that for all $n,k\in\N$ satisfying $2\leq k\leq n$, there is a prime $p>k$ such that $p$ divides
$$(n+k)(n+k-1)(n+k-2)\dotsb(n+1).$$ Erd\H{o}s \cite{erdos1951} later applied Sylvester's theorem to prove that if $4\leq k\leq n$, then $\binom{n+k}{k}$ is never a perfect power. In other words, the Diophantine equation
\begin{equation}\label{binomialpower}
\binom{n+k}{k}=x^\ell\text{ with }x\geq1,\ \ell\geq2,\text{ and }k\leq n
\end{equation}
has no positive integer solutions for $k\geq4$. Gy\H{o}ry \cite{Gyory} extended Erd\H{o}s's result to $k\geq2$, proving the only positive integer solutions to equation~\eqref{binomialpower} occur at $\binom{50}{3}=140^2$ or when $k=\ell=2$. These results motivate us to ask the same questions about the Catalan numbers and the Catalan triangle.

Let $n\in\N\cup\{0\}$. The Catalan numbers, defined as
$$C_n=\frac{1}{n+1}\binom{2n}{n},$$
form an integer sequence with rich combinatorial implications. They count the number of Dyck paths, the number of non-crossing partitions, the number of full binary trees, and the number of ways to insert parentheses, to name only a few examples. The number theoretic aspect of Catalan numbers is equally interesting, and numerous researches have been conducted on various divisibility and modulo properties of the Catalan numbers and their derivatives \cite{konvalinka,kg,ly,xx}.

The question of whether Catalan numbers can be perfect powers was answered negatively by Checcoli and D'Adderio \cite{cd}. Their proof was a simple application of a strong version of Bertrand's postulate by Ramanujan \cite{ramanujan}, and it is included here for completeness.

\begin{theorem}[\cite{cd}]\label{c_nn not power}
For all $n\in\N$ such that $n\geq2$, the $n$-th Catalan number $C_n$ is never a perfect power.
\end{theorem}

\begin{proof}
First, note that $C_2=2$, $C_3=5$, $C_4=14$, and $C_5=42$, so none of these are perfect powers. When $n\geq6$, by Ramanujan's theorem \cite{ramanujan}, there are at least two primes in the open interval $(n,2n)$. As a result, there is a least one prime $p$ in the interval $[n+2,2n)$. Therefore,
$$p\mid\mid C_n=\frac{2n(2n-1)(2n-2)\dotsb(n+2)}{n!},$$
i.e., $p\mid C_n$ but $p^2\nmid C_n$. Hence, $C_n$ cannot be a perfect power.
\end{proof}

The Catalan numbers can be generalized to the Catalan triangle. For all $n,k\in\N\cup\{0\}$ satisfying $n\geq k$, the entry $c_{n,k}$ in the Catalan triangle is given by the number of Dyck paths starting from the upper-left vertex $(0,0)$ to the vertex $(n,k)$ on the $n$-th row and the $k$-th column. Here, a Dyck path is a lattice path consisting of downward or rightward steps without visiting the region above the diagonal $n=k$. The first few rows in the Catalan triangle are depicted below.
\begin{equation}\label{catalan triangle}
\begin{matrix}
    1 \\
    1 & 1 \\
    1 & 2 & 2 \\
    1 & 3 & 5 & 5 \\
    1 & 4 & 9 & 14 & 14 \\
    1 & 5 & 14 & 28 & 42 & 42 \\
    \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{matrix}
\end{equation}

Note that the rows and columns are indexed by $\N\cup\{0\}$, so the topmost row and the leftmost column are referred to as the zeroth row and the zeroth column respectively. The entry on the $n$-th row and the $k$-th column is $c_{n,k}$. In particular, the diagonal entries are $c_{n,n}=C_n$. The general formula for the entries of the Catalan triangle is given by
\begin{equation} \label{catalan formula}
c_{n,k}=\frac{n-k+1}{n+1}\binom{n+k}{k}=\frac{(n+k)(n+k-1)(n+k-2)\dotsb(n+2)(n-k+1)}{k!},
\end{equation}
and for all $1\leq k<n$, they satisfy the recursion relation
\begin{equation} \label{catalan recursion}
c_{n,k}=c_{n-1,k}+c_{n,k-1}.
\end{equation}

Observe that the first column of the Catalan triangle in \eqref{catalan triangle} is the sequence $(c_{n,1})_{n\geq1}$, where $c_{n,1}= \frac{n-1+1}{n+1}\binom{n+1}{1}=n$ for all $n\in\N$. As a result, every positive integer appears at least once in the Catalan triangle. Nevertheless, not all positive integers appear more than once in the Catalan triangle. The sequence of positive integers that appear uniquely in the Catalan triangle was added by the authors to the On-Line Encyclopedia of Integer Sequences (OEIS), listed as \seqnum{A275481} \cite{oeis}, and its complement is listed as \seqnum{A275586} \cite{oeis}.

The algorithm to search for positive integers that appear uniquely in the Catalan triangle is given in the aforementioned OEIS entries, and it relies on the following lemma.

\begin{lemma}\label{increasing}
For all $n,k\in\N$ such that $n\geq k$, the following statements hold.
\begin{itemize}
\item For all $n'\in\N$ such that $n<n'$, $c_{n,k}<c_{n',k}$.
\item For all $k'\in\N$ such that $k<k'\leq n$, $c_{n,k}\leq c_{n,k'}$, where equality holds if and only if $n=k+1$.
\item $c_{n,k}<c_{n+1,k+1}$.
\end{itemize}
\end{lemma}

\begin{proof}
Since every entry in the Catalan triangle is positive by definition, from the recursion relation in equation~\eqref{catalan recursion}, we have
$$c_{n,k}<c_{n,k}+c_{n+1,k-1}=c_{n+1,k}.$$
Hence, for any fixed $k\in\N$, $c_{n,k}$ strictly increases with $n\geq k$. This proves the first statement. Also, when $n>k+1$,
$$c_{n,k}<c_{n-1,k+1}+c_{n,k}=c_{n,k+1}.$$
Together with the observation that
$$c_{k+1,k}=\frac{2}{k+2}\binom{2k+1}{k}=\frac{2k+2}{(k+2)(k+1)}\cdot\frac{(2k+1)!}{k!(k+1)!}=\frac{1}{k+2}\binom{2k+2}{k+1}=c_{k+1,k+1},$$
the second statement follows. Finally, the third statement is an immediate consequence of the prior two.
\end{proof}

By algorithmically computing the sequence \seqnum{A275481}, we observe that most perfect powers appear uniquely in the Catalan triangle. In other words, $c_{n,k}$ are rarely perfect powers when $2\leq k\leq n$. We prove in Section~\ref{primes sec} that for $2\leq k\leq n$, $c_{n,k}$ cannot be prime nor a perfect prime power except when $c_{n,k}=2$, $5$, $9$, or $27$. Furthermore, we prove that for $3\leq k\leq n$, $c_{n,k}$ cannot be a perfect power of semiprimes. We prove in Section~\ref{powers sec} there are infinitely many perfect squares in the Catalan triangle when $k=2$. By assuming the $abc$ conjecture, we then show the scarcity of squarefull numbers among $c_{n,k}$ when $k\geq4$, thus proving that, other than those $c_{n,2}$ that are perfect squares, there are at most finitely many perfect powers when $k\geq2$. A positive integer $m$ is \textit{squarefull} if for all primes $p\mid m$, we also have $p^2\mid m$. In other words, no exponent in the prime power factorization of $m$ is $1$. A squarefull number is also called \textit{powerful} in the literature. Our proof utilizes a strong result of Granville \cite{granville} related to the $abc$ conjecture.


\section{Prime powers and perfect semiprime powers in the Catalan triangle}\label{primes sec}
We begin with a simple result on the occurrence of primes in the Catalan triangle.
\begin{lemma}\label{c_nk prime}
For all $n,k\in\N$ such that $2\leq k\leq n$, if $c_{n,k}$ is a prime, then $c_{n,k}=2$ or $5$.
\end{lemma}

\begin{proof}
From the Catalan triangle \eqref{catalan triangle}, we observe that the statement is true for $n\leq 4$. Hence, it suffices to prove that $c_{n,k}$ is composite when $k\geq2$ and $n\geq\max\{k,5\}$.

We will proceed by induction on $k$. When $k=2$, by equation~\eqref{catalan formula}, $c_{n,2}=\frac{(n+2)(n-1)}{2}$, which is composite since both $n+2$ and $n-1$ are greater than $2$.

Suppose that for some $k\geq2$, $c_{n,k}$ is composite for all $n\geq\max\{k,5\}$. For all $n\geq k+1$,
\begin{align*}
c_{n,k+1}&=\frac{n-(k+1)+1}{n+1}\binom{n+k+1}{k+1}\\
&=\frac{(n-k)(n+k+1)}{(n+1)(k+1)}\binom{n+k}{k}\\
&=\frac{(n-k)(n+k+1)}{(k+1)(n-k+1)}c_{n,k}.
\end{align*}

Let $\frac{(n-k)(n+k+1)}{(k+1)(n-k+1)}=\frac{a}{b}$, where $a,b\in\N$ such that $\gcd(a,b)=1$. Since $c_{n,k+1}$ is an integer, we have $b\mid c_{n,k}$. In other words, $c_{n,k+1}$ is the product of two integers $a$ and $\frac{c_{n,k}}{b}$. If $b=1$, then $c_{n,k+1}=a\cdot c_{n,k}$ is composite by the induction hypothesis. If $b>1$, then $a>1$ since $a\geq b$ by Lemma~\ref{increasing}. Also, $\frac{c_{n,k}}{b}>1$; otherwise, $c_{n,k}=b\leq(k+1)(n-k+1)$, which implies
\begin{align*}
k+1&\geq\frac{(n+k)(n+k-1)(n+k-2)\dotsb(n+2)}{k!}\\
(k+1)!&\geq(n+k)(n+k-1)(n+k-2)\dotsb(n+2)\\
&\geq(k+5)(k+4)(k+3)\dotsb7\\
&\geq7\cdot6\cdot5\cdot4\cdot(k+1)k(k-1)\dotsb7\\
&>(k+1)k(k-1)\dotsb7\cdot6\cdot5\cdot4\cdot(3\cdot2\cdot1)=(k+1)!,
\end{align*}
a contradiction. Therefore, $c_{n,k+1}$ is composite.
\end{proof}

To prove the uniqueness of prime powers in the Catalan triangle, we will use the following lemma, which is a moderate strengthening of Sylvester's theorem \cite{sylvester} based on Faulkner's results \cite{faulkner}.

\begin{lemma}\label{faulkner modified}
For all $n,k\in\N$ such that $2\leq k\leq n$, $(n+k)(n+k-1)\dotsb(n+2)$ has a prime factor $q\geq k+1$ except when $(n,k)=(6,3)$ or $(2^\alpha-2,2)$, where $\alpha\geq2$ is an integer.
\end{lemma}

\begin{proof}
For convenience, let $N=n+k$, so that it suffices to prove the following statement.
\begin{quote}
If $k\geq2$ and $N\geq2k$, then $N(N-1)\dotsb(N-k+2)$ has a prime factor $q\geq k+1$ except when $(N,k)=(9,3)$ or $(2^\alpha,2)$, where $\alpha\geq2$ is an integer.
\end{quote}

By Faulkner's result \cite{faulkner}, if $N\geq2K$, then $\binom{N}{K}$, or equivalently, $N(N-1)\dotsb(N-K+1)$, has a prime factor $q\geq\frac{7}{5}K$. Substituting $K=k-1$, if $N\geq2(k-1)$, then
$$N(N-1)\dotsb(N-k+2)$$
has a prime factor $q\geq\frac{7}{5}(k-1)$. Note that $\frac{7}{5}(k-1)\geq k+1$ if and only if $k\geq6$, so our lemma is proved for $k\geq6$.

When $k=2$, then $N$ does not have a prime factor $q\geq3$ if and only if $N=2^\alpha$ for some integer $\alpha\geq2$. 

When $k=3$, if $N(N-1)$ does not have a prime factor $q\geq4$, then $N(N-1)$ only has factors $2$ and $3$, which happens only when one of $N$ and $N-1$ is a power of $2$ and the other is a power of $3$. Also, as $N\geq2k$, both numbers are at least $5$. Mih\u{a}ilescu's theorem \cite{mihailescu} implies that the only pair of consecutive integers $(N,N-1)$ that satisfies these conditions is $(9,8)$, meaning $(N,k)=(9,3)$. 

When $k=4$, it follows directly from the case when $k=3$, since any prime factor $q\geq4$ is at least $5$.

When $k=5$, if $\prod_{i=0}^{3}(N-i)$ does not have a prime factor $q\geq6$, then its only prime factors are $2$, $3$, and $5$. Let the prime factorization of $N-i$ be $2^{\alpha_i}3^{\beta_i}5^{\gamma_i}$, where $i=0,1,2,3$. Note that exactly two $\alpha_i$'s are positive, with one of them equal to $1$. Note also that at most two $\beta_i$'s are positive, and if two are positive, then one of them is $1$. Finally, at most one $\gamma_i$ is positive. As $N\geq2k$, all four numbers $N$, $N-1$, $N-2$, and $N-3$ are at least $7$. Since there are at most $5$ indices that are positive, we must have three of those four numbers being divisible by a power of $2$, a power of $3$, and a power of $5$ respectively. Finally, the remaining number is at most $2\times3=6$, which is a contradiction.
\end{proof}

We are now ready to prove the following two theorems, which are the main results of this section on the occurrence of prime powers and semiprime powers in the Catalan triangle.

\begin{theorem}\label{c_nk prime power}
The only positive integer solutions to the Diophantine equation
$$c_{n,k}=p^\ell$$
with $2\leq k\leq n$, $\ell \geq 1$, and prime $p$ are
$$(n,k,p^\ell)=(2,2,2),(3,2,5),(3,3,5),(4,2,9),\text{or }(7,2,27).$$
\end{theorem}

\begin{proof}
First, consider the case $k=2$. Suppose that 
$$c_{n,2}=\frac{(n+2)(n-1)}{2}=p^\ell$$
for some $n,p,\ell\in\N$ such that $n\geq2$ and $p$ is a prime. If $n-1=1$ or $2$, then
$$(n,k,p^\ell)=(2,2,2)\text{ or }(3,2,5)$$
respectively. If $n-1>2$, then $p$ divides $n-1$ and $n+2$, implying that $p\mid(n+2)-(n-1)=3$, i.e., $p=3$.

Let $n-1=3m$ for some $m\in\N$. Then
$$3^\ell=\frac{(3m+3)(3m)}{2}=9\cdot\frac{(m+1)m}{2}.$$
If $m>2$, then $3$ divides both $m$ and $m+1$, which is impossible. Hence, $m=1$ or $2$, which gives $(n,k,p^\ell)=(4,2,9)$ or $(7,2,27)$ respectively.

Next, consider the case $k>2$. If $c_{n,k}$ is a prime, by Lemma~\ref{c_nk prime}, $c_{n,k}=2$ or $5$. From the Catalan triangle \eqref{catalan triangle}, $(n,k,p^\ell)=(3,3,5)$ is a solution. Also, from Lemma~\ref{increasing}, we know that $(n,k,p^\ell)=(3,3,5)$ is the only solution when $k>2$. If $c_{n,k}$ is a perfect prime power, by Theorem~\ref{c_nn not power}, we have $n\geq k+1$. Furthermore, we can assume that $(n,k)\neq(6,3)$ since $c_{6,3}=48$ is not a perfect prime power.

Let $S= \{n+k,n+k-1,\dotsc,n+2\}$. By Lemma~\ref{faulkner modified}, there exists a prime $q\geq k+1$ such that $q\mid\prod_{s\in S}s$. As $q$ is relatively prime with $k!$, which is the denominator of equation~\eqref{catalan formula}, in order for $c_{n,k}=p^\ell$, we have $p=q$. Also, since the difference between the largest and the smallest elements in $S$ is $k-2<p$, there is a unique element $s\in S$ such that $p\mid s$, and $\prod_{s'\in S\setminus\{s\}}s'$ must divide $k!$. This implies that
\begin{align*}
k!&\geq\prod_{s'\in S\setminus\{s\}}s'\\
&\geq(n+k-1)(n+k-2)(n+k-3)\dotsb(n+2)\\
&\geq2k(2k-1)(2k-2)\dotsb(k+3)\\
&>2k(k-1)(k-2)\dotsb(3)=k!,
\end{align*}
which is a contradiction.
\end{proof}

\begin{theorem}\label{semiprimes}
There are no positive integer solutions to the Diophantine equation
$$c_{n,k}=(pq)^\ell$$
with $3\leq k\leq n$, $\ell\geq2$, and distinct primes $p$ and $q$.
\end{theorem}

\begin{proof}
First, consider the case $k=3$. Suppose that
$$c_{n,3}=\frac{(n+3)(n+2)(n-2)}{6}=(pq)^\ell$$
for some $n,p,\ell\in\N$ such that $n\geq3$, $\ell\geq2$, and $p$ and $q$ are distinct primes. By computer exhaustion, we check that there are no integer solutions for $n\leq 122$. Consider $n>122$. Since $n+3$ and $n+2$ are greater than $6$ and are relatively prime, assume without loss of generality that $p\mid(n+3)$ and $q\mid(n+2)$. As $\gcd(n+3,n-2)\mid5$ and $\gcd(n+2,n-2)\mid4$, we have
\begin{align*}
(n+3,n+2,n-2)=&\hspace{2pt}(\alpha p^\ell,\beta q^\ell,\gamma),\ (\alpha 5^{\ell_1},\beta q^\ell,\gamma5^{\ell-\ell_1}),\\
&\hspace{2pt}(\alpha p^\ell,\beta2^{\ell_2},\gamma2^{\ell-\ell_2}),\text{ or }(\alpha5^{\ell_1},\beta2^{\ell_2},\gamma5^{\ell-\ell_1}2^{\ell-\ell_2}),
\end{align*}
where $\alpha,\beta,\gamma\in\N$, $\alpha\beta\gamma=6$, $\ell_1=1$ or $\ell-1$, and $\ell_2=1$, $2$, $\ell-2$, or $\ell-1$. Note that
\begin{align*}
\min\{\alpha p^\ell,\beta q^\ell,\gamma\}&\leq6,\\
\min\{\alpha 5^{\ell_1},\beta q^\ell,\gamma5^{\ell-\ell_1}\}&\leq6\cdot5=30,\\
\min\{\alpha p^\ell,\beta2^{\ell_2},\gamma2^{\ell-\ell_2}\}&\leq6\cdot4=24,\text{ and}\\
\min\{\alpha5^{\ell_1},\beta2^{\ell_2},\gamma5^{\ell-\ell_1}2^{\ell-\ell_2}\}&\leq6\cdot5\cdot4=120.
\end{align*}
All these violate the condition that $n>122$. Hence, no positive integer solutions exist when $k=3$.

Next, consider the case $k>3$. Without loss of generality, let $p>q$. By Lemma~\ref{faulkner modified}, it follows that $p>k$. Let $T=\{n+k,n+k-1,\dotsc,n+2,n-k+1\}$. If $p^\ell\mid t_0$ for some $t_0\in T$, then
$$(p^\ell-1)(p^\ell-2)\dotsb(p^\ell-k+2)(p^\ell-2k+1)\leq\prod_{t\in T\setminus\{t_0\}}t=\frac{p^\ell q^\ell k!}{t_0}\leq q^\ell\cdot k!.$$
Since $q<p$ and $k<p$, we have $q^\ell\leq(p-1)^\ell<p^\ell-2k+1$ and $k^2\leq (p-1)^2<p^\ell-2k+1$. As a result,
$$k^{2k-4}<(p^\ell-1)(p^\ell-2)\dotsb(p^\ell-k+2)<k!,$$
which is a contradiction since $k\geq4$. Note that the difference between the largest and the smallest elements in $T$ is $2k-1<2p$, and the difference between the largest and the second smallest elements in $T$ is $k-2<p$. So we must have $p^{\ell_1}\mid\mid (n-k+1)$ and $p^{\ell-\ell_1}\mid\mid t_1$ for a unique $t_1\in T\setminus\{n-k+1\}$, where $\ell_1=1$ or $\ell-1$.

When $\ell>2$, depending on $\ell_1=1$ or $\ell-1$, we have either
$$(p^{\ell-1}-1)(p^{\ell-1}-2)\dotsb(p^{\ell-1}-k+2)(p^{\ell-1}-2k+1)\leq\prod_{t\in T\setminus\{t_1\}}t=\frac{p^\ell q^\ell k!}{t_1}\leq pq^\ell\cdot k!$$
or
$$(p^{\ell-1}+2k-1)(p^{\ell-1}+2k-2)\dotsb(p^{\ell-1}+k-1)\leq pq^\ell\cdot k!.$$
In either case, since $q^{\ell-1}\leq p^{\ell-1}-2k+1$, we always have
$$(p^{\ell-1}-1)(p^{\ell-1}-2)\dotsb(p^{\ell-1}-k+2)\leq pq\cdot k!.$$
Furthermore, as $pq< p(p-1)<p^{\ell-1}-k+2$, $p^{\ell-1}-1\geq5^2-1=4!$, and $p^{\ell-1}-2>k$, we have
$$4!\cdot k(k-1)\dotsb5<4!\cdot(p^{\ell-1}-2)(p^{\ell-1}-3)\dotsb(p^{\ell-1}-k+3)<k!,$$
a contradiction. When $\ell=2$, note that $n\geq p+k-1$ and $k<p<2k$ since $p\mid\mid (n-k+1)$ and $p\mid\mid t_1$. Hence, if $k\geq6$, then
\begin{align*}
pq^2\cdot k!&\geq(n+k)(n+k-1)\dotsb(n+2)\\
&\geq(p+2k-1)(p+2k-2)\dotsb(p+k+1)\\
&>(p+2k-1)(p+2k-2)\dotsb(p+k+4)\left(\frac{3p}{2}\right)^3\\
&>\frac{27}{8}(3k)(3k-1)\dotsb(2k+5)\cdot pq^2\\
&>\frac{27}{8}(3k)(3(k-1))(k-2)(k-3)\dotsb5\cdot pq^2>k!\cdot pq^2,
\end{align*}
a contradiction. If $k\leq5$, then $p\leq7$, and $q\leq5$. As a result, $c_{n,k}\leq(7\cdot5)^2=1225$. Since $c_{12,4}=1260$ and $c_{10,5}=1638$, by Lemma~\ref{increasing}, we only need to consider $n<12$ when $k=4$ and $n<10$ when $k=5$. By computer exhaustion, $c_{n,k}$ are never perfect squares for $n<12$ when $k=4$ and $n<10$ when $k=5$3, which completes our proof.
\end{proof}

\section{Scarcity of perfect powers and squarefull numbers}\label{powers sec}

The previous section showed that there are only two perfect prime powers in the Catalan triangle when $k=2$, and no perfect prime powers nor perfect semiprime powers when $k\geq3$. This section addresses the general question of the occurrence of perfect powers in the Catalan triangle. One of the authors constructed an algorithm to search for perfect powers that appear nonuniquely in the Catalan triangle. The sequence, together with the algorithm, is listed on the OEIS as \seqnum{A317027} \cite{oeis}. Note that \seqnum{A317027} is an infinite sequence since there are infinitely many perfect squares in the Catalan triangle when $k=2$, due to the following theorem.

\begin{theorem}\label{k=2ell=2}
The Diophantine equation
$$c_{n,k}=x^\ell$$
has infinitely many integer solutions with $x\geq1$, $2=k\leq n$, and $\ell=2$.
\end{theorem}

\begin{proof}
For any positive integer solution pair $(X_{0},Y_0)$ to Pell's equation
$$X^2-2Y^2=1,$$
let $n=3X_{0}^2-2$. Note that $n=6Y_0^2+1$. Hence,
$$c_{n,2}=\frac{(n+2)(n-1)}{2}=\frac{3X_{0}^2\cdot6Y_0^2}{2}=(3X_{0}Y_0)^2.$$
Since Pell's equation has infinitely many integer solutions, the proof is complete.
\end{proof}

The conditions that $k=2$ and $\ell=2$ in Theorem~\ref{k=2ell=2} are both essential. If either condition is relaxed, then the results change drastically, as shown in Theorem~\ref{2<=k<=3} and Corollary~\ref{k>=4}.

\begin{theorem}\label{2<=k<=3}
There are at most finitely many positive integer solutions to the Diophantine equation
$$c_{n,k}=x^\ell$$
with
\begin{enumerate}[$(a)$]
\item $x\geq1$, $3=k\leq n$ and $\ell=2$; or
\item $x\geq1$, $2\leq k\leq 3$, $k\leq n$, and $\ell\geq3$.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}[$(a)$]
\item When $3=k\leq n$ and $\ell=2$, the equation $c_{n,k}=x^\ell$ can be rewritten as
$$(n+3)(n+2)(n-2)=6x^2.$$

This equation defines a genus 1 curve, and hence by Siegel's theorem on integral points \cite{siegel}, there are at most finitely many positive integer solutions for $n$ on this elliptic curve.

\item First, consider $k=2$. Assume that $c_{n,2}=x^\ell$ for some positive integers $n\geq2$, $x$, and $\ell\geq3$. Then
\begin{equation}\label{k=2}
(n+2)(n-1)=2x^\ell.
\end{equation}

Let $g=\gcd(n+2,n-1)$. Then clearly $g\mid3$. Equation~\eqref{k=2} implies that $\frac{n+2}{g}=aX^\ell$ and $\frac{n-1}{g}=bY^\ell$ for some $a,b,X,Y\in\N$, where $\gcd(a,b)=1$ and $ab=2g^{\ell-2}$. Hence,
\begin{equation} \label{Thue1}
    aX^\ell-bY^\ell=\frac{3}{g}.
\end{equation}

Let $\mathscr{S}=\{s\in\Z:p\text{ is a prime and }p\mid s\Rightarrow p\in\{2,3\}\}$, i.e., $\mathscr{S}$ is the set of integers not divisible by primes outside $\{2,3\}$. Since $a,b,\frac{3}{g}\in\mathscr{S}$, Gy\H{o}ry and Pint\'{e}r \cite{gp} proved that there are at most finitely many integer solutions $(X^\ell,Y^\ell)$ with $\ell\geq3$ for the Thue equation \eqref{Thue1}. As a result, there are at most finitely many positive integer solutions for $c_{n,2}=x^\ell$.

Next, consider $k=3$. Assume that $c_{n,3}=x^\ell$ for some positive integers $n\geq3$, $x$, and $\ell\geq3$. Then
\begin{equation}\label{k=3}
(n+3)(n+2)(n-2)=6x^\ell.
\end{equation}
Let $g_1=\gcd(n+3,n-2)$ and $g_2=\gcd(n+2,n-2)$. Then clearly $g_1\mid5$ and $g_2\mid4$. Equation~\eqref{k=3} implies that $\frac{n+3}{g_1}=aX^\ell$, $\frac{n+2}{g_2}=bY^\ell$, and $\frac{n-2}{g_1g_2}=cZ^\ell$ for some $a,b,c,X,Y,Z\in\N$, where $a,b,c$ are pairwise relatively prime and $abc\mid6g_1^{\ell-2}2^{\ell-2}$. Hence,
\begin{equation}\label{Thue2}
    g_1aX^\ell-g_2bY^\ell=1.
\end{equation}

Let $\mathscr{T}=\{t\in\Z:p\text{ is a prime and }p\mid t\Rightarrow p\in\{2,3,5\}\}$, i.e., $\mathscr{T}$ is the set of integers not divisible by primes outside $\{2,3,5\}$. Since $g_1a,g_2b,1\in\mathscr{T}$, again by Gy\H{o}ry and Pint\'{e}r's results \cite{gp}, there are at most finitely many integer solutions $(X^\ell,Y^\ell)$ with $\ell\geq3$ for the Thue equation \eqref{Thue2}. As a result, there are at most finitely many positive integer solutions for $c_{n,3}=x^\ell$.
\end{enumerate}
\end{proof}

To prove that there are at most finitely many perfect powers in the Catalan triangle with $k\geq4$, we expand our consideration to squarefull numbers. Lemma~\ref{faulkner modified} implies that when $4\leq k\leq n<2k$, $c_{n,k}$ is not squarefull, as $c_{n,k}$ is divisible by a prime $q\geq k+1$ but not divisible by $q^2$. Assuming the $abc$ conjecture, we can further show that there are at most finitely many perfect powers in the Catalan triangle with $k\geq4$.

\theoremstyle{plain}\newtheorem*{abcconj}{The $abc$ conjecture}
\begin{abcconj}
For all $\epsilon>0$, there exists $M>0$ such that for all relatively prime positive integers $a,b,c$ that satisfy $a+b=c$,
$$c^{1-\epsilon}\leq M\prod_{\substack{p\textup{ is prime}\\p\mid abc}}p.$$
\end{abcconj}

Granville \cite{granville} applied the $abc$ conjecture to prove the following theorem.

\begin{theorem}[\cite{granville}]\label{>>}
For all $3\leq k\leq n$, let $a_{n,k}=\prod_{p\mid\mid\binom{n+k}{k}}p$. The $abc$ conjecture implies that
$$a_{n,k}>>_\epsilon\binom{n+k}{k}^{1-2/k-\epsilon}.$$
In other words, for all $\epsilon>0$, there exist $M,n_0>0$ such that for all $n\geq n_0$,
$$a_{n,k}\geq M\binom{n+k}{k}^{1-2/k-\epsilon}.$$
\end{theorem}

Note that the above theorem is uniform in $k$. Now, we use Granville's result to prove the following theorem.

\begin{theorem}\label{squarefull}
The $abc$ conjecture implies that there are at most finitely many squarefull $c_{n,k}$ for $4\leq k\leq n$.
\end{theorem}

\begin{proof}
First, consider $k=4$. The proof technique for the case $k=4$ is similar to that in the proof of Proposition 3 in Granville's paper \cite{granville}. Suppose that $c_{n,4}$ is squarefull. Then for all primes $p>4$ such that $p\mid(n+4)(n+3)(n+2)(n-3)$, we also have $$p^2\mid(n+4)(n+3)(n+2)(n-3).$$
Let $n-3=\tau_1\eta_1$, and $n+i=\tau_i\eta_i$ for each $i=2,3,4$, where $\tau_i$ is squarefree, $\eta_i$ is squarefull, and $\gcd(\tau_i,\eta_i)=1$ for all $i=1,2,3,4$. Since $(n+4)-(n-3)=7$, by the assumptions, all prime factors of $\tau_i$ are at most $7$. Hence,
$$\prod_{\substack{p\text{ is prime}\\p\mid\tau_1\tau_2\tau_3\tau_4}}p\leq2\times3\times5\times7=210.$$

Let $\epsilon=\frac{1}{5}$. Applying the $abc$ conjecture, there exists $M>0$ such that if $a=(n+4)(n+2)$, $b=1$, and $c=(n+3)^2$, then
\begin{align*}
(n+3)^{2(1-\epsilon)}&\leq M\prod_{\substack{p\text{ is prime}\\p\mid(n+4)(n+2)(n+3)^2}}p\\
&=M\left(\left(\prod_{\substack{p\text{ is prime}\\p\mid\tau_2\tau_3\tau_4}}p\right)^{\frac{1}{2}}\prod_{\substack{p\text{ is prime}\\p\mid\eta_2\eta_3\eta_4}}p\right)\left(\prod_{\substack{p\text{ is prime}\\p\mid\tau_2\tau_3\tau_4}}p\right)^{\frac{1}{2}}\\
&\leq M\big((n+4)(n+3)(n+2)\big)^{\frac{1}{2}}\sqrt{210}<M\sqrt{210}(n+4)^{\frac{3}{2}},
\end{align*}
which is a contradiction for sufficiently large $n$.

Next, consider $k\geq5$. For all $5\leq k\leq n$, let $b_{n,k}=\prod_{p\mid\mid c_{n,k}}p$. By Theorem~\ref{>>}, the $abc$ conjecture implies that when $\epsilon=\frac{1}{10}$, there exist $M,n_0>0$ such that for all $n\geq n_0$, $a_{n,k}\geq M\binom{n+k}{k}^{1-2/k-1/10}$. Hence,
$$b_{n,k}\geq\frac{a_{n,k}}{(n+1)(n-k+1)}\geq \frac{M{n+k\choose k}^{1-2/5-1/10}}{(n+1)(n-k+1)}\geq \frac{M{n+5\choose 5}^{1/2}}{(n+1)(n-k+1)} >\frac{Mn^{5/2}}{5!n^2}=\frac{M}{120}n^{1/2}.$$
Thus $b_{n,k}>1$ whenever $n\geq\max\{n_0,(\frac{120}{M})^2\}$, in which case $c_{n,k}$ is not squarefull.
\end{proof}

Since a perfect power is squarefull, we immediately have the following corollary.

\begin{corollary}\label{k>=4}
The $abc$ conjecture implies that there are at most finitely many positive integer solutions to the Diophantine equation
$$c_{n,k}=x^\ell$$
with $x\geq1$, $4\leq k\leq n$, and $\ell\geq2$.
\end{corollary}

Theorem~\ref{k=2ell=2} showed that there are infinitely many perfect squares in the Catalan triangle when $k=2$. Furthermore, we have shown through Theorem~\ref{2<=k<=3} and Corollary~\ref{k>=4} that, other than those perfect squares given in Theorem~\ref{k=2ell=2}, there are at most finitely many perfect powers when $k\geq2$, provided the $abc$ conjecture holds. However, by observing the list of perfect powers in the sequence \seqnum{A275481}, we conclude our paper with the following conjecture.

\begin{conjecture}
Consider the Diophantine equation
$$c_{n,k}=x^\ell.$$
\begin{enumerate}[$(a)$]
\item When $x\geq1$, $2=k\leq n$, and $\ell\geq3$, the only solutions are $(n,x^\ell)=(7,27)$ and $(126,8000)$.
\item When $x\geq1$, $3\leq k\leq n$ and $\ell\geq2$, there are no positive integer solutions.
\end{enumerate}
\end{conjecture}
These results are based upon work supported by the National Science Foundation under the grant number DMS-1560019, as well as the Kutztown University Bringing Experiences About Research in Summer (KU BEARS) and the Muhlenberg College Summer Research Program. 


\begin{thebibliography}{99}

\bibitem{cd}
S.~Checcoli and M.~D'Adderio, Perfect powers in Catalan and Narayana numbers, preprint, 2013. Available at \url{https://arxiv.org/abs/1306.5929}.

\bibitem{erdos1934}
P.~Erd\H{o}s, A theorem of Sylvester and Schur, \textit{J.\ London Math.\ Soc.\/} \textbf{9} (1934), 282--288.

\bibitem{erdos1951}
P.~Erd\H{o}s, On a diophantine equation, \textit{J.\ London Math.\ Soc.\/} \textbf{26} (1951), 176--178.

\bibitem{faulkner}
M.~Faulkner, On a theorem of Sylvester and Schur, \textit{J.\ London Math.\ Soc.\/} \textbf{41} (1966), 107--110.

\bibitem{granville}
A.~Granville, On the scarcity of powerful binomial coefficients, \textit{Mathematika} \textbf{46} (1999), 397--410.

\bibitem{Gyory}
K.~Gy\H{o}ry, On the diophantine equation ${n\choose k}=x^l$, \textit{Acta Arith.\/} \textbf{80} (1997), 289--295.

\bibitem{gp}
K.~Gy\H{o}ry and \'{A}. Pint\'{e}r, Binomial Thue equations, ternary equations and power values of polynomials, \textit{J.\ Math.\ Sci.\ (N.Y.)} \textbf{180} (2012), 569--580.

\bibitem{konvalinka}
M.~Konvalinka, Divisibility of generalized Catalan numbers, \textit{J.\ Combin.\ Theory Ser.\ A} \textbf{114} (2007), 1089--1100.

\bibitem{kg}
T.~Koshy and Z.~Gao, Some divisibility properties of Catalan numbers, \textit{Math.\ Gaz.\/} \textbf{95} (2011), 96--102.

\bibitem{ly}
S.~Liu, and J.~C.-C.~Yeh, Catalan numbers modulo $2^k$, \textit{J.\ Integer Seq.\/} \textbf{13} (2010), Article 10.5.4.

\bibitem{mihailescu}
P.~Mih\u{a}ilescu, Primary cyclotomic units and a proof of Catalan's conjecture, \textit{J.\ Reine Angew.\ Math.\/} \textbf{572} (2004), 167--195.

\bibitem{ramanujan}
S.~Ramanujan, A proof of Bertrand's postulate, \textit{J.\ Indian Math.\ Soc.\/} \textbf{11} (1919), 181--182.

\bibitem{siegel}
C.~Siegel, \"{U}ber einige Anwendungen diophantischer approximationen, \textit{Abh.\ Preu\ss, Akad.\ Wissen.\ Phys.-Math.\ Klasse} (1929) = \textit{Ges.\ Abh.\ Bd.\ I}, Springer-Verlag, 1966, pp.\ 209--266.

\bibitem{oeis}
N.~J.~A.~Sloane,
\textit{The On-Line Encyclopedia of Integer Sequences},
\url{https://oeis.org}.

\bibitem{sylvester}
J.~J.~Sylvester, On arithmetical series, \textit{Messenger Math.\/} \textbf{21} (1892), 1--19, 87--120.  Reprinted in
\textit{Collected Mathematical Papers} \textbf{4} (1912), 687--731.

\bibitem{xx}
G.~Xin and J.-F.~Xu, A short approach to Catalan numbers modulo $2^r$, \textit{Electron.\ J.\ Combin.\/} \textbf{18} (2011), \#P177.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11D72; Secondary 11B65, 11A51.

\noindent \emph{Keywords:} Catalan triangle, squarefull number, prime
power, semiprime power, perfect power, Sylvester's theorem, Gy\H{o}ry
and Pint\'{e}r's theorem.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A275481},
\seqnum{A275586}, and
\seqnum{A317027}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  January 30 2019;
revised versions received  October 18 2019; October 31 2019.
Published in {\it Journal of Integer Sequences},
November 8 2019.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


.