Generating Functions
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
- PDF / 323,473 Bytes
- 16 Pages / 477 x 684 pts Page_size
- 98 Downloads / 238 Views
Generating Functions
6.1
Basic Properties
Example 6.1.1 (Great Britain 2007) In Hexagonia, there are six cities connected by railways in such a way that between every two cities there is a direct railway. On Sundays, some railways close for repairs. The train company guarantees that passengers will be able to get from any city to any other city (it may not be in a direct way) at any time. In how many ways can the company close railways so that this promise is kept? Solution In graph theory language, we want to count the number of connected graphs that use six distinguishable given vertices. To do this counting we consider the problem with n vertices and call f (n) the number we want. n Note that the total number of graphs with n vertices is 2(2) . Let us count these graphs in a different way. Let v be any vertex. If the connected component in which v is has k vertices, there are n−1 k−1 ways to choose the other k − 1 vertices of that component. With this, n−k there are f (k) ways to put the edges of that component and 2( 2 ) ways to put edges in the rest of the graph. We obtain n
2( 2 ) =
n n−k n−1 f (k) · 2( 2 ) . k−1 k=1
This is a recursive formula. It can be used to compute f (6). First we have that f (1) = f (2) = 1. Using the formula for n = 3 to find f (3) gives f (3) = 4. With the same idea, f (4) = 28, f (5) = 728 and f (6) = 26704. However, since the company has to close at least one railway, the number we wanted is 26703 (eliminating the complete graph with 6 vertices). Many times in combinatorics problems we find sequences of numbers and only recursive equations to work with them. Generating functions are a tool that allows P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_6, © Springer Basel 2013
77
78
6
Generating Functions
us to work efficiently with these equations. They are very useful to find closed-form formulas, i.e., formulas that do not depend on previous terms of the sequence. What we do is to assign to each sequence a function in the following way: (a0 , a1 , a2 , a3 , . . .) ←→ f (x) = a0 + a1 x + a2 x 2 + a3 x 3 + · · · . The function f (x) is called the generating function of the sequence (a0 , a1 , a2 , . . .) and represents this sequence. a0 is called the independent term of f (x). We have to note that f (x) is, at this point only, a way to refer to the sequence, so we are not interested in evaluating it at some point. When can generating functions be evaluated at a point will be explained in Sect. 6.5. We can sum and multiply generating functions. Given two functions f (x) and g(x) associated to the sequences (a0 , a1 , a2 , . . .) and (b0 , b1 , b2 , . . .), respectively, the sum and product are defined by (f + g)(x) = f (x) + g(x) = (a0 + b0 ) + (a1 + b1 )x + (a2 + b2 )x 2 + · · · , (6.1) (fg)(x) = f (x)g(x) = (a0 b0 ) + (a0 b1 + a1 b0 )x + (a0 b2 + a1 b1 + a2 b0 )x 2 + · · · . (6.2) In the product, the coefficient of x k is ak b0 +ak−1 b1 +ak−2 b2 +· · ·+a1 bk−1 +a0 bk . With these rules, generating functions behave like infini
Data Loading...