Técnicas de contagem: do Princípio Fundamental da Contagem às Funções Geradoras

Abstract

In the first chapter, a historical report of the studied subject is made, so that it is possible to locate yourself in time and have knowledge of the main characters involved, and then, at the end, the most basic counting techniques begin to be worked on, giving the foundations for all the rest of the text. In the second chapter, counting techniques resulting from the initials begin to be demonstrated and developed, gradually, as in a sequence of deductive reasoning, all of which are motivated through examples and practical situations, starting from the Fundamental Counting Principle to techniques more complex ones involving the Principle of Reflection, the Catalan Numbers, Dyck paths and the Chung-Feller theorem. Continuing, the third chapter explores the Pascal Triangle with all its main associated theorems. Binomial numbers are defined and extended to negative and even rational values, which will have great consequences in the rest of the text and even for the sum calculations, which are beginning to be developed in the same chapter. In chapter number four, the concepts of developing a binomial are worked out and expanded, as in a Leibniz polynomial. And, going further, the Generating Functions and the technique of hunting coefficients are introduced, now having a more prominent position in the text because it is a powerful tool in the resolution of problems hitherto not supported by the previous methods. In the sequence, there could be no lack of recurrences, a subject widely developed in the fifth chapter, in which not only the resolution techniques are formally demonstrated, but also a range of applications and cases in the history of Combinatorial Analysis are contextualized and resolved through the methods shown. Finally, in chapter six, all the counting techniques and methods of solving previous counting problems culminate. Permeating the recurrence relations, added to the techniques previously demonstrated, the Generating Functions are able to solve advanced and complex counting problems, such as partitions and triangulations.