\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{xcolor}

\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://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\be{\begin{equation}}
\newcommand\ee{\end{equation}}
\newcommand\bn{\begin{eqnarray}}
\newcommand\en{\end{eqnarray}}
\newcommand\bns{\begin{eqnarray*}}
\newcommand\ens{\end{eqnarray*}}

\renewcommand*{\thefootnote}{\fnsymbol{footnote}}

\begin{center}
\vskip 1cm{\LARGE{\bf On the Primality of the Generalized  \\
\vskip .1in
Fuss-Catalan Numbers}}
\vskip 1cm
Wun-Seng Chou\footnote{The author would like to thank Ministry of Science and Technology of Taiwan, ROC, for partial support under grant number 106-2115-M-001-003.}\\
Institute of Mathematics, Academia Sinica\\
Taipei 11529\\
Taiwan\\
\href{mailto:macws@math.sinica.edu.tw}{\tt macws@math.sinica.edu.tw}\\
\ \\
Tian-Xiao He\\
Department of Mathematics\\
Illinois Wesleyan University\\
Bloomington, IL 61702\\
USA\\
\href{mailto:the@iwu.edu}{\tt the@iwu.edu} \\
\ \\
Peter J.-S. Shiue\footnote{This work was completed while on sabbatical leave from the University of Nevada, Las Vegas, and the author would like to thank UNLV for its support.}
\\
Department of Mathematical Sciences\\
University of Nevada, Las Vegas\\
Las Vegas, NV 89154-4020\\
USA\\
\href{mailto:shiue@unlv.nevada.edu}{\tt shiue@unlv.nevada.edu} \\
\end{center}

\vskip .2 in

\renewcommand*{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}

\begin{abstract}
In this note, we determine all primes among the Fuss-Catalan numbers
the generalized Fuss-Catalan numbers,
the Lobb numbers, and the ballot numbers.   
\end{abstract}

\section{Introduction}

It has long been known (see, for example, Koshy and Salmassi \cite{KS})
that the only primes among the Catalan numbers are $C_2=2$ and
$C_3=5$.  In this note we determine all the primes among the
generalized Fuss-Catalan numbers, the Lobb numbers, and the ballot
numbers.  The definition of the generalized Fuss-Catalan numbers
follows.  (The definitions of the Lobb numbers and ballot numbers are
given after Corollary \ref{cor:1.3} and Corollary \ref{cor:1.4},
respectively.)

