\documentclass[12pt,reqno]{article}

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

\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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
On Divisibility  of Narayana Numbers by \\
\vskip .1in
Primes \\
}
\vskip 1cm
\large
Mikl\'os B\'ona \\
Department of Mathematics \\
University of Florida \\
Gainesville, FL 32611 \\
USA \\
\href{mailto:bona@math.ufl.edu}{\tt bona@math.ufl.edu} \\
\ \\
Bruce E. Sagan\\
Department of Mathematics \\
Michigan State University\\
East Lansing, MI 48824-1027\\
USA\\
\href{mailto:sagan@math.msu.edu}{\tt sagan@math.msu.edu} \\
\end{center}

\vskip .2 in
\begin{abstract}
Using Kummer's theorem, we give a necessary and sufficient condition
for a Narayana number to be divisible by a given prime.  We use this
to derive certain properties of the Narayana triangle.
\end{abstract}

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


%J Integer Seq 4/7/05 shallit@graceland.uwaterloo.ca
%
% THIS DOCUMENT IS WRITTEN IN LATEX 2e
%
% TO FIND THE TITLE:  search for the command \title using your word 
% processor
%
%\documentclass[12pt]{article}
% \usepackage{amssymb,latexsym}

\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\ble}{\begin{lem}}
\newcommand{\ele}{\end{lem}}
\newcommand{\bth}{\begin{thm}}
\renewcommand{\eth}{\end{thm}}
\newcommand{\bpr}{\begin{prop}}
\newcommand{\epr}{\end{prop}}
\newcommand{\bco}{\begin{cor}}
\newcommand{\eco}{\end{cor}}
\newcommand{\bcon}{\begin{conj}}
\newcommand{\econ}{\end{conj}}
\newcommand{\bde}{\begin{defn}}
\newcommand{\ede}{\end{defn}}
\newcommand{\bex}{\begin{exa}}
\newcommand{\eex}{\end{exa}}
\newcommand{\barr}{\begin{array}}
\newcommand{\earr}{\end{array}}
\newcommand{\btab}{\begin{tabular}}
\newcommand{\etab}{\end{tabular}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\bce}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\bpi}{\begin{picture}}
\newcommand{\epi}{\end{picture}}
\newcommand{\bfi}{\begin{figure} \begin{center}}
\newcommand{\efi}{\end{center} \end{figure}}
\newcommand{\capt}{\caption}
\newcommand{\bsl}{\begin{slide}{}}
\newcommand{\esl}{\end{slide}}

