\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}{-.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}

\begin{center}
\vskip 1cm{\LARGE\bf
Combinatorial Enumeration of Partitions
\\
\vskip .11in
of a Convex Polygon
}
\vskip 1cm
\Large
 Dong Zhang and Dongyi Wei\\
 Peking University\\
 Beijing 100871\\
 P. R. China\\
\href{mailto:dongzhang@pku.edu.cn}{\tt dongzhang@pku.edu.cn} \\
\href{mailto:jnwdyi@163.com}{\tt jnwdyi@163.com}\\

\ \\

Demin Zhang\\
 Xinxiang\\
 Henan\\
 P. R. China\\
\href{mailto:winlxm1972@sina.cn}{\tt winlxm1972@sina.cn}\\
\end{center}

\newcommand{\A}{\ensuremath{\mathcal{A}}}
\newcommand{\card}{\ensuremath{\mathrm{Card}}}
\newcommand{\res}{\ensuremath{\mathrm{Res}}}

\begin{abstract} 
We establish a class of polynomials on convex polygons,
which provides a new counting formula to all partitions of a convex polygon by non-intersecting diagonals.
\end{abstract}

\section{Introduction}

Counting partitions of a convex polygon of a specified type by using its non-intersecting diagonals is a problem which can go back to Euler, Catalan, Cayley \cite{Cayley} and Przytycki and Sikora \cite{Przy}. Recently, Floater and Lyche \cite{Michael} showed a way to enumerate all partitions of a convex polygon of a certain type as follows.

\begin{proposition}[Floater, Lyche \cite{Michael}]\label{pro:1}
A partition of a convex $(n + 1)$-gon is said to be of type $\mathbf{b} = (b_2, b_3,\ldots , b_n)$ if it contains $b_2$ triangles, $b_3$ quadrilaterals, and so on, and in general $b_i$ $(i + 1)$-gons. Then the number of partitions of a convex $(n+1)$-gon of type $\mathbf{b}=(b_2,b_3,\ldots,b_n)$ with $b_2+b_3+\cdots+b_n=k$ and $2b_2+3b_3+\cdots+nb_n=n+k-1$, is
$$C(\mathbf{b})=\frac{(n+k-1)(n+k-2)\cdots(n+1)}{b_2! b_3! \cdots b_n!}.$$
\end{proposition}

Inspired by Lee's result \cite{Lee}, Shephard \cite{Shephard} got an interesting equality on convex polygons with $n+2$ sides as follows.
\begin{proposition}[Lee \cite{Lee}, Shephard \cite{Shephard}]\label{pro:2}
Given a $(n+2)$-gon, let $d_1$ be the number of diagonals, $d_2$ be the number of disjoint pairs of diagonals, and, in general, $d_i$ be the number of sets of $i$ diagonals of the polygon which are pairwise disjoint. Then we have
\[{d_1} - {d_2} + {d_3} -  \cdots  + {( - 1)^n}{d_{n - 1}} = 1 + {( - 1)^n}\]
\end{proposition}
The original proof \cite{Lee} of Proposition \ref{pro:2} is very complicated.
We will provide a rather simple proof in the last part.

We organize this paper as follows. Section \ref{sec:main} shows the main result (Theorem \ref{1}) via the properties of a derivation acting on a special polynomial algebra. In Section \ref{sec:app}, we prove Propositions \ref{pro:1} and \ref{pro:2} by our main result.

\section{Main results}\label{sec:main}
We call a vector space $\A:=(\A,+)$ an algebra over the real field $\mathbb{R}$, if $\A$ possesses a bilinear product satisfying $(ab)c=a(bc)$, $(a+b)(c+d)=ac+bc+ad+bd$ and  $(\lambda\mu)(ab)=(\lambda a)(\mu b)$, for all $ \lambda,\mu\in \mathbb{R},~a,b,c,d\in\A$. Recall that a linear map $D$ mapping $\A$ into itself is called a derivation if $D(xy)=(Dx)y+x(Dy)$ for all $x,y\in\A$. 
\begin{definition}
Let $\A$ be a polynomial algebra generated by $\{x_i:i\in \mathbb{N}^+\}$, i.e., the collection of the polynomials with the form $\sum_{k=1}^m\sum_{i_1,\ldots,i_k\in \mathbb{N}^+}a_{i_1,\ldots,i_k}x_{i_1}\cdots x_{i_k}$, where $a_{i_1,\ldots,i_k}\in \mathbb{R}$ and $m\in \mathbb{N}^+$. For given $y_i\in \A$, $i\in \mathbb{N}^+$, let $D':\{x_i:i\in \mathbb{N}^+\}\to \A$ be such that $x_i\mapsto y_i$, $i\in \mathbb{N}^+$.
The unique extension of $D'$ to $\A$ via Leibniz's law determines a derivation $D$ on $\A$, which is called the derivation defined by $D'$.
\end{definition}

