<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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{amsthm}
\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://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{\summ}{\sum\limits}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Central Component of a Triangulation
}
\vskip 1cm
\large
Alon Regev\\
Department of Mathematical Sciences\\
Northern Illinois University\\
DeKalb, IL 60115\\
USA \\
\href{mailto:regev@math.niu.edu}{\tt regev@math.niu.edu} \\
\end{center}

\vskip .2 in



\begin{abstract}
    We define the central component of a triangulation of a regular convex polygon as the diameter or triangle containing its geometric center.
    This definition yields a new recursion relation for Catalan numbers, which can be used to derive congruence relations. We generalize this idea to $k$-angulations, giving congruences of $k$-Catalan numbers. We also enumerate the triangulations that include a fixed vertex in their central components.
\end{abstract}

\section{Introduction}
	Considering a triangulation of a regular convex polygon as a subset of $\mathbb{R}^2$ centered at the origin, define its {\em central component} to be the diameter or triangle that contains the origin (see Figure \ref{Fig1}). More generally, every dissection of a polygon can be associated with its set of components, including one central component. Bowman and the author used components and central components to enumerate symmetry classes of dissections in a paper \cite{BR2}, where these notions are more formally defined.  In this note we use central components to obtain new recursion relations for Catalan and $k$-Catalan numbers, and use these recursions to prove congruence relations of these numbers. We also enumerate the triangulations that include a fixed vertex in their central components.


	Let $C_n$ be the $n$-th Catalan number, so $C_{n-2}$ is the number of triangulations of an $n$-gon, and let $C_x=0$ unless $x$ is a nonnegative integer. The Catalan numbers satisfy the recursion
\begin{align}\label{standard}
\summ_{k=0}^nC_k	C_{n-k}=C_{n+1}.
\end{align}

Consider a triangulation of an $n$-gon as a labeled graph with vertices $0,1,\ldots, n-1$ and edges denoted $xy$ for distinct vertices $x$ and $y$. The edges include $n$ sides $01, 12, \ldots ,(n-1)0$ and $n-3$ diagonals. The {\em cyclic length} of an edge $xy$, with $x&lt;y$, is defined as \[\min \{y-x, n+x-y\}.\]

By enumerating the triangulations of an $n$-gon according to their central components, we obtain the following new recursion relation, which is one of the main results of this paper.
\begin{lemma}\label{center-lem}
For any $n\ge 3$,
\begin{align}\label{center-eq}
C_{n-2}=\frac n 2 C_{n/2-1}^2+\summ_{\substack{i+j+k=n\\ i\le j \le k&lt;n/2}}m_{ijk}C_{i-1}C_{j-1}C_{k-1},
\end{align}
where
\begin{align*}
m_{ijk}=
\begin{cases}
\frac n 3, &amp; \text{if }i=j=k;\\
n,  &amp; \text{if }i&lt;j=k \text{ or } i=j&lt;k;\\
2n, &amp; \text{if } i&lt;j&lt;k.\\
\end{cases}
\end{align*}
\begin{proof}
The first term of \eqref{center-eq} enumerates the triangulations whose central component is a diameter: there are $n/2$ possible positions for a diameter, and for each of these there are $C_{n/2-1}$ triangulations of each of the two resulting $(n/2+1)$-gons.
In the summation, $m_{ijk}$ is the number of ways to position a triangle whose sides have cyclic lengths $i, j, k$ inside an $n$-gon (see Figure \ref{Fig1}). The conditions under the summation ensure that indeed this is a central triangle.
The three cases determining $m_{ijk}$ correspond to the central triangle being equilateral, isosceles or scalene. Each position of the triangle results in an $(i+1)$-gon, a $(j+1)$-gon and a $(k+1)$-gon, and these can be triangulated in $C_{i-1}$, $C_{j-1}$, and $C_{k-1}$ ways, respectively.
\end{proof}
\end{lemma}


\begin{figure}
\begin{center}
\epsfxsize=1.6in
\leavevmode\epsffile{centerFig1.eps}
\end{center}
\caption{A central triangle with $n=12$, $i=3$, $j=4$ and $k=5$.}\label{Fig1}
\end{figure}


\section{Congruence relations}

