Generating Functions

Pablo Soberón
Additional contact information
Pablo Soberón: University College London, Department of Mathematics

Chapter 6 in Problem-Solving Methods in Combinatorics, 2013, pp 77-92 from Springer

Abstract: Abstract This chapter contains an introduction to generating functions. We present generating functions as a way to deal with recursive equations that appear in combinatorial problems. First, we define these functions and their basic properties, and give examples of many basic generating functions. Then, we show how they can be used to obtain a closed formula to the Fibonacci numbers, and how this technique extends to similar sequences. As a more complicated example, we show how to obtain a closed formula for the Catalan numbers. This is done both via generating functions and with a purely combinatorial approach. Then, we introduce the concept of the derivative, and how it can make manipulations of generating functions much easier. The last section explains why generating functions are called “functions”. Namely, we explain when it is possible to evaluate them at a point and when an actual function can be represented as a generating function. At the end of the chapter, we present 18 problems for the reader.

Keywords: Catalan Number; Fibonacci Numbers; Recursive Formula; Good Path; Infinite Polynomial (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-0348-0597-1_6

Ordering information: This item can be ordered from
http://www.springer.com/9783034805971

DOI: 10.1007/978-3-0348-0597-1_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().