Composições de Fibonacci e monoides livres

Abstract

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.