%% 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{ }{ }