% $Id: catalan.tex,v 1.1.1.4 2004/10/04 17:25:16 nthiery Exp $
\begin{Mhelppage}{catalan}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{stefanw}{5.6.00}{fertig}
\Mproofread{nthiery}{10/2003}{proofread}

\begin{MInfo}
  \eng{Catalan numbers}
\end{MInfo}


\begin{MIntro}
  \eng{\Mthis(n) returns the \Mpar{n}-th Catalan number.}
\end{MIntro}

\begin{MCalls}
  \Mcall{n}
\end{MCalls}

\begin{MParameters}
  \param{n} 
  \eng{nonnegative integer}
\end{MParameters}

\begin{MReturnValue}
  \eng{A positive integer.}
\end{MReturnValue}

\begin{MDetails}
  \eng{
    \begin{sloppypar}
    The Catalan numbers are ubiquitous in combinatorics. For
    example, \Mthis(n) counts the Dyck words of size \Mpar{n}, the
    ordered trees with \Mpar{n} nodes, the binary trees with \Mex{n+1}
    nodes, the complete binary trees with \Mex{2n+1} nodes, the
    standard tableaux with two rows of size \Mpar{n},
    the triangulations of a regular \Mex{n+2}-gone, or the non-crossing
    partitions of \Mmath{{1,2,...,n}}{\{1,2,\ldots,n\}}.
    \end{sloppypar}
}%
  \eng{\Mthis(n) is calculated using the formula \Mdmath{catalan(n) =
      binomial(2*n,n) / (n+1)} {catalan(n)=\frac{1}{n+1}\binom{2n}{n}}}
\end{MDetails}

\MKeywords{combinatorics,catalan}

\begin{MExample}{ex1}
  \eng{We compute the $5$-th Catalan number:}
  \begin{Mexin}
combinat::catalan(5) 
  \end{Mexin}
  \begin{Mexout}
                              42
  \end{Mexout}
  \eng{Correct answer. But what was the question ?}
\end{MExample}

\begin{MExample}{ex2}
  \eng{We compute the first Catalan numbers:}
  \begin{Mexin}
combinat::catalan(n) $ n = 0..6
  \end{Mexin}
                                % $ <- for emacs's latex mode
  \begin{Mexout}
                    1, 1, 2, 5, 14, 42, 132
  \end{Mexout}

  \eng{They coincide with the number of Dyck words:}
  \begin{Mexin}
combinat::dyckWords::count(n) $ n = 0..6
  \end{Mexin}
                                % $ <- for emacs's latex mode
  \begin{Mexout}
                    1, 1, 2, 5, 14, 42, 132
  \end{Mexout}
  \eng{They also coincide with the numbers of tableaux with two rows
    or two columns of the same size:}
  \begin{Mexin}
1, nops(combinat::tableaux::list([2 $ n])) $ n = 1..6;
1, nops(combinat::tableaux::list([n $ 2])) $ n = 1..6;
  \end{Mexin}
  \begin{Mexout}
                    1, 1, 2, 5, 14, 42, 132

                    1, 1, 2, 5, 14, 42, 132
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex3}
  \eng{If one uses a wrong argument, an error message is returned}
\begin{Mexin}
combinat::catalan(-1) 
\end{Mexin}
\begin{Mexout}
Error: Wrong type of 1. argument (type 'Type::NonNegInt' expec\
ted,
       got argument '-1');
during evaluation of 'combinat::catalan'
\end{Mexout}
\end{MExample}

%\begin{MBackground}
  %\eng{References\par
  %}
%\end{MBackground}

\begin{MChanges}
  \version{2.5}
  \new
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