Congruence relations of Catalan numbers $C_n$ and related sequences have been the object of extensive study (see \cite{AK,DS} and the references therein). We next show that Lemma \ref{center-lem} can be used to derive some results of this nature.
Note that the following result can also be proved using \eqref{standard}. In what follows we use the notation
\begin{align*}
t_{ijk}=m_{ijk}C_{i-1}C_{j-1}C_{k-1},
\end{align*}
with $m_{ijk}$ as in Lemma \ref{center-lem}.
\begin{theorem}\label{oddcats}
$C_n$ is odd if and only if $n=2^a-1$ for some integer $a\ge 0$.
\begin{proof}
We use induction on $n$, with the base cases easily verified. The proof will follow from the next observation: the term $t_{ijk}$ (with $i\le j\le k$) is odd if and only if $i=1$ and $j=k=2^c$ for some $c\ge 1$.
To see this, first note that by induction, any term of the form $t_{1,2^c,2^c}$ is odd. Conversely, if $t_{ijk}$ is odd
then by induction, $i=2^b$, $j=2^c$ and $k=2^d$ for some $0\le b\le c\le d$. Since $n=2^b+2^c+2^d$ is odd it follows that
$b=0$, and since $m_{ijk}$ is odd then $c=d$ as claimed.

Now let $n=2^a+1$, with $a\ge 1$. On the right hand side of \eqref{center-eq} we have $C_{n/2-1}=0$, and the observation above implies that $t_{ijk}$
is odd for exactly one term of the summation, so $C_{n-2}$ is odd.

Conversely, suppose that $C_{n-2}$ is odd. If $n$ is even then so are the terms $t_{ijk}$, so that $\frac n 2 C_{n/2-1}^2$ must be odd.
Therefore $n/2$ is odd, and at the same time by induction $n/2=2^b$ for some $b\ge 0$. Thus $b=0$ and $n=0=2^0-1$.
If $n$ is odd then $C_{n/2-1}=0$, so at least one of the $t_{ijk}$ must be odd, and by the observation above this implies $n=1+2^c+2^c=1+2^{c+1}$, completing the proof.
\end{proof}
\end{theorem}

We next use Lemma \ref{center-lem} to prove a recent result of Eu, Liu and Yeh \cite{ELY}. Another proof is given by Xin and Xu \cite[Theorem 5]{XX}.
\begin{theorem}\cite[Theorem 2.3]{ELY}
For all $n\ge 0$,
\begin{align}\label{mod4eq}
C_n\equiv_4
\begin{cases}
1, &amp; \text{ if } n=2^a-1 \text{ for some } a\ge 0;\\
2, &amp; \text{ if } n=2^a+2^b-1 \text{ for some } b&gt;a\ge 0;\\
0, &amp; \text{ otherwise.}\\
\end{cases}
\end{align}
\begin{proof}
In what follows, we repeatedly make use without mention of Theorem \ref{oddcats} and of the uniqueness of binary representation. By verifying the base cases we may assume $n\ge 10$ and proceed by induction on $n$. Consider the three cases on the right hand side of \eqref{mod4eq}.

\begin{enumerate}
\item The case $n=2^a-1$:

 Let $n=2^a+1$ with $a\ge 4$, and we show that $C_{n-2}\equiv_4 1$. Reducing \eqref{center-eq} modulo $4$ gives
\begin{equation}\label{mod4}
C_{n-2}\equiv_4 \summ_{\substack{i+j+k=n\\ i\le j \le k&lt;n/2}}m_{ijk}C_{i-1}C_{j-1}C_{k-1}.
\end{equation}
Since $C_{2^{a-1}-1}$ is odd,
\begin{equation}\label{t1}
t_{1,2^{a-1},2^{a-1}}=n C_0 C_{2^{a-1}}C_{2^{a-1}}\equiv_4 1,
\end{equation}
and in fact this is the only term not divisible by $4$. To see this, consider the terms for which $t_{ijk}\not \equiv_40$.
\begin{enumerate}
\item Suppose $i=j=k$. Then $C_{i-1}$ must be odd, so $i=2^c$ for some $c\ge 0$. Therefore
\[3(2^c-1)=i+j+k=n=2^a+1,\] or equivalently, $2^{c+1}+2^c=2^a+2^2$.
Therefore $a=3$, $c=2$ and $n=9$, contrary to the assumption that $n\ge 10$.

\item Suppose $i=j&lt;k$. Then $C_{i-1}$ must be odd, so $i=j=2^c$ for some $c\ge 0$.  Since
$C_{k-1}\not \equiv_4 0$, by induction either $k=2^d$ with $d&gt;c$, or $k=2^d+2^e$ with $e&gt;d\ge c$.
In the former case, this implies \[2^a+1=2i+k=2^{c+1}+2^d,\] and in the latter case \[2^a+1=2^{c+1}+2^d+2^e,\] both cases resulting in a contradiction.