\begin{lemma}\label{0}
Let $\A$ be a polynomial algebra generated by~$\{X_1,X_2,\ldots,X_n,\ldots\}$.~Assume $D$ is a derivation with action defined by
\begin{equation}\label{eq:th1_1}
DX_n=(an+b)\sum_{i=1}^{n-1}X_iX_{n-i},~n\geq 2,~DX_1=0,
\end{equation}
where $a$ and $b$ are given real numbers. Then we have \begin{equation}\label{eq:th1_2}
D^mX_n=\frac{\prod_{k=1}^{m}(2an+(k+1)b)}{m+1}\sum_{i_1+i_2+\cdots+i_{m+1}=n}X_{i_1}X_{i_2}\cdots X_{i_{m+1}}.\end{equation}
\end{lemma}
\begin{proof}
Let $X(t)=\sum_{i\ge 1}X_it^i$ be a generating function. It follows from
$$X(t)^2=\sum_{n\ge 2}\left(\sum_{i=1}^{n-1}X_iX_{n-i}\right)t^n$$ that
\begin{align*}
 \left(at\frac{d}{dt}+b\right)X(t)^2&=\sum_{n\ge2}\left(\sum_{i=1}^{n-1}X_iX_{n-i}\right)
 \left(at\frac{d}{dt}+b\right)t^n
 =\sum_{n\ge2}\left(\sum_{i=1}^{n-1}X_iX_{n-i}\right)(an+b)t^n
 \\&=\sum_{n\ge1}(DX_n) t^n=DX(t).
\end{align*}
Similarly, the statement \eqref{eq:th1_2} becomes
\begin{equation}\label{eq:derivation}
D^mX=\frac{1}{m+1}\prod_{i=1}^m\left(2at\frac{d}{dt}+(i+1)b\right)X^{m+1},
\end{equation}
where $X:=X(t)$. It is evident that \eqref{eq:derivation} holds for $m=1$. Assume that \eqref{eq:derivation} holds for $m=k$. Now we show that \eqref{eq:derivation} holds for $m=k+1$. In fact, together with \eqref{eq:derivation} for $m=k$ and the fact
\begin{align*}
DX^m&=mX^{m-1}DX=mX^{m-1}\left(at\frac{d}{dt}+b\right)X^2
\\&=2amX^{m}t\frac{d}{dt}X+bmX^{m+1}
\\&=\frac{m}{m+1}\left(2at\frac{d}{dt}+(m+1)b\right)X^{m+1},
\end{align*}
we immediately obtain
\begin{align*}
D^{k+1}X&=D(D^kX)=D\left(\frac{1}{k+1}\prod_{i=1}^k\left(2a\frac{d}{dt}+(i+1)b\right)X^{k+1}\right)
\\&=\frac{1}{k+1}\prod_{i=1}^k\left(2at\frac{d}{dt}+(i+1)b\right)DX^{k+1}
\\&=\frac{1}{k+1}\prod_{i=1}^k\left(2at\frac{d}{dt}+(i+1)b\right)
\frac{k+1}{k+2}\left(2at\frac{d}{dt}+(k+2)b\right)X^{k+2}
\\&=\frac{1}{k+2}\prod_{i=1}^{k+1}\left(2at\frac{d}{dt}+(i+1)b\right)X^{k+2}.
\end{align*}
Therefore, by mathematical induction, we have completed the proof.
\end{proof}
We call a strictly convex polygon with $n+2$ sides a $(n+2)$-gon, denoted by $X_n$, where $n\in \mathbb{N}^+$. Given an integer $n\ge 2$, we use $\Delta$ to denote a set of diagonals of $X_n$ which are pairwise disjoint. It should be noted that a $\Delta$ with $m$ elements divides $X_n$ into $m+1$ convex polygons, $X_{i_1},X_{i_2},\ldots,X_{i_m}$ and $X_{i_{m+1}}$ for some $i_1,i_2,\ldots,i_m$ and $i_{m+1}$ in $\{1,2,\ldots,n\}$. The set of such convex polygons is said to be a partition of the original convex polygon. We symbolically set $f(\Delta)=\prod_{j=1}^{m+1}X_{i_j}$ and $\card~\Delta=m$. Figure \ref{Fig} provides two examples of $X_n$ for $n=8$ and $n=10$, respectively.