Let integers $m\geq 2$ and $n, k \geq 1$ be given.  
The \textit{Catalan numbers} $C_n$ (see \seqnum{A000108} in
the {\it Online Encyclopedia of Integer Sequences} are defined by 
\be \label{1}
C_n=\frac{1}{2n+1} {{2n+1}\choose{n}}=\frac{1}{n+1}{{2n}\choose{n}}.
\ee

The \textit{Fuss-Catalan numbers} 
(see \seqnum{A002293}, \seqnum{A002294}, \seqnum{A002295}, \seqnum{A002296})
$F_{m}(n)$ are the numbers of the form
\be \label{2}
F_{m}(n)=\frac{1}{mn+1}{{mn+1}\choose{n}}=\frac{1}{(m-1)n+1}{{mn}\choose{n}}.
\ee 

The \textit{generalized Fuss-Catalan numbers} $F_m(n,k)$ are the number of the form
\be\label{3}
F_m(n,k):=\frac{k}{mn+k}{{mn+k}\choose{n}}=\frac{k}{(m-1)n+k}{{mn+k-1}\choose{n}}.
\ee

The generalized Fuss-Catalan numbers are named after N. I. Fuss and E.
C. Catalan (see \cite{FL,GKP,LP,Mlo,PZ}), and are sometimes called the
$k$-fold Fuss-Catalan numbers or the Raney numbers.  Note that
$F_m(n,1)=F_{m}(n)$ and $F_2(n)=F_2(n,1)=C_n.$

The Fuss-Catalan numbers have several combinatorial applications; see,
for example, \cite{Arm,BMS,Ede,GKP,PS,SW, Sta}. The generating
function  $F_m(z)$ for the Fuss-Catalan numbers $\{ F_m(n,1)\}_{n\geq
0}$, that is,

\be \label{4}
F_m(z)=\sum_{n\ge 0}F_m(n,1)z^n,
\ee
is called the \textit{generalized binomial series} by Graham, Knuth, and Patashnik \cite [p.~200] {GKP}. Lambert's formula for the Taylor expansion of the powers of $F_m(z)$ (see \cite[(5.60)] {GKP}) is 
\be\label{5}
(F_m(z))^k=\sum_{n\geq 0}\frac{k}{mn+k}{{mn+k}\choose{n}}z^n=\sum_{n\geq 0} F_m(n,k)z^n
\ee
for all integers $k\geq 1$. An ingenious argument in \cite[p.~363]{GKP} uses \eqref{5} to show that 
\be\label{6}
F_m(z)=1+z(F_m(z))^m.
\ee

In this note, we are interested in the primality of the generalized
Fuss-Catalan numbers, $F_m(n,k)$, defined by \eqref{3}.


\section{Main results}

Here is our main result on the primality of the generalized
Fuss-Catalan numbers.

\begin{theorem}\label{thm:1.1}
Let the generalized Fuss-Catalan numbers $F_m(n,k)$ be defined by
\eqref{3} with $m\geq 2$ and $n, k \geq 1$. Then $F_{m}(n,k)$ is not
prime except in the following cases:
\begin{itemize}
\item[(a)] for $n\geq 3$, the only prime
of the form  $F_{m}(n,k)$ is $F_2(3,1)=5$;
\item[(b)] for $n=2$, $F_p(2,1)=p$,
where $p$ is prime, and $F_m(2,2)=2m+1$ when $m=(p-1)/2$ and $p$ is
prime; 
\item[(c)] for $n=1$, $F_m(1,k)=k$, where $k$ is prime.
\end{itemize}
\end{theorem}

\begin{proof}
We separate our proof into three cases as follows: (a) $n\geq 3$; (b) $n=2$; and (c) $n=1$. 

First, we show that for $n\geq 3$, $F_{m}(n,k)$ is not prime except for $F_2(3,1)=5$.  Indeed, 
\bn\label{0}
&&F_m(n,k)=\frac{k}{(m-1)n+k}{{mn+k-1}\choose{n}}\nonumber\\
&=&\frac{k}{(m-1)n+k}\frac{mn+k-1}{n}\frac{mn+k-2}{n-1}\cdots 
\frac{mn+k-(n-1)}{2}\frac{mn+k-n}{1}\nonumber\\
&=&k\frac{mn+k-1}{n}\frac{mn+k-2}{n-1}\cdots \frac{mn+k-(n-2)}{3}\frac{mn+k-(n-1)}{2}.
\en
Since $m\geq 2$, $n\geq 3$, and $k\geq 1$, we have 

\[
\frac{mn+k-1}{n}, \frac{mn+k-2}{n-1}, \ldots, \frac{mn+k-(n-3)}{4} >1
\]
and 

\[
\frac{mn+k-(n-2)}{3}\geq 2.
\]
Noting  $m\geq 2$, and combining the above estimates, we have 

\[
F_m(n,k)>k((m-1)n+k+1)\geq mn+k-1
\]
for $k\geq 2$. Thus, 

\be\label{lower bound of GFC}
F_m(n,k)>mn+k-1
\ee
for $m\geq 2$, $n\geq 3$ and $k\geq 2$. Note that every prime factor of $F_m(n,k)$ is less than or equal to $mn+k-1$ because each factor of $F_m(n,k)$ must be a factor of the numerator in the definition of $F_m(n,k)$ (see \eqref{0}). So, if $F_m(n,k)$ were a prime, we would have $F_m(n,k) \leq mn+k-1$, which contradicts to \eqref{lower bound of GFC}. Hence, $F_m(n,k)$ is a composite number.

We have finished the discussion for the sub-case of (a) where $n\geq 3$ and $k\geq 2$, and we now consider the sub-case of $n\geq 3$ and $k=1$, i.e., the case of  

\be\label{0-2}
F_m(n,1)=\frac{1}{(m-1)n+1}{{mn}\choose{n}}.
\ee
If $n=3$, then \eqref{0-2} gives 
\be\label{0-3}
F_m(3,1)=\frac{1}{3m-2}{{3m}\choose{3}}=\frac{m(3m-1)}{2}.
\ee
If $m=2\ell +1$, $\ell \geq 1$,
then the above equation \eqref{0-3} implies that 
$F_{2\ell+1}(3,1)=(2\ell+1)(3\ell+1)
$
is not a prime number.
If $m=2\ell$, $\ell\geq 1$, then \eqref{0-3} implies that 
$
F_{2\ell}(3,1)=\ell (6\ell -1)
$
is not prime unless $\ell=1$. Thus, $F_2(3,1)=5$ is the only prime number for $m\geq 2$ and $n=3$. The final phase of case (a)  that we have not yet considered is $n\geq 4$ and $k=1$. Similarly to \eqref{0}, we may write \eqref{0-2} as  
\bns
&&F_m(n,1)=\frac{1}{(m-1)n+1}{{mn}\choose{n}}\nonumber\\&=&\frac{1}{(m-1)n+1}\frac{mn}{n}\frac{mn-1}{n-1}\cdots \frac{mn-(n-3)}{3}\frac{mn-(n-2)}{2}\frac{mn-(n-1)}{1}\\
&=&\frac{mn}{n}\frac{mn-1}{n-1}\cdots \frac{mn-(n-4)}{4}\frac{mn-(n-3)}{3}\frac{mn-(n-2)}{2}\\
&>& \frac{mn-(n-4)}{4}\frac{mn-(n-3)}{3}\frac{mn-(n-2)}{2}\\
&\geq &2\frac{7}{3}\frac{mn-(n-2)}{2}\\
&>&2(mn-(n-2))>mn,
\ens
where we used $n\geq 4$ and $m\geq 2$ so that $mn-(n-4)/4\geq 2$ and $(mn-(n-3)/3\geq 7/3$, and the last inequality is due to $m\geq 2$. Thus, $F_m(n,1)$ is not prime when $n\geq 4$ 
by similar arguments as those stated right after \eqref{lower bound of GFC}. This finishes the proof of case (a). 

In case (b), under the assumption $n=2$, we have 
\[
F_m(2,k)=\frac{k}{2(m-1)+k}{{2m+k-1}\choose{2}}=\frac{k(2m+k-1)}{2} \  .
\]
Thus,  if $k=1$ and $m=p$, a prime number, then $F_m(2,k)=p$ is prime. If $k=2\ell$ ($\ell\geq 1$), then 
\[
F_m(2,2\ell)=\ell(2m+2\ell-1)
\]
is not prime unless $\ell=1$ and $2m+1$ is prime, or equivalently, $\ell =1$ and $m=(p-1)/2$, where $p$ is prime. 
If $k=2\ell +1$, $\ell>1$, then 
\[
F_m(2,k)=(2\ell+1)(m+1)
\]
is not prime. 

In case (c), we assume $n=1$; then 
\[
F_m(1,k)=k
\]
is prime exactly when $k$ is prime. This completes the proof of the theorem.
\end{proof}


\begin{corollary}\label{cor:1.2}
Let $F_m(n,1)$ be the Fuss-Catalan numbers defined by \eqref{2}. Then none of these are prime except for $F_p(2,1)=p$, where $p$ is prime, and $F_2(3,1)=5$.
\end{corollary}

For the Catalan numbers $C_n=F_2(n,1)$, Koshy and Salmassi \cite{KS} use a different method to prove the following special case of  Theorem \ref{thm:1.1}.

\begin{corollary}\label{cor:1.3}
The Catalan numbers $C_n$ are not prime except $C_2=2$ and $C_3=5$.
\end{corollary}

Lobb \cite{Lob} defines the Lobb numbers \seqnum{A039599}
\[
L_{n,m}:=\frac{2m+1}{n+m+1}{{2n}\choose{n+m}}
\]
for $n\geq m\geq 0$, which have the combinatorial interpretation as follows: $L_{n,m}$ is the number of sequences of length $2n$ with $n+m$ of the terms equal to $1$ and $n-m$ of the terms equal to $-1$, such that no partial sum is negative.  
Bobrowski et al.~\cite{BHS} extend Lobb numbers to the number of sequences with $(k-1)n+m$ terms equal to $1$ and $n-m$ terms equal to $1-k$. The extended Lobb numbers are denoted by $L_{m,n}^k$ and are defined by 
\be\label{1.8}
L_{n,m}^k:=\frac{km+1}{(k-1)n+m+1}{{kn}\choose{(k-1)n+m}}.
\ee

Generalized Lobb numbers include many number sequences as special cases. For example, when $k=2$, the numbers $L_{n,m}^2$ are the classical Lobb numbers. When $m=0$, the numbers
\[
L_{n,0}^k=\frac{1}{(k-1)n+1}{{kn}\choose{n}}=F_k(n)
\]
are the Fuss-Catalan numbers. When $k=2$ and $m=0$, the numbers 
\[
L_{n,0}^2=\frac{1}{n+1}{{2n}\choose{n}}=C_n
\]
are the classical Catalan numbers. When $k=1$, the numbers 
\[
L_{n,m}^1={{n}\choose{m}}
\]
are the binomial coefficients. Other special cases can be seen in \cite{He}. 


Equations \eqref{3} and \eqref{0-3} imply that
\be\label{1.6}
L_{n,m}^k=F_k(n-m,km+1).
\ee
Hence, we have the inverse relationship 
\be\label{1.7}
F_m(n,k)=L^m_{n+(k-1)/m, (k-1)/m},
\ee
which can be used to transfer the results of Theorem \ref{thm:1.1} for the generalized Fuss-Catalan numbers to corresponding results for the generalized Lobb numbers.  This gives us the following corollary to Theorem~\ref{thm:1.1}.

\begin{corollary}\label{cor:1.4}
For integers $m\geq 2$ and $n, k \geq 1$, the only extended Lobb numbers which are prime  are $L^m_{1+(k-1)/m, (k-1)/m}=k$, where $k$ is prime, $L^p_{2,0}=p$, where $p$ is prime, $L^2_{3,0}=5$, and $L^m_{2+1/m, 1/m}=2m+1$, where $m=(p-1)/2$ and $p$ is prime.
\end{corollary}

The Lobb numbers $L^2_{n,m}$ are also related to the ballot numbers \seqnum{A002026} (see, for example, \cite{GKP})
\be\label{1.81}
B(a,b)=\frac{a-b}{a+b}{{a+b}\choose{a}}=\frac{a-b}{a+b}{{a+b}\choose{b}}.
\ee
Namely, when $L^k_{n,m}$ and $B(a,b)$ are defined by \eqref{1.7} and \eqref{1.81}, respectively, we have
\be\label{1.9}
L^2_{n,m}=B(n+m+1,n-m),
\ee
or equivalently,
\be\label{1.10}
B(n,m)=L^2_{\frac{n+m-1}{2}, \frac{n-m-1}{2}}.
\ee
Hence, $L^2_{n,m}$ is a ballot number. From Corollary \ref{cor:1.4}, we immediately have 

\begin{corollary}\label{cor:1.5}
Let the ballot numbers $B(a,b)$ be defined by \eqref{1.8}. Then the only prime numbers of the form $B(a,b)$ are $B(k+1,1)=k$, where $k$ is prime, $B(3,2)=2$, and $B(4,2)=B(4,3)=5$.
\end{corollary}

\section{Acknowledgments} 
The authors wish to express their sincere gratitude and appreciation to Professor Tom Brown for helpful comments and remarks that led to an revised version of the original manuscript. 
The authors also wish to thank the Editor-in-Chief and the anonymous referee for useful comments and suggestions. 

\begin{thebibliography}{99}

\bibitem{Arm}
D. Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, {\it Mem. Amer. Math. Soc.}, \textbf{202} (2009).

\bibitem{BHS}
J. Bobrowski, T. X. He, and P. J.-S. Shiue, Divisibility of generalized
Catalan numbers and Raney numbers, {\it J. Comput. Anal. Appl.}, to appear.

\bibitem{BMS}
M. Bousquet-M\'elou and G. Schaeffer, Enumeration of planar
constellations, {\it Adv. in Appl. Math.} \textbf{24} (2000),
337--368.

\bibitem{Ede}
P. H. Edelman, Chain enumeration and non-crossing partitions, {\it
Discrete Math.} \textbf{31} (1980), 171--180.

\bibitem{FL}
P. J. Forrester and D.-Z. Liu, Raney distributions and random matrix
theory, {\it J. Stat. Phys.} \textbf{158} (2015), 1051--1082.

\bibitem{GKP} 
R. Graham, D. Knuth, and O. Patashnik,  {\it Concrete Mathematics,} 2nd
edition,  Addison-Wesley, 1994.

\bibitem{He}
T. X. He, Parametric Catalan numbers and Catalan triangles, {\it Linear
Algebra Appl.} \textbf{438} 3 (2013), 1467--1484.

\bibitem{HS}
T. X. He and L. Shapiro, FussCatalan matrices, their weighted sums, and
stabilizer subgroups of the Riordan group, {\it Linear Algebra Appl.}
\textbf{532} (2017), 25--42.

\bibitem{KS}
T. Koshy and M. Salmassi, Parity and primality of Catalan numbers, {\it
College Math. J.}, \textbf{37} (2006), 52--53.

\bibitem{LP}
J.-G. Liu and R. Pego, On generating functions of Hausdorff moment
sequences, \textit{Trans. Amer. Math. Soc.} \textbf{368} 
(2016), 8499--8518.

\bibitem{Lob}
A. M. Lobb, Deriving the $n$th Catalan number, \textit{Math. Gaz.}
\textbf{83} (1999), 109--110.

\bibitem{Mlo} 
W.  Mlotkowski, Fuss-Catalan numbers in noncommutative probability,
{\it Doc. Math.} {\bf 15} (2010), 939--955.

\bibitem{PZ}
K. A. Penson and K. \.Zyczkowski, Product of Ginibre matrices:
Fuss-Catalan and Raney distributions, {\it Phys. Rev. E}, \textbf{83}
(2011) 061118.

\bibitem{PS}
J. H. Przytycki and A. S. Sikora, Polygon Dissections and Euler, Fuss,
Kirkman, and Cayley Numbers, {\it J.  Combin. Theory Series A},
\textbf{92} (2000), 68--76.

\bibitem{SW}
A. Schuetz and G. Whieldon, Polygonal dissections and reversions of
series, arxiv preprint, 2014.  Available at
\url{https://arxiv.org/abs/1401.7194}.

\bibitem{Sta}
R. P. Stanley, {\it Catalan Numbers}, Cambridge University Press, 
2015.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39, Secondary 11B37,  05A15.


\noindent \emph{Keywords: } 
prime number, Catalan number, Fuss-Catalan number, generalized
Fuss-Catalan number, Lobb number, ballot number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A002026},
\seqnum{A002293},
\seqnum{A002294},
\seqnum{A002295},
\seqnum{A002296}, and
\seqnum{A039599}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 13 2017;
revised version received February 19 2018.
Published in {\it Journal of Integer Sequences},  February 23 2018.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                               }