\item Suppose $i&lt;j=k$. As above, it follows that $j=k=2^e$ and either $i=2^c$, with $e&gt;c$,
or $i=2^c+2^d$, with $e\ge d&gt;c$. In the former case, \[2^a+1=i+2j=2^c+2^{e+1},\] which implies $c=0$ and $e=a-1$, yielding the term given by \eqref{t1}. The latter case again results in a contradiction.

\item Suppose $i&lt;j&lt;k$. Since $m_{ijk}$ is even, $C_{i-1}C_{j-1}C_{k-1}$ must be odd. Therefore $i=2^c$, $j=2^d$ and $k=2^e$ for some $e&gt;d&gt;c\ge 0$, but then $2^e+2^d+2^c=2^a+1$, which is impossible.
\end{enumerate}

\item The case $n=2^a+2^b-1$:

Let $n=2^a+2^b+1$, and we show that $C_{n-2}\equiv_4 2$.
If $a=0$, then $n/2-1=2^{b-1}$, so by induction on $b$ we have $C_{n/2-1}\equiv_4 2$. If $a\ge 1$, then by definition $C_{n/2-1}= 0$.
In either case, \eqref{mod4} still holds. Note that $C_{2^0}=1$ and if $a\ge 1$ then by induction $C_{2^a}\equiv_4 2$. Therefore
\begin{equation}\label{2t}
t_{2^a+1,2^{b-1},2^{b-1}}=nC_{2^a}C_{2^{b-1}-1}C_{2^{b-1}-1}\equiv_4 2.
\end{equation}
Again, we show that all other $t_{ijk}$ are divisible by $4$, by considering the terms for which $t_{ijk}\not \equiv_4 0$.
\begin{enumerate}
\item Suppose $i=j=k$. Then we must have $i=2^c$ for some $c\ge 0$, but this implies \[2^{c+1}+2^c=n=2^a+2^b+1,\]
which is impossible for sufficiently large $n$.

\item Suppose $i&lt;j&lt;k$. Then $C_{i-1}C_{j-1}C_{k-1}$ is odd, so $i=2^c$, $j=2^d$ and $k=2^e$ for some $e&gt;d&gt;c\ge 0$.
Therefore \[2^c+2^d+2^e=n=2^a+2^b+1.\] Since we may assume $a\ge 1$ (otherwise $2n\equiv_4 0$), it follows that $c=0$, $d=a$ and $e=b$. But this implies $k\ge n/2$, contrary to the conditions under the summation.

\item Suppose that $i&lt;j=k$. Since $C_{k-1}$ must be odd, $k=2^e$ for some $e\ge 0$. Now if $i=2^d$ for some $d&lt;e$ then
\[2^a+2^b+1=2^d+2^{e+1},\] which is impossible. Therefore by induction we have $i=2^c+2^d$, with $e&gt;d&gt;c\ge 0$. This gives
\[2^a+2^b+1=i+2k=2^c+2^d+2^{e+1},\]
so $c=0$ and $2^a+2^b=2^d+2^{e+1}$. It follows that $e=b-1$ and $d=a$, which is the term given by \eqref{2t}.
A similar analysis of the case $i=j&lt;k$ results in a contradiction.
\end{enumerate}

\item {Otherwise:}

 We show that $C_{n-2}\equiv_40$ unless $n-2$  has one of the forms above.
If $C_{n/2-1}^2\not \equiv_4 0$ then $n/2=2^a$ for some $a\ge 0$. For $n$ sufficiently large this implies $8|n$  so that
$\frac n 2C_{n/2-1}^2\equiv_4 0$. Next, consider the terms for which $t_{ijk}\not \equiv_4 0$.

\begin{enumerate}
\item Suppose $i=j=k$. Since $C_{n/3-1}^3\not \equiv_4 0$, we must have $n/3=2^a$ for some $a\ge 0$. Thus  $n=3\cdot 2^a$. However, for sufficiently large $n$ this would imply that $m_{ijk}=n/3\equiv_4 0$.

\item Suppose $i=j&lt;k$ or $i&lt;j=k$. If $C_{i-1}C_{j-1}C_{k-1}$ is odd then
\begin{align}\label{bc}
n=2^{b+1}+2^c
\end{align}
for some $b,c\ge 0$ .
Now
\[2^c&lt;n/2=2^b+2^{c-1},\]
so $c-1&lt; b$ and in fact $c&lt;b$ (since $c-1=b$ would imply $n=2^c\equiv_40$).
Therefore  \eqref{bc} implies that $c=0$ or $c=1$, so $n-2=2^{b+1}-1$ or $n-2=2^{b+1}+2^0-1$.