\begin{figure}[h!]
\begin{center}
\epsfbox{polygon.eps}
\end{center}
\caption{The left figure shows $X_8$ with $\Delta=\{AD,AG,DG\}$ and the corresponding partition $\{ABCD,DEFG,AGHIJ,ADG\}$, where $\card~\Delta=3$, $f(\Delta)=X_1X_2X_2X_3$.
The right figure shows $X_{10}$ with $\Delta=\{AE,AJ,EJ,EG,GJ\}$ and the corresponding partition $\{ABCDE,EFG,GHIJ,AJKL,EGJ,AEJ\}$, where $\card~\Delta=5$, $f(\Delta)=X_1X_1X_1X_2X_2X_3$.}
 \label{Fig}
\end{figure}


\begin{theorem}\label{1}Given $n\in \mathbb{N}^+$ and $m\in \mathbb{N}$, we have\begin{equation}\label{eq:th2}\sum_{\card~\Delta=m}f(\Delta)=\frac{1}{m+1}{n+m+1\choose m}\sum_{i_1+i_2+\cdots+i_{m+1}=n}X_{i_1}X_{i_2}\cdots X_{i_{m+1}}.
\end{equation}
\end{theorem}
\begin{proof}
Consider partitions of $X_n$ with $m$ diagonals, in which the diagonals are labelled, say with integers $1,2,\cdots,m$. Then the derivation $D$ is an operator that acts as an analogue combinatorial device for splitting the polygon on a labelled diagonal; consequently, $D^m$ is an operator that splits the polygon (with $m$ diagonals) into $m + 1$ polygons. We then divide by $m!$ to remove the effect of labelling the diagonals, so that $\frac{D^m}{m!}$ is the operator that produces the counting series for partitioning a polygon into $m + 1$ parts.

Next, we calculate $DX_n$. Notice that there are $n-1$ diagonals starting from a vertex, and each diagonal divides $X_n$ into two parts. So we have $n-1$ ways to divide $X_n$, which can be expressed as $X_1X_{n-1}+X_2X_{n-2}+\cdots+X_{n-1}X_1$ by using our notation.
Since $X_n$ has $n+2$ vertices, the whole set of partitions of $X_n$ can be written as $(n+2)\sum_{i=1}^{n-1}X_iX_{n-i}$. However, each diagonal has two ends, and will be counted twice. Consequently, we should divide it by $2$, and get $DX_n=\frac{n+2}{2}\sum_{i=1}^{n-1}X_iX_{n-i}$. Taking $a=\frac{1}{2}$ and $b=1$ in Lemma \ref{0}, we have
$$\sum_{\card~\Delta=m}f(\Delta)=\frac{1}{m!}D^mX_n=\frac{1}{m+1}{n+m+1\choose m}\sum_{i_1+i_2+\cdots+i_{m+1}=n}X_{i_1}X_{i_2}\cdots X_{i_{m+1}}.$$
\end{proof}


\section{Applications}\label{sec:app}
A result about partitioning polygons is as follows.
\begin{corollary}\label{2}
Given $i_1,i_2,\ldots,i_{m+1}$ with $i_1+i_2+\cdots+i_{m+1}=n$. Then the number of different ways of cutting $X_n$ into sub-polygons $X_{i_1},X_{i_2},\ldots,X_{i_{m+1}}$ by diagonals is $\frac{S}{m+1}{n+m+1\choose m}$, where $S$ is the number of permutations of $i_1,i_2,\ldots,i_{m+1}$.
\end{corollary}
\begin{proof}
By Theorem \ref{1}, we obtain that there exist $\frac{S}{m+1}{n+m+1\choose m}$ ways to divide $X_n$ into $X_{i_1},X_{i_2},\ldots,X_{i_{m+1}}$, where $S$ is the number of permutations of $i_1,i_2,\ldots,i_{m+1}$.
\end{proof}
One can easily verify that Proposition \ref{pro:1} is equivalent to Corollary \ref{2}.
\begin{example}[Catalan numbers]

Let $m=n-1$. Then $i_1=i_2=\cdots=i_{m+1}=1$ is the only positive integer solution of $i_1+i_2+\cdots+i_{m+1}=n$. Hence $S=1$,
and we get the Catalan numbers $\frac{1}{n}{2n\choose n-1}=\frac{1}{n+1}{2n\choose n}$.
\end{example}

