%% Antes de processar este arquivo LaTeX (LaTeX2e) deve
%% verificar que o arquivo PORANDU.cls estah no mesmo
%% diretorio. O arquivo PORANDU.cls pode ser obtido do

\documentclass{PORANDUp}

\begin{document}

%% TÍTULO DO ARTIGO - pode ser separado em várias linhas usando-se \\
\title
    {Uma Interpretação Combinatória Para \\ Os Números de Catalan
     \thanks{Agradecimentos por auxílio;  apoiado pela Capes.}}

\criartitulo  % CRIA O CABEÇALHO FIXO DA REVISTA

\runningheads {PORANDU}{Matemática Aplicada/Teoria Analítica dos Números} % DEFINE-SE A ÁREA/SUBÁREA DO ARTIGO

\begin{abstract}
{\bf Resumo} o escopo desse trabalho é explorar a sequência
numérica, conhecida como números de Catalan através de uma abordagem
com o uso de  funções geradoras. Introduzir conceitos e aspectos
algébricos para algumas propriedades relacionadas a essas
sequências. Iremos explorar uma  interpretação combinatória por meio
do conceito de triangulações de um poligono convexo.


{\bf Palavras-chave}.  Função Geradora , Número de Catalan,
Triangulação.
\end{abstract}

\begin{abstract}
{\bf Abstract}. the scope of this work is to explore the sequence
numerical data, known as Catalan numbers through a with the use of
generating functions. Introduce concepts and aspects algebraic
properties for some properties related to these sequences. We will
explore a combinatorial interpretation through of the concept of
triangulations of a convex polygon.
\end{abstract}


\newsec{Introdução}  % INICIA-SE NOVA SEÇÃO

Os números de Catalan é uma sequência de números que surge em
diversas areas da matemática, entre essas estão a Geometria,
Álgebra, Análise e Combinatória, essa última é a que nos interessa e
será a fonte de estudo.  Em  \cite{PAK} descreve a trajetória dos
números de Catalan. Eugene Catalan (1814 - 1894) nasceu em Bruges,
na Bélgica e teve uma infância tranquila, aos dez anos tornou-se
aprendiz de joalheiro, mas desistiu da arte por não ter habilidade.
Anos mais tarde sua famíliamudou-se para Paris e seu pais começou a
trabalhar como arquiteto e levava seu filho Eugene para o trabalho,
essa experiência influenciou sua vida acadêmica e o início dos seus
estudos na Escola École Polytechnique. A vida acadêmica e
profissional de Eugene foi tumultuada por seu envolvimento político,
republicano e esquerdista, que quase acabou com seu futuro, mas
ainda assim tornou-se um grande especialista em Teoria dos Números e
Teoria Combinatória.\\

Em 1838 é atribuído a Eugene Catalan o nome da sequência dos Números
de Catalan, durante um estudo das sequências bem formadas entre
parênteses descobriu quase ao acaso a sequência de Catalan. Há três
matemáticos que merecem uma menção especial quando se trata
da descoberta e desenvolvimento do número de Catalan: Leonhard Euler,Eugene Charles Catalan e Sharabiin Myangat.\\

Nesse trabalho apresentamos uma fórmula para os números de Catalan
usando o conceito de funções geradoras, em seguida uma interpretação
para esses números fazendo uso da definição de triangulação de um
poligono convexo.



%********************************************************
\newsec{Definição e fórmula explicita para os números de Catalan}

\setcounter{equation}{0}


Os números de Catalan é uma sequência numérica  $1,2,5 ,14,42 \dots$
definida por um relação de recorrência não linear.