The only case left to check is when $n$ is odd and $C_{i-1}C_{j-1}C_{k-1}\equiv_4 2$. In this case, by induction $n=2\cdot 2^b+(2^c+2^d)$ with $b,c,d\ge 0$ and $d&gt;c$.
Since $n$ is odd then $c=0$, so that $n-2=2^{b+1}+2^d-1$.
\item Suppose $2nC_iC_jC_k\not \equiv_4 0$. Since $C_i$, $C_j$ and $C_k$ are odd, $n=2^b+2^c+2^d$ for some $d&gt;c&gt;b\ge 0$. Since $n$ is odd, $b=0$ and $n-2=2^c+2^d-1$.
\end{enumerate}
\end{enumerate}
 \end{proof}
 \end{theorem}

Another congruence relation follows immediately from reducing \eqref{center-eq} modulo a prime $p\ge 5$.

\begin{theorem}\label{modpthm}
If $p\ge 5$ is prime and $n\equiv_p -2$ then $C_n\equiv_p 0$.
\end{theorem}

\section{\texorpdfstring{Generalization to $k$-angulations}{k}}

Lemma \ref{center-lem} can be generalized to give a recursion for the number of {\em $k$-angulations}, which are partitions of a polygon into $k$-gons.
Let $f_{n,k}$ be the number of $k$-angulations of an $n$-gon. It is well known (see, for example, the paper of Przytycki and Sikora \cite{PS}) that

\begin{align}\label{kang-Fuss-eq}
 f_{(k-1)n+2,k+1}=C_{n,k}
 \end{align}

where
 \[C_{n,k}=\frac 1{(k-1)n+1} \binom{kn}{n}\]
are the $k$-Catalan numbers \cite[A137211]{Sl}.
Define $f_{n,k}=0$ unless $n=(k-2)m+2$ for some integer $m\ge 0$. The proof of the following Lemma is completely analogous to that of Lemma \ref{center-lem}.

\begin{lemma}
For any $n\ge 2$ and $ k\ge 3$,
\begin{align}\label{kang-eq}
f_{n,k}=\frac n 2 f_{n/2+1,k}^2+\summ_{\substack{i_1+\ldots+ i_k=n\\ i_1\le \ldots \le i_k &lt;n/2}} m_{i_1\ldots i_k} f_{i_1+1,k} \cdots f_{i_k+1, k},
\end{align}
where $m_{i_1\ldots i_k}$ is the number of ways to position a $k$-gon with sides of cyclic lengths $i_1,\ldots, i_k$ inside an $N$-gon for $N=i_1+\ldots+i_k$.
\end{lemma}

For example, let
\[Q_n=\frac 1 {2n+1}\binom{3n}{n}\]
be the number of quadrangulations of a $(2n+2)$-gon, and let $Q_x=0$ unless $x$ is a nonnegative integer. Then
\begin{align}\label{quads-eq}
Q_n=(n+1)Q_{n/2}^2+\summ_{\substack{i+j+k+l=2n+2\\ i\le j \le k\le l&lt;n+1}}m_{ijkl}Q_{(i-1)/2}Q_{(j-1)/2}Q_{(k-1)/2}Q_{(l-1)/2},
\end{align}
where
\begin{align}
m_{ijkl}=
\begin{cases}
\frac N 4, &amp; \text{ if } i=l;\\
N,&amp; \text{ if } i=k&lt;l \text{ or } i&lt;j=l;\\
\frac{3N}2,&amp; \text{ if } i=j&lt;k=l;\\
3N, &amp; \text{ if } i=j&lt;k&lt;l \text{ or } i&lt;j=k&lt;l \text{ or } i&lt;j&lt;k=l; \\
6N, &amp; \text{ if } i&lt;j&lt;k&lt;l\\
\end{cases}
\end{align}
for $N=i+j+k+l$.

Theorem \ref{modpthm} can be generalized by reducing equation
\eqref{kang-eq} modulo a prime $p\ge 3$.

\begin{theorem}
If $p\ge 3$ is prime with $p\not | k$ and $p | n$
then $f_{n,k}\equiv_p 0$.
\begin{proof}
For a given $k$-gon, the number of cyclic permutations of the $k$ sides that leave the $k$-gon unchanged is divisible by $k$. Therefore the number of inequivalent rotations of the
$k$-gon inside the $n$-gon is divisible by $n/k$. It follows that $m_{i_1\ldots i_k}$ is divisible by $n/ k$, and so the given assumptions imply that $p$ divides $f_{n,k}$.
\end{proof}
\end{theorem}