%\newcommand{\ch}{\choose}
\newcommand{\bib}{thebibliography}
\newcommand{\pf}{{\bf Proof}\hspace{7pt}}
\newcommand{\qed}{\rule{1ex}{1ex}}
\newcommand{\Qed}{\rule{1ex}{1ex} \medskip}
\newcommand{\qqed}{\qquad\rule{1ex}{1ex}}
\newcommand{\Qqed}{\qquad\rule{1ex}{1ex}\medskip}
\newcommand{\mc}[3]{\multicolumn{#1}{#2}{#3}}
\newcommand{\Mc}[1]{\multicolumn{#1}{c}{}}
%\newcommand{\mc}[2]{\multicolumn{#1}{#2}}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\hor}{\mbox{--}}
\newcommand{\hs}[1]{\hspace{#1}}
\newcommand{\hso}[1]{\hspace{-1pt}}
\newcommand{\vs}[1]{\vspace{#1}}
\newcommand{\qmq}[1]{\quad\mbox{#1}\quad}
\newcommand{\ssk}{\smallskip}
\newcommand{\msk}{\mediumskip}
\newcommand{\bsk}{\bigskip}
\newcommand{\rp}[2]{\rule{#1pt}{#2pt}}
\newcommand{\st}[1]{\rule{#1pt}{0pt}}
%\newcommand{\st}[1]{\rule{#1}{0pt}}
\newcommand{\mbl}[1]{\makebox(0,0)[l]{#1}}
\newcommand{\mbr}[1]{\makebox(0,0)[r]{#1}}
\newcommand{\mbt}[1]{\makebox(0,0)[t]{#1}}
\newcommand{\mbb}[1]{\makebox(0,0)[b]{#1}}
\newcommand{\mbc}[1]{\makebox(0,0){#1}}


\newcommand{\emp}{\emptyset}
\newcommand{\indu}{\uparrow}
\newcommand{\rest}{\downarrow}
\newcommand{\sm}{\hspace{-2pt}\setminus\hspace{-2pt}}
\newcommand{\sbs}{\subset}
\newcommand{\sbe}{\subseteq}
\newcommand{\sps}{\supset}
\newcommand{\spe}{\supseteq}
\newcommand{\setm}{\setminus}
\newcommand{\asy}{\thicksim}
\newcommand{\dle}{<\hspace{-6pt}\cdot}
\newcommand{\dge}{\cdot\hspace{-6pt}>}
\newcommand{\iso}{\cong}
%\newcommand{\con}{\equiv}
\newcommand{\Cong}{\equiv}
\newcommand{\conm}[1]{\stackrel{#1}{\equiv}}

\newcommand{\widevec}{\overrightarrow}
%makes a wide arrow over stuff if have \overrightarrow{stuff} 
\newcommand{\Ch}{\hat{C}}
\newcommand{\eh}{\hat{e}}
\newcommand{\Gh}{\hat{G}}
\newcommand{\ih}{\hat{\imath}}
\newcommand{\jh}{\hat{\jmath}}
\newcommand{\gh}{\hat{g}}
\newcommand{\mh}{\hat{0}}
\newcommand{\Mh}{\hat{1}}
\newcommand{\Dh}{\hat{D}}
\newcommand{\zh}{\hat{0}}
\newcommand{\oh}{\hat{1}}
\newcommand{\Ph}{\hat{P}}
\newcommand{\ph}{\hat{p}}
\newcommand{\Pih}{\hat{\Pi}}
\newcommand{\Qh}{\hat{Q}}
\newcommand{\Sh}{\hat{S}}
\newcommand{\lh}{\hat{l}}
\newcommand{\xh}{\hat{x}}
\newcommand{\ptn}{\vdash}
\newcommand{\lt}{\lhd}
\newcommand{\gt}{\rhd}
\newcommand{\lte}{\unlhd}
\newcommand{\gte}{\unrhd}
\newcommand{\jn}{\vee}
\newcommand{\Jn}{\bigvee}
\newcommand{\mt}{\wedge}
\newcommand{\Mt}{\bigwedge}
\newcommand{\bdy}{\partial}
\newcommand{\sd}{\bigtriangleup}
\newcommand{\case}[4]{\left\{\barr{ll}#1&\mbox{#2}\\#3&\mbox{#4}\earr\right.}
\newcommand{\fl}[1]{\lfloor #1 \rfloor}
\newcommand{\ce}[1]{\lceil #1 \rceil}
\newcommand{\flf}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}
\newcommand{\cef}[2]{\left\lceil\frac{#1}{#2}\right\rceil}
\newcommand{\gau}[2]{\left[ \barr{c} #1 \\ #2 \earr \right]}
\newcommand{\setc}[2]{\{left{#1}\ :\ #2\}}
\newcommand{\setl}[2]{\{left{#1}\ |\ #2\}}
\newcommand{\qst}{$q$-Stirling numbers}
\newcommand{\qbi}{$q$-binomial coefficients}
\newcommand{\del}{\nabla}
\newcommand{\pde}[2]{\frac{\partial#1}{\partial#2}}
\newcommand{\spd}[2]{\frac{\partial^2\hspace{-2pt}#1}{\partial#2^2}}
\newcommand{\ode}[2]{\ds\frac{d#1}{d#2}}
\def\<{\langle}
\def\>{\rangle}
\newcommand{\fall}[2]{\langle{#1}\rangle_{#2}}
\newcommand{\nor}[1]{\parallel{#1}\parallel}
\newcommand{\ipr}[2]{\langle{#1},{#2}\rangle}
\newcommand{\spn}[1]{\langle{#1}\rangle}
%\newcommand{\lb}{\left\{}
%\newcommand{\rb}{\right\}}
\newcommand{\ree}[1]{(\ref{#1})}
\newcommand{\rpl}{$\longleftarrow$}

\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\lta}{\leftarrow}
\newcommand{\rla}{\leftrightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\lla}{\longleftarrow}
\newcommand{\Lra}{\Longrightarrow}
\newcommand{\llra}{\longleftrightarrow}
\newcommand{\Llra}{\Longleftrightarrow}
\newcommand{\ve}[1]{\stackrel{\ra}{#1}}


\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\de}{\delta}
\newcommand{\ep}{\epsilon}
\newcommand{\io}{\iota}
\newcommand{\ka}{\kappa}
\newcommand{\la}{\lambda}
\newcommand{\mut}{\tilde{\mu}}
\newcommand{\om}{\omega}
\newcommand{\Phit}{\tilde{\Phi}}
\newcommand{\Psit}{\tilde{\Psi}}
\newcommand{\rhot}{\tilde{\rho}}
\newcommand{\si}{\sigma}
\renewcommand{\th}{\theta}
%       NOTE THAT \th HAS BEEN RENEWCOMMANDed
\newcommand{\ze}{\zeta}
\newcommand{\Al}{\Alpha}
\newcommand{\Ga}{\Gamma}
\newcommand{\De}{\Delta}
\newcommand{\Ep}{\epsilon}
\newcommand{\La}{\Lambda}
\newcommand{\Om}{\Omega}
\newcommand{\Si}{\Sigma}
\newcommand{\Th}{\Theta}
\newcommand{\Ze}{\Zeta}


\newcommand{\0}{{\bf 0}}
\newcommand{\1}{{\bf 1}}
\newcommand{\2}{{\bf 2}}
\newcommand{\3}{{\bf 3}}
\newcommand{\4}{{\bf 4}}
\newcommand{\5}{{\bf 5}}
\newcommand{\6}{{\bf 6}}
\newcommand{\7}{{\bf 7}}
\newcommand{\8}{{\bf 8}}
\newcommand{\9}{{\bf 9}}
\newcommand{\ba}{{\bf a}}
\newcommand{\bb}{{\bf b}}
\newcommand{\bc}{{\bf c}}
\newcommand{\bd}{{\bf d}}
\newcommand{\bfe}{{\bf e}}
\newcommand{\bff}{{\bf f}}
\newcommand{\bg}{{\bf g}}
\newcommand{\bh}{{\bf h}}
\newcommand{\bi}{{\bf i}}
\newcommand{\bj}{{\bf j}}
\newcommand{\bk}{{\bf k}}
\newcommand{\bm}{{\bf m}}
\newcommand{\bn}{{\bf n}}
\newcommand{\bp}{{\bf p}}
\newcommand{\bq}{{\bf q}}
\newcommand{\br}{{\bf r}}
\newcommand{\bs}{{\bf s}}
\newcommand{\bt}{{\bf t}}
\newcommand{\bu}{{\bf u}}
\newcommand{\bv}{{\bf v}}
\newcommand{\bw}{{\bf w}}
\newcommand{\bx}{{\bf x}}
\newcommand{\by}{{\bf y}}
\newcommand{\bz}{{\bf z}}
\newcommand{\bA}{{\bf A}}
\newcommand{\bB}{{\bf B}}
\newcommand{\bC}{{\bf C}}
\newcommand{\bE}{{\bf E}}
\newcommand{\bF}{{\bf F}}
\newcommand{\bG}{{\bf G}}
\newcommand{\bH}{{\bf H}}
\newcommand{\bN}{{\bf N}}
\newcommand{\bP}{{\bf P}}
\newcommand{\bQ}{{\bf Q}}
\newcommand{\bR}{{\bf R}}
\newcommand{\bS}{{\bf S}}
\newcommand{\bT}{{\bf T}}
\newcommand{\bX}{{\bf X}}
\newcommand{\bXh}{\hat{{\bf X}}}
\newcommand{\bZ}{{\bf Z}}
\newcommand{\bep}{{\bf \ep}}
\newcommand{\bcdot}{{\bf \cdot}}
\newcommand{\bbC}{{\mathbb C}}
\newcommand{\bbF}{{\mathbb F}}
\newcommand{\bbN}{{\mathbb N}}
\newcommand{\bbP}{{\mathbb P}}
\newcommand{\bbQ}{{\mathbb Q}}
\newcommand{\bbR}{{\mathbb R}}
\newcommand{\bbS}{{\mathbb S}}
\newcommand{\bbZ}{{\mathbb Z}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cAB}{{\cal AB}}
\newcommand{\cAD}{{\cal AD}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cBC}{{\cal BC}}
\newcommand{\cC}{{\cal C}}
\newcommand{\cD}{{\cal D}}
\newcommand{\cDB}{{\cal DB}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cG}{{\cal G}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cI}{{\cal I}}
\newcommand{\cIF}{{\cal IF}}
\newcommand{\cJ}{{\cal J}}
\newcommand{\cK}{{\cal K}}
\newcommand{\cL}{{\cal L}}
\newcommand{\cm}{{\cal m}}
\newcommand{\cM}{{\cal M}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cNBC}{{\cal NBC}}
\newcommand{\cO}{{\cal O}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cPD}{{\cal PD}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cRF}{{\cal RF}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cV}{{\cal V}}
\newcommand{\cW}{{\cal W}}
\newcommand{\cX}{{\cal X}}
\newcommand{\cY}{{\cal Y}}
\newcommand{\cZ}{{\cal Z}}

\newcommand{\df}{\dot{f}}
\newcommand{\dF}{\dot{F}}
\newcommand{\fgl}{{\mathfrak gl}}
\newcommand{\fS}{{\mathfrak S}}
\newcommand{\at}{\tilde{a}}
\newcommand{\ct}{\tilde{c}}
\newcommand{\dt}{\tilde{d}}
\newcommand{\pt}{\tilde{p}}
\newcommand{\Bt}{\tilde{B}}
\newcommand{\Gt}{\tilde{G}}
\newcommand{\Ht}{\tilde{H}}
\newcommand{\Kt}{\tilde{K}}
\newcommand{\Nt}{\tilde{N}}
\newcommand{\St}{\tilde{S}}
\newcommand{\Xt}{\tilde{X}}
\newcommand{\alt}{\tilde{\alpha}}
\newcommand{\bet}{\tilde{\beta}}
\newcommand{\rht}{\tilde{\rho}}
\newcommand{\Pit}{\tilde{\Pi}}
\newcommand{\tal}{\tilde{\alpha}}
\newcommand{\tbe}{\tilde{\beta}}
\newcommand{\tPi}{\tilde{\Pi}}
\newcommand{\ab}{\ol{a}}
\newcommand{\Ab}{\ol{A}}
\newcommand{\Bb}{\ol{B}}
\newcommand{\cb}{\ol{c}}
\newcommand{\Cb}{{\ol{C}}}
\newcommand{\db}{\ol{d}}
\newcommand{\Db}{\ol{D}}
\newcommand{\eb}{\ol{e}}
\newcommand{\Eb}{\ol{E}}
\newcommand{\fb}{\ol{f}}
\newcommand{\Gb}{\ol{G}}
\newcommand{\Hb}{\ol{H}}
\newcommand{\ib}{\ol{\imath}}
\newcommand{\Ib}{\ol{I}}
\newcommand{\jb}{\ol{\jmath}}
\newcommand{\Jb}{\ol{J}}
\newcommand{\kb}{\ol{k}}
\newcommand{\Kb}{\ol{K}}
\newcommand{\nb}{\ol{n}}
\newcommand{\pb}{\ol{p}}
\newcommand{\Pb}{\ol{P}}
\newcommand{\Phib}{\ol{\Phi}}
\newcommand{\Qb}{\ol{Q}}
\newcommand{\rb}{\ol{r}}
\newcommand{\Rb}{\ol{R}}
\newcommand{\Sb}{\ol{S}}
\newcommand{\tb}{\ol{t}}
\newcommand{\Tb}{\ol{T}}
\newcommand{\Ub}{\ol{U}}
\newcommand{\Wb}{\ol{W}}
\newcommand{\xb}{\ol{x}}
\newcommand{\Xb}{\ol{X}}
\newcommand{\yb}{\ol{y}}
\newcommand{\Yb}{\ol{Y}}
\newcommand{\zb}{\ol{z}}
\newcommand{\Zb}{\ol{Z}}
\newcommand{\pib}{\ol{\pi}}
\newcommand{\sib}{\ol{\si}}
\newcommand{\degb}{\ol{\deg}}
\newcommand{\vj}{\vec{\jmath}}
\newcommand{\vv}{\vec{v}}
\newcommand{\ttab}{\{t\}}
\newcommand{\stab}{\{s\}}



\newcommand{\Aut}{\mathop{\rm Aut}\nolimits}
\newcommand{\abl}{\mathop{\rm al}\nolimits}
\newcommand{\capa}{\mathop{\rm cap}\nolimits}
\newcommand{\codim}{\mathop{\rm codim}\nolimits}
\newcommand{\ch}{\mathop{\rm ch}\nolimits}
%Commented out \ch for choose
\newcommand{\col}{\mathop{\rm col}\nolimits}
\newcommand{\ctt}{\mathop{\rm ct}\nolimits}
\newcommand{\Der}{\mathop{\rm Der}\nolimits}
\newcommand{\des}{\mathop{\rm des}\nolimits}
\newcommand{\Des}{\mathop{\rm Des}\nolimits}
\newcommand{\diag}{\mathop{\rm diag}\nolimits}
\newcommand{\Diag}{\mathop{\rm Diag}\nolimits}
\newcommand{\diam}{\mathop{\rm diam}\nolimits}
\newcommand{\End}{\mathop{\rm End}\nolimits}
\newcommand{\ev}{\mathop{\rm ev}\nolimits}
\newcommand{\eval}{\mathop{\rm eval}\nolimits}
\newcommand{\Eval}{\mathop{\rm Eval}\nolimits}
\newcommand{\FPF}{\mathop{\rm FPF}\nolimits}
\newcommand{\gen}{\mathop{\rm gen}\nolimits}
\newcommand{\Harm}{\mathop{\rm Harm}\nolimits}
\newcommand{\Hom}{\mathop{\rm Hom}\nolimits}
\newcommand{\id}{\mathop{\rm id}\nolimits}
\newcommand{\im}{\mathop{\rm im}\nolimits}
\newcommand{\imaj}{\mathop{\rm imaj}\nolimits}
\newcommand{\inc}{\mathop{\rm inc}\nolimits}
\newcommand{\Ind}{\mathop{\rm Ind}\nolimits}
\newcommand{\inter}{\mathop{\rm int}\nolimits}
\newcommand{\Inter}{\mathop{\rm Int}\nolimits}
\newcommand{\inv}{\mathop{\rm inv}\nolimits}
\newcommand{\Inv}{\mathop{\rm Inv}\nolimits}
\newcommand{\lcm}{\mathop{\rm lcm}\nolimits}
\newcommand{\LHS}{\mathop{\rm LHS}\nolimits}
\newcommand{\Mat}{\mathop{\rm Mat}\nolimits}
\newcommand{\maj}{\mathop{\rm maj}\nolimits}
\newcommand{\Mod}{\mathop{\rm mod}\nolimits}
\newcommand{\NBB}{\mathop{\rm NBB}\nolimits}
\newcommand{\nin}{\mathop{\rm nin}\nolimits}
\newcommand{\Nin}{\mathop{\rm Nin}\nolimits}
\newcommand{\nul}{\mathop{\rm nul}\nolimits}
\newcommand{\od}{\mathop{\rm od}\nolimits}
\newcommand{\per}{\mathop{\rm per}\nolimits}
\newcommand{\Pete}{\mathop{\rm Pete}\nolimits}
\newcommand{\pfa}{\mathop{\rm pf}\nolimits}
\newcommand{\Pm}{\mathop{\rm pm}\nolimits}
\newcommand{\PM}{\mathop{\rm PM}\nolimits}
\newcommand{\Pol}{\mathop{\rm Pol}\nolimits}
\newcommand{\rad}{\mathop{\rm rad}\nolimits}
\newcommand{\RHS}{\mathop{\rm RHS}\nolimits}
\newcommand{\rk}{\mathop{\rm rk}\nolimits}
\newcommand{\rank}{\mathop{\rm rank}\nolimits}
\newcommand{\reg}{\mathop{\rm reg}\nolimits}
\newcommand{\row}{\mathop{\rm row}\nolimits}
\newcommand{\sdiam}{\mathop{\rm sdiam}\nolimits}
\newcommand{\sgn}{\mathop{\rm sgn}\nolimits}
\newcommand{\sign}{\mathop{\rm sign}\nolimits}
\newcommand{\sh}{\mathop{\rm sh}\nolimits}
\newcommand{\slack}{\mathop{\rm slack}\nolimits}
\newcommand{\spa}{\mathop{\rm span}\nolimits}
\newcommand{\sta}{\mathop{\rm st}\nolimits}
\newcommand{\summ}{\mathop{\rm sum}\nolimits}
\newcommand{\sus}{\mathop{\rm susp}\nolimits}
\newcommand{\Sym}{\mathop{\rm Sym}\nolimits}
\newcommand{\SYT}{\mathop{\rm SYT}\nolimits}
\newcommand{\tang}{\mathop{\rm tang}\nolimits}
\newcommand{\tr}{\mathop{\rm tr}\nolimits}
\newcommand{\tri}{\mathop{\rm tri}\nolimits}
\newcommand{\wed}{\mathop{\rm wedge}\nolimits}
\newcommand{\wt}{\mathop{\rm wt}\nolimits}








\newcommand{\bul}{\bullet}
\newcommand{\dil}{\displaystyle}
\newcommand{\dsum}{\dil\sum}
\newcommand{\dint}{\dil\int}
% \newcommand{\dfrac}{\dil\frac}
\newcommand{\scl}{\scriptstyle}
\newcommand{\ssl}{\scriptscriptstyle}
\newcommand{\foz}{\footnotesize}
\newcommand{\scz}{\scriptsize}
\newcommand{\cho}{\choose}

\newcommand{\Schu}{Sch\"utzenberger}
\newcommand{\aim}{Adv.\ in Math.\/}
\newcommand{\bams}{Bull.\ Amer.\ Math.\ Soc.\/}
\newcommand{\cjm}{Canad.\ J. Math.\/}
\newcommand{\dm}{Discrete Math.\/}
\newcommand{\dmj}{Duke Math.\ J.\/}
\newcommand{\ejc}{European J. Combin.\/}
\newcommand{\jaa}{J. Algebra\/}
\newcommand{\jac}{J. Algebraic Combin.\/}
\newcommand{\jas}{J. Algorithms\/}
\newcommand{\jams}{J. Amer.\ Math.\ Soc.\/}
\newcommand{\jct}{J. Combin.\ Theory\/}
\newcommand{\jcta}{J. Combin.\ Theory Ser. A\/}
\newcommand{\jctb}{J. Combin.\ Theory Ser. B\/}
\newcommand{\jgt}{J. Graph Theory\/}
\newcommand{\jram}{J. Reine Angew.\ Math.\/}
\newcommand{\pjm}{Pacific J. Math.\/}
\newcommand{\pams}{Proc.\ Amer.\ Math.\ Soc.\/}
\newcommand{\plms}{Proc.\ London Math.\ Soc.\/}
\newcommand{\tams}{Trans.\ Amer.\ Math.\ Soc.\/}
\newcommand{\pja}{Proc.\ Japan Acad.\ Ser.\ A  Math\/}
\newcommand{\sv}{Springer-Verlag Lecture Notes in Math.\/}
\newcommand{\crgs}{Combinatoire et Repr\'{e}sentation du 
    Groupe Sym\'{e}trique, Strasbourg 1976, D. Foata ed.}
\newcommand{\caup}{Cambridge University Press}
\newcommand{\oup}{Oxford University Press} 
\newcommand{\pr}{preprint}
\newcommand{\ip}{in preparation}
\newcommand{\ds}{\displaystyle}


\setlength{\topmargin}{.1in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{7in}
\setlength{\evensidemargin}{-.2in}
\setlength{\oddsidemargin}{-.2in}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{exa}[thm]{Example}
\newtheorem{question}[thm]{Question}


\section{The main theorem}

Let $\bbN$ denote the nonnegative integers and let $k,n\in\bbN$.  The
{\it Narayana numbers\/}~\cite[A001263]{slo:ole} can be defined as
$$
N(n,k)=\frac{1}{n}{n\choose k}{n\choose k+1}
$$
where $0\le k<n$.  The Narayana numbers (in fact, a $q$-analogue of
them) were first studied by  MacMahon~\cite[Article 495]{mac:ca} and
were later rediscovered by Narayana~\cite{nar:tfp}.  They are closely
related to the {\it Catalan numbers\/}~\cite[A000108]{slo:ole}
$$
C_n=\frac{1}{n+1}{2n\choose n}
$$
and in fact $\sum_k N(n,k)= C_n$.   The
Narayana numbers can be arranged in a triangular array with $N(n,k)$
in row $n$ and column $k$ so that the row sums are the Catalan numbers.
Like the numbers $C_n$, the numbers
$N(n,k)$ have many combinatorial interpretations; see, for
example, the article of Sulanke~\cite{sul:nd}.

The main result of this note is a characterization of when $N(n,k)$ is
divisible by a given prime $p$.  To state it, we need some notation.  Let
$\De_p(n)=(n_i)$ denote the sequence of digits of $n$ in base $p$
so that $n=\sum_i n_i p^i$.  Similarly we define $\De_p(k)=(k_i)$.
If we are considering $k\le n$ then it will be convenient to 
extend the range of definition of $(k_i)$ so that both sequences have
the same length by setting $k_i=0$ if $p^i>k$.  The {\it order\/} of
$n$ modulo $p$ is the largest power of $p$ dividing $n$ and will be
denoted $\om_p(n)$.  As usual,
$k|n$ means that $k$ divides $n$.

Kummer's theorem~\cite{kum:ear} gives a useful way of finding the
order of binomial coefficients.  For example, Knuth and
Wilf~\cite{kw:ppd} used it 
to find the highest power of a prime which divides a generalized
binomial coefficient.
\bth[Kummer]
Let $p$ be prime and let $\De_p(n)=(n_i)$, $\De_p(k)=(k_i)$. 
Then $\om_p {n\choose k}$ is the number of carries
in performing the addition $\De_p(k)+\De_p(n-k)$.  Equivalently, it is the
number of indices $i$ such that either $k_i>n_i$ or there exists an
index $j<i$ with $k_j>n_j$ and
$k_{j+1}=n_{j+1},\ldots,k_i=n_i$.\Qqed
\eth

Now everything is in place to state and prove our principal theorem.
\bth
\label{main}
Let $p$ be prime. 
Also let $\De_p(n)=(n_i)$, $\De_p(k)=(k_i)$ and $\om=\om_p(n)$. 
Then $p\nmid N(n,k)$ if and only if one of the two following conditions hold:
\ben 
\item When $p \nmid n$ we have
  \ben 
  \item $k_i\le n_i$ for all $i$, and
  \item $k_j < n_j$ where $j$ is the first index with $k_j\neq p-1$
  (if such an index exists).
  \een
\item When $p\mid n$ we have
  \ben 
  \item $k_i\le n_i$ for all $i>\om$, and
  \item $k_\om < n_\om$, and
  \item $k_0=k_1=\ldots=k_{\om-1}=
   \case{0}{if $p\mid k$;}{p-1}{if $p\nmid k$.}$
  \een
\een
\eth
\pf
First suppose that $p$ is not a divisor of $n$.  Then $p$ does not divide
$N(n,k)$ if and only if $p$ divides neither ${n\choose k}$ nor
${n\choose k+1}$.  By Kummer's theorem this is equivalent to 
$k_i\le n_i$ and $(k+1)_i\le n_i$ for all $i$.  However, if $j$ is the
first index with $k_j\neq p-1$, then we have
$$
(k+1)_i=
{\left\{\barr{ll}0&\mbox{if $i<j$;}\\
(k)_i+1&\mbox{if $i=j$;}\\
(k)_i&\mbox{if $i>j$.}
\earr\right.}
$$
So these conditions can be distilled down to insisting that
$k_j<n_j$ in addition to $k_i\le n_i$ for all
other $i$.  

Now consider what happens when $p$ divides $n$.  Suppose first that
$p$ also divides $k$.  So $(n)_i=0$ for $i<\om$, which is a
nonempty set of indices, and $(k+1)_0=1$.  It follows
there are at least $\om$ carries in computing
$\De_p(k+1)+\De_p(n-k-1)$.  By Kummer's theorem again, 
$\om_p{n\choose k+1}\ge\om$.  So $p$ does not divide $N(n,k)$ if
and only if it does not divide ${n\choose k}$ and $\om_p{n\choose k+1}=\om$.  
Applying Kummer's theorem  once more shows that this will happen exactly when
$k_i\le n_i$ for all $i$ with $k_\om<n_\om$.  So in particular $k_i=0$
for $i<\om$ since then $n_i=0$.  This completes the case when $p$
divides both $n$ and $k$.

Finally, suppose $p\mid n$ but $p\nmid k$.  Arguing as in the
previous paragraph, we see that $p$ is not a divisor of $N(n,k)$ if
and only if
$\om_p{n\choose k}=\om$ and $p$ does not divide ${n\choose k+1}$. 
But if $p$ is not a divisor of ${n\choose k+1}$ then, using Kummer's theorem,
 we must have $(k+1)_i=0$ for $i<\om$.  So $(k)_i=p-1$ for
$i<\om$.  Conditions 2(b) and (c) also follow as before.  This completes the
demonstration of the theorem.  \Qqed

\section{Applications}

It is well known that $C_n$ is odd if and only if $n=2^m-1$ for some
$m$.  For a combinatorial proof of this  which in fact establishes
$\om_2(C_n)$, see the article of Deutsch and Sagan~\cite{ds:ccm}.
Analogously, all the entries of the $n$th row of the Narayana triangle
are odd.  This is a special case of the following result.
\bco
\label{notdiv}
Let $p$ be prime and let $n=p^m-1$ for some $m\in\bbN$.  Then for 
all $k$, $0\le k\leq n-1$, we have $p\nmid N(n,k)$.

\eco
\pf
By Theorem~\ref{main} we just need to verify that 1(a) and (b) hold
for all $k$.  However, they must be true because
$n_i=p-1$ for all $i$.
\Qqed

We clearly can not have a row of the Narayana triangle where every
element is divisible by $p$ since $N(n,0)=N(n,n-1)=1$ for all $n$.
But we can ensure that every entry except the first and last is a
multiple of $p$.
\bco
\label{div}
Let $p$ be prime and let $n=p^m$ for some $m\in\bbN$.  Then $p\mid N(n,k)$
for $1\le k\le n-2$.
\eco
\pf
Suppose that $n=p^m$ and that $p$ does not divide $N(n,k)$.  If $p$
divides $k$, then 
condition 2(c) forces $k=0$.  If $p$ does not divide $k$, then the
same condition forces $k=n-1$.  So these are the only two numbers not
divisible by $p$ in the $n$th row of Narayana's triangle.
\Qqed




\section{Comments and Questions}

I.\  Clearly one could use the same techniques presented here to
determine $\om_p(N(n,k))$.  However, the cases become complicated enough
that it is unclear whether this would be an interesting thing to do.

\medskip

\noindent II.\  The characterization in Theorem~\ref{main} is involved enough
that it may be hopeless to ask for a combinatorial proof.  However,
there should be a combinatorial way to derive the simpler statements
in Corollaries~\ref{notdiv} and~\ref{div}, although we have not been
able to do so.  

As has already been mentioned, the order $\om_2(C_n)$
can be established by combinatorial means, specifically through the
use of group actions.  Unfortunately, the action used by
Deutsch and Sagan~\cite{ds:ccm} is not 
sufficiently refined to preserve the objects counted by $N(n,k)$.
For more information about how such methods can
be used to prove congruences, the reader can consult Sagan's
article~\cite{sag:cva} which also contains a survey of the literature.

Deutsch~\cite{deu:idp},
E\u{g}ecio\u{g}lu~\cite{ege:pcn}, and Simion and Ullman~\cite{su:sln}
have all found combinatorial ways to explain the fact that $C_n$ is
odd if and only if $n=2^m-1$ for some $m$.  Perhaps one or more of the
viewpoints in these papers could be adapted to the Narayana numbers.

\medskip



{\it Acknowledgment}.  We would like to thank Robert Sulanke for
valuable references and discussions, and to Neil White for bringing the
problem to our attention.


\begin{\bib}{99}

\bibitem{deu:idp}  E. Deutsch, An involution on Dyck paths and its
consequences, {\it Discrete Math.\/} {\bf 204} (1999), 163--166.


\bibitem{ds:ccm} 
\begin{flushleft}
E. Deutsch and B. E. Sagan, Congruences for Catalan
and Motzkin numbers and related sequences, preprint, available at
\href{http://www.math.msu.edu/~sagan}{\texttt
http://www.math.msu.edu/$\sim$sagan/}.
\end{flushleft}

\bibitem{ege:pcn} \"O. E\u{g}ecio\u{g}lu, The parity of the Catalan
numbers via lattice paths, {\it Fibonacci Quart.\/}  {\bf 21} (1983)
65--66. 

\bibitem{kw:ppd} D. E. Knuth and H. S. Wilf, The power of a prime that
divices a generalized binomial coefficient, {\it J. Reine Angew.\
Math.\/} {\bf 396} (1989), 212--219.

\bibitem{kum:ear} E. E. Kummer, \"Uber die Erg\"anzungss\"atze zu den
allgemeinen Reciprocit\"ats\-gesetzen, {\it J. Reine Angew.\ Math.\/}
{\bf 44} (1852) 93--146.

\bibitem{mac:ca} P. A. MacMahon, {\it Combinatorial Analysis,
Vols. 1 and 2}, Cambridge University Press, 1915,1916; reprinted by
Chelsea, 1960.

\bibitem{nar:tfp}  T. V. Narayana, Sur les treillis form\'es par les
partitions d'une unties et leurs applications \`a la th\'eorie des
probabilit\'es, {\it C. R. Acad.\ Sci.\ Paris\/} {\bf 240} (1955),
1188--1189. 

\bibitem{sag:cva} B. E. Sagan, Congruences via Abelian groups,
{\it J. Number Theory} {\bf 20} (1985), 210--237.

\bibitem{su:sln} R. Simion and D. Ullman,  On the structure of the
lattice of noncrossing partitions, {\it Discrete Math.\/} {\bf 98}
(1991), 193--206.

\bibitem{slo:ole} 
\begin{flushleft}
N. J. A. Sloane, ``The On-Line Encyclopedia of
Integer Sequences,'' available at
\href{http://www.research.att.com/~njas/sequence/}{\texttt http://www.research.att.com/$\sim$njas/sequences/}.
\end{flushleft}

\bibitem{sul:nd} R. A. Sulanke, The Narayana distribution,
{\it J. Statist.\ Plann.\ Inference\/} {\bf 101} (2002), 311--326.

\end{\bib}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B50; Secondary 05A10, 11A07, 11B64.

\noindent \emph{Keywords: } divisibility, Narayana numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001263} and \seqnum{A000108}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 7 2005;
revised version received  April 14 2005.
Published in {\it Journal of Integer Sequences},
May 15 2005.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


.