Nesta dissertação, estudaremos fórmulas expressando números de Fibonacci como somas sobre composições, onde a soma se estende sobre todas as composições a1; a2; ... ; ak de n1 para um k qualquer. Daremos uma explicação sistemática de tais fórmulas usando monoides livres. O número de composições de nem partes 1 e 2 e o (n+1)- ésimo n umero de Fibonacci Fn+1, e essas composições estão associadas a um monoide livre. Veremos algumas fórmulas surgindo a partir de submonoides livres desse monoide livre. Alternativamente, e sempre que possível, tentaremos interpretar combinatorialmente os resultados tratados aqui. / In this dissertation, we study formulas expressing Fibonacci numbers as sums over compositions, where the sums are over all compositions a1; a2; ..., ak of n1 for any k. We will give a systematic explanation of such formulas using free monoids. The number of compositions of n with parts 1 and 2 is the (n + 1)th Fibonacci number Fn+1, and these compositions form a free monoid. We will see some formulas coming from free submonoids of this free monoid. Alternatively, and whenever possible, we try to interpret combinatorially such results.

Nesta dissertação, estudaremos fórmulas expressando números de Fibonacci como somas sobre composições, onde a soma se estende sobre todas as composições a1; a2; ... ; ak de n1 para um k qualquer. Daremos uma explicação sistemática de tais fórmulas usando monoides livres. O número de composições de nem partes 1 e 2 e o (n+1)- ésimo n umero de Fibonacci Fn+1, e essas composições estão associadas a um monoide livre. Veremos algumas fórmulas surgindo a partir de submonoides livres desse monoide livre. Alternativamente, e sempre que possível, tentaremos interpretar combinatorialmente os resultados tratados aqui. / In this dissertation, we study formulas expressing Fibonacci numbers as sums over compositions, where the sums are over all compositions a1; a2; ..., ak of n1 for any k. We will give a systematic explanation of such formulas using free monoids. The number of compositions of n with parts 1 and 2 is the (n + 1)th Fibonacci number Fn+1, and these compositions form a free monoid. We will see some formulas coming from free submonoids of this free monoid. Alternatively, and whenever possible, we try to interpret combinatorially such results.

Nesta dissertação, estudaremos fórmulas expressando números de Fibonacci como somas sobre composições, onde a soma se estende sobre todas as composições a1; a2; ... ; ak de n1 para um k qualquer. Daremos uma explicação sistemática de tais fórmulas usando monoides livres. O número de composições de nem partes 1 e 2 e o (n+1)- ésimo n umero de Fibonacci Fn+1, e essas composições estão associadas a um monoide livre. Veremos algumas fórmulas surgindo a partir de submonoides livres desse monoide livre. Alternativamente, e sempre que possível, tentaremos interpretar combinatorialmente os resultados tratados aqui. / In this dissertation, we study formulas expressing Fibonacci numbers as sums over compositions, where the sums are over all compositions a1; a2; ..., ak of n1 for any k. We will give a systematic explanation of such formulas using free monoids. The number of compositions of n with parts 1 and 2 is the (n + 1)th Fibonacci number Fn+1, and these compositions form a free monoid. We will see some formulas coming from free submonoids of this free monoid. Alternatively, and whenever possible, we try to interpret combinatorially such results.

En aquest treball, estudiarem diferents exemples de construccions d'anells i de monoides. En cada cas hem intentat fer notables les idees en la construcció per generadors i relacions. Una eina que utilitzarem bastant per a trobar formes normals a partir de presentacions de monoides és el Lema del Diamant [15, Theorem I.4.9]. En altres casos, no obtenim formes normals d'elements pròpiament dites, però podem aconseguir expressions per als elements que no són úniques però si conserven certes propietats. En altres casos, ens és molt útil de?nir funcions sobre els generadors d'un anell per poder treballar amb l'estructura graduada de l'anell i les components homogènies dels elements. Els exemples que tractarem, seran anells i monoides amb condicions de cadena. Tractar les condicions de cadena amb generadors i relacions ens planteja la di?cultat de que generalment ens calen una quantitat in?nita d'aquests. Això fa que l'exemple vingui presentat per molts generadors i moltes relacions.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-19T15:51:20Z No. of bitstreams: 2 Dissertação - Laredo Rennan Pereira Santos - 2015.pdf: 970933 bytes, checksum: 6b8836c42db993ababe18805a5857373 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-19T15:54:12Z (GMT) No. of bitstreams: 2 Dissertação - Laredo Rennan Pereira Santos - 2015.pdf: 970933 bytes, checksum: 6b8836c42db993ababe18805a5857373 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-05-19T15:54:12Z (GMT). No. of bitstreams: 2 Dissertação - Laredo Rennan Pereira Santos - 2015.pdf: 970933 bytes, checksum: 6b8836c42db993ababe18805a5857373 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-02-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work we consider monoid presentations MonhX,Ri, with set of generators X and relations R, defining groups and monoids as equivalence classes of words over X, in relation to a congruence generated by R. Taking R as a rewriting system with respect to an linear ordering of X , the set of words over X, we can apply some rewriting strategies in its laws. We use a version of the Knuth-Bendix method in R to find a confluent rewriting system equivalent to original, when such finite system exist. This new set of relations, denoted by RC(X, R), allows that in MonhX,Ri any element be defined by a unique irreducible word with respect to RC(X, R). We exhibit several examples of the execution of the Knuth-Bendix method from the functions of KBMAG package of the GAP system. Lastly, we set up a sufficient condition so that certain monoid presentations for polycyclic groups be confluent. / Neste trabalho, consideramos apresentações monoidais MonhX,Ri, com conjunto de geradores X e de relações R, definindo grupos e monoides como classes de equivalência de palavras sobre X, em relação a uma congruência gerada por R. Tomando R como um sistema de reescrita com respeito à uma ordenação linear de X , o conjunto de palavras sobre X, podemos aplicar algumas estratégias de reescrita em suas leis. Usamos uma versão do método de Knuth-Bendix em R para encontrar um sistema de reescrita confluente que seja equivalente ao original, quando um tal sistema finito existe. Este novo conjunto de relações, denotado por RC(X, R), permite que em MonhX,Ri qualquer elemento seja definido por uma única palavra irredutível com respeito a RC(X, R). Exibimos diversos exemplos da execução do método de Knuth-Bendix a partir das funções do pacote KBMAG do sistema GAP. Por fim, estabelecemos uma condição suficiente para que certas apresentações monoidais para grupos policíclicos sejam confluentes.