\section{Triangulations with a fixed vertex in their central component}

L. Shapiro \cite{Sh}
proposed the following question: how many triangulations include the vertex $0$ in their central component? The following theorem answers this question.

\begin{theorem}
Let $n\ge 3$. The number $f(n)$ of triangulations of an $n$-gon with the vertex $0$ outside their central component is
\begin{align*}
f(n)={\frac 1  2}C_{n-1}-C_{n-2}+{\frac 1  2}C_{n/2-1}^2.
\end{align*}
\begin{proof}
Enumerate these triangulations according to the cyclic length $l$ of the shortest diagonal that separates $0$ form the center (see Figure \ref{Fig2}).

Given such $l$, suppose this diagonal is given by $k(n+k-l)$. Note that $1\le k\le l-1$.
Since this is the shortest such diagonal, the triangulation must also
include the diagonals $0k$ and $0(n+k-l)$, forming a triangle. The regions outside of this triangle can be triangulated arbitrarily. Therefore
\begin{align*}
f(n)&amp;=\summ_{l=2}^{\lfloor n/2 \rfloor} \summ_{k=1}^{l-1} C_{n-l-1}C_{l-k-1}C_{k-1}\\
	&amp;=\summ_{l=2}^{\lfloor n/2 \rfloor}  C_{n-l-1}C_{l-1}\\
	&amp;=\summ_{m=1}^{\lfloor n/2 \rfloor-1}C_mC_{n-2-m}\\
	&amp;={\frac 1 2} \summ_{m=1}^{n-3}C_mC_{n-2-m}+{\frac 1 2}C_{n/2-1}^2,\\
\end{align*}
where the second equality follows from \eqref{standard}. The result now follows by again applying \eqref{standard}.
\end{proof}
\end{theorem}

\begin{figure}[H]
\begin{center}
\epsfxsize=1.8in
\leavevmode\epsffile{centerFig2.eps}
\end{center}
\caption{Triangulations with the vertex $0$ outside the central component.}\label{Fig2}
\end{figure}

It seems that the sequence  $a(n)=f(n-3)$ is given in an entry of Sloane's encyclopedia \cite[A027302]{Sl}:

\[a(n)=\summ_{0\le k &lt; n/2}T(n,k)T(n,k+1),\]

where \[T(n,k)=  \frac{n-2k+1}{n-k+1}\binom{n}{k}.\]

In this entry it also asserted that $a(n)$ is the number of Dyck $(n+2)$-paths with $UU$ spanning their midpoint.
It would be interesting to determine whether any known bijection between triangulations and Dyck paths gives this correspondence.

\begin{thebibliography}{99}
\bibitem{AK} R. Alter and K. Kubota, Prime and prime power divisibility of Catalan numbers, {\em J. Combin. Theory Ser. A} {\bf 15} (1973), 243--256.

\bibitem{BR2} D. Bowman and A. Regev,
Counting symmetry classes of dissections of a convex regular polygon,
preprint,  \url{http://arxiv.org/abs/1209.6270}.

\bibitem{DS}  E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, {\em J. Number Theory} {\bf 117} (2006), 191--215.

\bibitem{ELY} S. Eu, S. Liu, and  Y. Yeh, Catalan and Motzkin numbers
modulo 4 and 8, {\em European J. Combin.} {\bf 29} (2008), 1449--1466.

\bibitem{PS}
J. H. Przytycki and A. Sikora, Polygon dissections and Euler, Fuss, Kirkman and Cayley numbers, {\em J. Comb. Theory A} {\bf 92} (1) (2000), 68--76.

\bibitem{Sh} L. Shapiro, Private communication, 2012.

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

\bibitem{XX} G. Xin and J. Xu, A short approach to Catalan numbers modulo $2^r$, {\em Electron. J. Combin.} {\bf 18} (2011), P177.
\end{thebibliography}

\bigskip
\hrule
\bigskip
\noindent {\em 2010 Mathematics Subject Classification: } Primary 05A15; Secondary 05A10.

\noindent {\em Keywords:} Catalan numbers, polygon triangulation, polygon dissection, congruence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A137211}, and
\seqnum{A027302}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 21 2012;
revised version received March 1 2013. 
Published in {\it Journal of Integer Sequences}, March 9 2013.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                




</pre></body></html>