\begin{defi} Seja $n \in  \mathbb{N},$ definimos por $C_{n}$ o
número de Catalan de ordem $n$ pela seguinte relação de recorrência:
\label{cin}
\begin{equation} \label{cin.um}
  \left\{ \begin{array}{rcl}
     C_{0} & = & 1 \\ [1ex]
    C_{n}  & = &
             \displaystyle \sum_{j=0}^{n} C_{j}C_{n-j}, \mbox{ para } n>0
   \end{array} \right.
   \end{equation}
\end{defi}


Podemos reescrever ( \ref{cin.um} )da seguinte forma:\\



\begin{equation} \label{cin.um1}
  \left\{ \begin{array}{rcl}
     C_{0} & = & 1 \\ [1ex]
    C_{k}  & = &
             \displaystyle \sum_{j=0}^{k-1} C_{j}C_{k-1-j}, \mbox{ para } k>0
   \end{array} \right.
   \end{equation}




 Por meio da recorrência definida em ( \ref{cin.um1}) queremos  determinar uma fórmula explícita  para os números de Catalan. Para isso, considere a série de potências
$C(z)=\displaystyle\sum_{n=0}^{\infty}C_{n}z^{n}$, onde $C_n$ é o
$n$-ésimo de Catalan:

$$
C(z)=C_0+C_1x+C_2x^2+C_3x^3+ \dots =\sum_{n=0}^{\infty}C_nz^n
$$

Multiplicando por $z^n$ em ambos os lados de (\ref{cin.um1}) e
somando em $n$ com $n\geq 1$  e em seguida adicionando $C_{0}$ em
ambos lados da identidade temos:

$$
\sum_{n=1}^{\infty}C_nz^n+C_0 = \sum_{n=1}^{\infty}z^n
\sum_{j=0}^{n-1}C_jC_{n-1-j}+C_0.
$$

Utilizando o conceito de produto de series de potência obtemos:
$$
C(z)=\sum_{j=0}^{n-1}C_jz^j\sum_{n-1}^{\infty}z^{n-j-1}z+C_0;
$$
$$
C(z)=z\sum_{j=0}^{n-1}C_jz^j\sum_{n-1}^{\infty}z^{n-j-1}C_{n-1-j}+C_0.
$$

Dessa forma: $ C(z)=zC(z)\cdot C(z)+1,$ ou seja, $ C(z)=zC(z)^2+1.$
Resolvendo a equação quadrática $zC(z)^2-C(z)+1=0$ obtemos: $
C(z)=\dfrac{1\pm \sqrt{1-4z}}{2z} .$

Como
$$
\lim_{z \rightarrow 0+}\dfrac{1+\sqrt{1-4z}}{2z}=+\infty \quad
\mbox{e} \quad \lim_{z \rightarrow
0-}\dfrac{1+\sqrt{1-4z}}{2z}=-\infty
$$ e  $C(z)=C_0+C_1x+C_2x^2+C_3x^3+ \ldots,$ com $C(0)=C_0=1,$ então
$C(z)=\dfrac{1-\sqrt{1-4z}}{2z}.$ Dessa forma, concluímos que
\begin{prop}\label{PRC1}

A função ordinária para os números de Catalan é:

\begin{equation}\label{cin2}
C(z)=\dfrac{1-\sqrt{1-4z}}{2z}
\end{equation}

\end{prop}

Agora vamos determinar uma formula explícita para os números de
Catalan. Utilizando o teorema Binomial Generalizado, cujo resultado
segue de \cite{SANTOS}, dessa forma obtemos:
\\
$$
\sqrt{1-4z}=(1-4z)^{\frac{1}{2}}=1+\sum_{k=1}^{\infty}{\frac{1}{2}\choose
k}(-4z)^{k}=1+ \sum_{k=1}^{\infty}\dfrac{\frac{1}{2}\left(
\frac{1}{2}-1 \right)\ldots \left( \frac{1}{2}-k+1
\right)(-4z)^{k}}{k!}.
$$ e substituindo em ( \ref{cin2}) temos:
$$
C(z)=\dfrac{1-\sqrt{1-4z}}{2z}=
\frac{(1-(1-2z)^{\frac{1}{2}})}{2z}=\sum_{k=1}^{\infty}\dfrac{\dfrac{\frac{1}{2}
\left(\frac{1}{2}-1 \right) \ldots \left(\frac{1}{2}-k+1
\right)\left( -4z \right)^{k}}{k!}}{2z}=
$$

$$
=\sum_{k=1}^{\infty}\dfrac{\left(\frac{1}{2}-1 \right)
\left(\frac{1}{2}-2 \right)\ldots \left(\frac{1}{2}-k+1
\right)\left( -4z \right)^{k-1}}{k!}=
$$
$$
=\sum_{k=1}^{\infty}\dfrac{\left(\dfrac{1-2}{2} \right)
\left(\dfrac{1-4}{2} \right) \left(\dfrac{1-6}{2} \right)\ldots
\left(\dfrac{1-2k+2}{2} \right)\left( -4 \right)^{k-1} \left( z
\right)^{k-1}}{k!}=
$$
$$
=\sum_{k=1}^{\infty}\dfrac{\left(-\dfrac{1}{2} \right)
\left(-\dfrac{3}{2} \right) \left(-\dfrac{5}{2} \right)\ldots
\left(\dfrac{3-2k}{2} \right)\left( -4 \right)^{k-1} \left( z
\right)^{k-1}}{k!}=
$$
$$
=\sum_{k=1}^{\infty}\dfrac{\dfrac{1}{2} \cdot \dfrac{3}{2} \cdot
\dfrac{5}{2} \cdot \ldots \cdot \left(\dfrac{2k-3}{2} \right)\left(
-1 \right)^{k-1}\left( -4 \right)^{k-1} \left( z \right)^{k-1}}{k!}=
$$
$$
=\sum_{k=1}^{\infty}\dfrac{1}{2^{k-1}}\dfrac{1 \cdot 3 \cdot \ldots
\cdot (2k-3)(-1)^{k-1}(-1)^{k-1}(-4)^{k-1}(z)^{k-1}}{k!}=
$$

\begin{equation}\label{nin2}
=\sum_{k=1}^{\infty}2^{k-1}\dfrac{1 \cdot 3 \cdot \cdots \cdot
(2k-3)} {k!}(z)^{k-1}.
\end{equation}

O coeficiente de $z^{k}$ em  ( \ref{nin2} )  é:

$$
C_{k}=2^{k}\dfrac{1 \cdot 3 \ldots 2k-1}
{(k+1)!}=\dfrac{2^k}{(k+1)!}\dfrac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5
\ldots (2k-1)\cdot 2k} {2 \cdot 4 \cdot 6 \ldots 2k}=
$$
$$
=\dfrac{2^{k}}{(K+1)!}\dfrac{(2k)!}{(2 \cdot 1)(2 \cdot 2)(2 \cdot
3)\ldots (2 \cdot k)}=\dfrac{2^k}{(k+1)!}\dfrac{(2^k)!}{2^k \cdot 1
\cdot 2 \cdot 3 \ldots k}=
$$
$$ =\dfrac{(2^{k})!}{(k+1)!k!}=\dfrac{1}{k+1}\cdot
\dfrac{(2k)!}{k!k!}= \dfrac{1}{k+1}{2k \choose k} \qedhere
$$

Portanto temos o seguinte resultado:

\begin{teorema}
Seja $C_n$ o $n$-enésimo de Catalan e $n \in \mathbb{N}$, então

$$
C_n=\dfrac{1}{n+1}{2n\choose n}.
$$
\end{teorema}

%********************************************************
\newsec{Interpretações Combinatórias para os números de Catalan: Triangulações}

\setcounter{equation}{0}


Os números de Catalan possuem várias e maravilhosas aplicações além
de uma infinidade de interpretações combinatórias, Richard P.
Stanley, do Massachusetts Institute of Technology (MIT), reuniu ao
longo de sua vida acadêmica inúmeros problemas com os números de
Catalan e mais tarde escreveu o livro Enumerative Combinatorics vol.
2, com cerca de 66 problemas cuja solução é um número de Catalan.
Apresentaremos algumas dessas interpretações e começaremos por uma
interpretação geométrica para os números de Catalan.\\


Historicamente, matemáticos demonstram grande interesse em estudar
objetos com propriedade especiais, por exemplo, as triangulações de
um polígono convexo. Uma triangulação de um polígono convexo $P_{n}
$ de $n$ lados  é a decomposição de $P_{n}$ em triângulos por um
conjunto maximal de diagonais que não se cruzam. Ou seja, dado
$n\geq3,$ definimos por $T_{n}$ o número de triangulações válidas de
um poligono $P_{n},$ isto é aquelas obtidas por $n-3$ diagonais que
não se interceptam no seu interior.  No caso de $n=3$, temos um
triângulo e convencionamos $T_2=1$. Por inspeção podemos constatar
que há 2 maneiras de triangular um quadrilátero convexo e cinco
maneiras de triangular o pentágono convexo traçando diagonais que
não se cruzam. \vspace{2cm}

\begin{figure}[h!]
    \centering
        \includegraphics[scale=0.9]{marcia1.eps}
  \caption{ Triangulações de um poligono de $n$ lados, $n=3, 4, 5.$}
    \label{figura1}
\end{figure}

Os resultados que validamos agora segue de \cite{KOSHY}.
\begin{teorema} Para $n \geq 3$ a  sequência $T_{n}$ satisfaz $$T_{n}=\sum_{j=2}^{n-1}T_{j}T_{n-j+1}.$$
\end{teorema}
\begin{dem}  De fato, dado um poligono convexo de $n$ lados , vamos particionar o conjunto das triangulações de $P_{n}$ em triangulaçoes de poligonos cuja quantidade de lados
é menor do que $n.$ Para isso, seja $Q \in \{3,4, \dots, n\}$ Vamos
fixar o triângulo $12Q$ no poligono $P_{n}$ dividindo-o em dois
poligonos de lados menores, um poligono de $Q-1$ lados e outro de
$n-Q+2$ lados. Segue do principio multiplicativo que temos
$T_{Q-1}T_{n-Q+2}$ triangulações válidas de $P_{n}$ com o triângulo
$12Q$ fixo. Somando em $Q$ temos:


$$T_{n}=T_{2}T_{n-1} + \sum_{Q=4}^{n-1}T_{Q-1}T_{Q-1}T_{n-Q+2}+
T_{n-1}T_{2}= \sum_{j=2}^{n-1}T_{j}T_{n-j-1}.$$
 \end{dem}
Denotamos por $\vartheta_{n}$ o conjunto das triangulações de
$P_{n}.$ \newpage
 \begin{figure}[h!]
    \centering
        \includegraphics[scale=0.5]{tabela1.eps}
  \caption{ Ilustração da demonstração do Teorema (3.1) no caso $n=6.$}
    \label{figura2}
\end{figure}


\begin{teorema} Para $n \geq 4$ a  sequência $T_{n}$ satisfaz $$(n-3)T_{n}=\frac{n}{2}\sum_{j=3}^{n-1}T_{j}T_{n-j+1}.$$
\end{teorema}
\begin{dem}   De fato,  considere $Q \in \{3,4, \dots, n-1\}$  e uma diagonal $\overline{1Q}$ do poligono convexo $P_{n},$ que divide em dois outros poligonos convexos, sendo
um a direita com $Q$ lados e com $T_{Q}$ maneiras de triangular e
outro a esquerda com $n-Q+2$ lados com $T_{n-Q+2}$ maneiras de
triangular. Logo temos $T_{Q}T_{n-Q+2}$ triangulações válidas fixada
a diagonal  $\overline{1Q}$ e ao variar $Q$ obtemos um total de
triangulações válidas para diagonais que cruzem o vértice 1:
 $\displaystyle \sum_{Q=3}^{n-1}T_{Q}T_{n-Q+2}.$

 Somando os números de triangulações e variando o vértice de $1$ até
 $n$ teremos duplicidade feitas a partir das diagonais. Isso pelo
 fato de contarmos duas vezes as diagonais $\overline{1Q}$ e $\overline{Q1}.
 $ Portanto  $\displaystyle\frac{n}{2}\displaystyle
 \sum_{Q=3}^{n-1}T_{Q}T_{n-Q+2}$ é o número de triangulações
 válidas a partir de cada diagonal de $P_{n}.$ Esse número contém
 $n-3$ diagonais e cada triangulação utiliza $n-3$ diagonais, com
 isso finalizamos a demonstração do teorema: $$(n-3)T_{n}=\frac{n}{2}\sum_{j=3}^{n-1}T_{j}T_{n-j+1}.$$


 \end{dem}


\begin{teorema} Se $n$  inteiro, com $n \geq 0,$ então $C_{n}=T_{n+2}.$
\end{teorema}
\begin{dem}  Vamos definir a função $g$, cujo domínio é o conjunto dos inteiros não negativos $: \{x \in \mathbb{Z}, x\geq 0\}, $ e a lei de formação é:
$g(m)= \frac{T_{m+2}}{C_{m}}.$ Queremos provar que $g(m)=1,$ para
todo inteiro $m\geq 0.$ De fato, sabemos que $T_{2}=T_{3}=1, $
$C_{0}=C_{1}=1$ e $T_{4}=C_{4}=2.$ Logo $g(0)=g(1)=g(2)=1.$

Segue do Teorema (3.2)  que para $n\geq 4, $ $T_{n+1}= \displaystyle
\sum_{j=2}^{n}T_{j}T_{n-j+2},$ ou seja, $T_{n+1}= T_{2}T_{n} +
\displaystyle \sum_{j=3}^{n-1}T_{j}T_{n-j+2} + T_{n}T_{2}= $
$T_{n+1}= \displaystyle \sum_{j=3}^{n-1}T_{j}T_{n-j+2}+ 2T_{n}.$
Logo $T_{n+1}-2T_{n}=$ $T_{n+1}= \displaystyle
\sum_{j=3}^{n-1}T_{j}T_{n-j+2}.$ Segue do Teorema (3.3)
$displaystyle (n-3)T_{n}=\frac{n}{2}\sum_{j=3}^{n-1}T_{j}T_{n-j+1}.$
Dessa forma concluímos: $\displaystyle
(n-3)T_{n}=\frac{n}{2}(T_{n+1}-2T_{n}),$ ou seja,
$4nT_{n}-6T_{n}=nT_{n+1}.$ Portanto
\begin{equation}\label{cin3}
\frac{T_{n+1}}{T_{n}}=\frac{4n-6}{n} .\end{equation}

Podemos verificar que $C_{n-1}=\frac{4n-6}{n}C_{n-2},$ para $n\geq
2.$ Ou seja,
\begin{equation} \label{cin4}
\frac{C_{n-2}}{C_{n-2}}= \frac{n}{4n-6}.
\end{equation}
Portanto segue de ( \ref{cin3} ) e ( \ref{cin4} ) que :
$\displaystyle \frac{g(n-1)}{g(n-2)}=\frac{T_{n+1}}{C_{n-1}}
\frac{C_{n-2}}{T_{n}}=\frac{T_{n+1}}{T_{n}} \frac{C_{n-2}}{C_{n-1}}=
\frac{4n-6}{n}\frac{n}{4n-6}=1. $ Assim, para todo $n \geq 4,$
$g(n-1)=g(n-2).$ Como $g(3)=g(4)=1,$ então $g(m)=1$ para todo
inteiro $m\geq 0.$

 \end{dem}




\bibliographystyle{ieeetr}
\bibliography{porandu}

\end{document}
\newpage
$ \  \  $  \thispagestyle{myheadings}  \markboth{      }{   }
