% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A short conceptual proof \\ of Narayana's path-counting formula}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Mihai Ciucu\thanks{Research supported in part by NSF grant DMS-1101670 and DMS-1501052.}\\
\small Department of Mathematics\\[-0.8ex]
\small Indiana University \\[-0.8ex] 
\small Bloomington, Indiana 47405\\
\small\tt mciucu@indiana.edu\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{May 10, 2016}{Sept 7, 2016}\\
\small Mathematics Subject Classifications: 05A15, 05A17}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
We deduce Narayana's formula for the number of lattice paths that fit in a Young diagram as a direct consequence of the Gessel-Viennot theorem on non-intersecting lattice paths.
  % keywords are optional
  
\bigskip\noindent \textbf{Keywords:} lattice paths;
 Young diagram; Narayana's path-counting formula
\end{abstract}

%\section{Introduction}

Let $\lambda$ and $\mu$ be two partitions so that $\mu\subset\lambda$, and consider the skew Young diagram $\lambda/\mu$ (see Figure 1 for an example). We give a conceptual proof for the fact that the number of minimal lattice paths\footnote{A minimal lattice path between two lattice points on $\Z^2$ is a lattice path with the smallest possible number of steps connecting the two points.} on $\Z^2$ contained in this skew Young diagram from its southwestern to its northeastern corner is
%
\begin{equation}
\det\left({\binom{\lambda_j-\mu_i+1}{j-i+1}}_{1\leq i,j\leq n}\right)
\end{equation}
%
($n$ being the number of parts in $\lambda/\mu$), an extension of Narayana's formula \cite{Na} due to Kreweras \cite{Kr} (see \cite{Natwo}). Narayana's formula is the special case $\mu=\emptyset$, which we include below for completeness.


\begin{theorem}
  \label{Thm:NT} The number of minimal lattice paths on $\Z^2$ contained in the Young diagram of any partition $\lambda$ with $n$ parts is equal to 
\begin{equation}
\det\left({\binom{\lambda_j+1}{j-i+1}}_{1\leq i,j\leq n}\right).
\end{equation}
\end{theorem}


%
\begin{figure}[h]
\centerline{
\hfill
{\includegraphics[width=0.40\textwidth]{1-1.eps}}
\hfill
{\includegraphics[width=0.40\textwidth]{1-2.eps}}
\hfill
}
\vskip-0.1in
\caption{The skew shape $(9,7,6,2)/(3,1)$ (left); the corresponding region $R$ (right).}
\vskip-0.1in
\end{figure}
%



%\begin{proof}
 
%\end{proof}

Consider the region $R$ on the triangular lattice corresponding to $\lambda/\mu$ indicated by the the outside contour in Figure 2 --- it is obtained from the Young diagram of $\lambda/\mu$ by affinely deforming it so that its unit squares become unit rhombi on the triangular lattice, and then translating the southeastern boundary one unit in the $-\pi/3$ polar direction. 
%For we will argue that the number of tilings of $R$ by unit rhombi (a.k.a. lozenge tilings) is equal to both the number of lattice paths considered above and (1).
%Indeed, 
Recall that lozenge tilings of regions on the triangular lattice are in one-to-one correspondence with families on non-intersecting paths of rhombi (see \cite{DT}). The latter can be chosen in three different ways, depending on whether the segments where the paths of lozenges start and end point in the $-\pi/3$, $\pi/3$ or $-\pi$ polar directions. For the region $R$, the first of these three ways yields a single path of rhombi (lightly shaded in Figure 2), which can be regarded as a lattice path in $\lambda/\mu$ connecting the southwestern and northeastern corners. On the other hand, the second way yields a family of $n$ non-intersecting paths of rhombi, which can be regarded as non-intersecting lattice paths on $\Z^2$. By the Gessel-Viennot theorem \cite{GV}, their number is the determinant of the $n\times n$ matrix whose $(i,j)$-entry is the number of minimal lattice paths on $Z^2$ from the $i$-th starting point to the $j$-th ending point. One readily checks that these are precisely the entries of the  matrix in (1). This proves formula~(1). 




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{figure}[!h]
%  \begin{center}
%    % use \includegraphics to import figures 
%    % \includegraphics{filename}
%  \end{center}
%  \caption{\label{fig:InformativeFigure} Here is an informative
%    figure.}
%\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{DT} G. David and C. Tomei.  
\newblock The problem of the calissons.  
\newblock {\em Amer\. Math\. Monthly}, 96:429--431, 1989.


\bibitem{GV} I. M. Gessel and X. Viennot. 
\newblock Binomial determinants, paths, and hook length formulae.
\newblock {\em Adv. in Math.}, 58:300--321, 1985.

\bibitem{Kr} G. Kreweras.
\newblock  Sur une classe de probl\`emes d\'enombrement li\'es au trellis des partitions de entiers.
\newblock {\em Cahiers du Bur. Univ. de Rech. Op\'er.}, 6:5--105, 1965.  

\bibitem{Na} T. V. Narayana.
\newblock   A combinatorial problem and its application to probability theory.
\newblock {\em J. Indian Soc. Agr. Stat.}, 7:169--178, 1955.

\bibitem{Natwo} T. V. Narayana.
\newblock  Lattice path combinatorics with statistical applications.
\newblock {\em Mathematical Expositions No. 23}, University of Toronto Press, Toronto, 1979. 


\end{thebibliography}

\end{document}