Next we give a new proof for Proposition \ref{pro:2} by using Theorem \ref{1} and the residue theorem.

\begin{proof}[Proof of Proposition \ref{pro:2}]
Consider $X_n$. Notice that the number of positive integer solutions of $i_1+i_2+\cdots+i_{m+1}=n$ is ${n-1\choose m}$. By Theorem \ref{1}, there are $\sum\limits_{i_1+i_2+\cdots+i_{m+1}=n}\frac{1}{m+1}{n+m+1\choose m}$  monomials on the right-hand side of (\ref{eq:th2}). Thus we get $d_m=\frac{1}{m+1}{n-1\choose m}{n+m+1\choose m}$, and then
\begin{align*}
\sum_{k=1}^{n-1}(-1)^kd_k&=\sum_{k=1}^{n-1}(-1)^{k-1}
\frac{{n-1\choose k}}{k+1}{n+k+1\choose k}
\\&=\sum_{k=1}^{n-1}(-1)^{k-1}\frac{{n\choose k+1}}{n}\res
\left(\frac{(1+u)^{n+k+1}}{u^{k+1}},0\right)
\\&=\frac{1}{n}\res
\left((1+u)^{n}\sum_{k=1}^{n-1}(-1)^{k-1}{n\choose k+1}\frac{(1+u)^{k+1}}{u^{k+1}},0\right)
\\&=\frac{1}{n}\res
\left((1+u)^{n}\left((1-\frac{u+1}{u})^n-(1-n\frac{u+1}{u})\right),0\right)
\\&=\frac{1}{n}\res
\left((1+u)^{n}\left((-\frac{1}{u})^n-1+n\frac{u+1}{u}\right),0\right)
\\&=\frac{1}{n}\left((-1)^n \res
\left(\frac{(1+u)^{n}}{u^n},0\right)+n\res \left(\frac{(1+u)^{n+1}}{u},0\right)\right)
\\&=\frac{1}{n}\left((-1)^n {n\choose n-1}+n\cdot 1\right)
\\&=1+(-1)^n,
\end{align*}
where $\res(f(u),0)$ means the residue of function $f(u)$ at $u=0$.
\end{proof}
\begin{remark}
Proposition \ref{pro:2} also follows immediately from the hypergeometric summation formula, by
\begin{align*}
\sum_{k=1}^{n-1}(-1)^kd_k&=\sum_{k=1}^{n-1}(-1)^{k-1}\frac{{n-1\choose k}}{k+1}{n+k+1\choose k}
=\frac{1}{n}\left(n-\sum_{i=1}^{n-1}{n\choose n-k-1}{-n-2\choose k}\right)
\\&=\frac{1}{n}\left(n-{-2\choose n-1}\right)=\frac{1}{n}(n+(-1)^nn)=1+(-1)^n.
\end{align*}
\end{remark}
\section{Acknowledgments}

The authors thank the anonymous referee for his/her careful reading and helpful comments.
The proofs of Lemma \ref{0} and Theorem \ref{1}, were effectively simplified by the referee. Moreover, he/she also gave the above remark.


\begin{thebibliography}{9}

\bibitem{Cayley}  A. Cayley, On the partition of a polygon, {\it Proc.
Lond. Math. Soc. (3)} {\bf 22} (1890), 237--262.

\bibitem{Przy} J. H. Przytycki and A. S. Sikora, Polygon dissections
and Euler, Fuss, Kirkman, and Cayley numbers, {\it J. Combin. Theory
Ser. A} {\bf 92} (2000), 68--76.

\bibitem{Michael} M. S. Floater and T. Lyche, Divided differences of
inverse functions and partitions of a convex polygon, {\it Math. Comp.}
{\bf 77} (2008), 2295--2308.

\bibitem{Lee} C. W. Lee, The associahedron and triangulations of the
$n$-gon, {\it European J. Combin.} {\bf 10} (1989), 551--560.

\bibitem{Shephard} G. C. Shephard, A polygon problem, {\it Amer. Math.
Monthly} {\bf 102} (1995), 505--507.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 51E12; Secondary 05A15, 13N15, 16W25.

\noindent \emph{Keywords: } 
polygon, diagonal, combinatorial enumeration, derivation, generating function.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000108}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 9 2014; 
revised versions received  April 26 2014; February 4 2015; March 14 2015; July 29 2015; August 6 2015.
Published in {\it Journal of Integer Sequences}, August 18 2015.

\bigskip
\hrule
\bigskip

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


\end{document}