- Examples of generating functions
The following examples are in the spirit of
George Pólya , who advocated learning mathematics by doing and re-capitulating as many examples and proofs as possible. The purpose of this article is to present common tricks of the trade in context, so that the reader may incorporate them into his knowledge.Worked example A: basics
New generating functions can be created by extending simpler generating functions. For example, starting with
:
and replacing with , we obtain
:
Worked example B: Fibonacci numbers
Consider the problem of finding a closed formula for the
Fibonacci number s "F""n" defined by "F"0 = 0, "F"1 = 1, and "F""n" = "F""n"−1 + "F""n"−2 for "n" ≥ 2. We form the ordinary generating function:
for this sequence. The generating function for the sequence ("F""n"−1) is "xf" and that of ("F""n"−2) is "x"2"f". From the recurrence relation, we therefore see that the power series "xf" + "x"2"f" agrees with "f" except for the first two coefficients:
:
Taking these into account, we find that
:
(This is the crucial step; recurrence relations can almost always be translated into equations for the generating functions.) Solving this equation for "f", we get
:
The denominator can be factored using the
golden ratio φ1 = (1 + √5)/2 and φ2 = (1 − √5)/2, and the technique ofpartial fraction decomposition yields:
These two formal power series are known explicitly because they are
geometric series ; comparing coefficients, we find the explicit formula:
Worked example C: edges in an undirected graph
The focus of the example is the use of generating functions in several variables to achieve the goal of classifying the elements of a set according to several parameters through the correspondence . Here the variables of the generating function are and the generating function is:so that the number of elements of that correspond to the tuple of parameters is given by:where we have used the coefficient-extraction operator for
formal power series .The example we will study concerns a
undirected graph whose vertices correspond to words of length over an alphabet containing exactly letters, i.e.:In the following we will use the numbers from to in place of the letters to keep the notation simple.Furthermore we are given a set of functions that determine which of the possible vertices occur in the graph, and what the edges are. More precisely, specifies a set of possible replacements for , if it occurs at position . In that case, may be changed to any letter occurring in , yielding an adjacent word, i.e., vertex. Edges exist between adjacent words, but only "if they differ in exactly one position." Intuitively speaking, the provide the neighbors of a particular letter occurring at position , and the neighbors of a word are those words that may be obtained by selecting one position and replacing the letter at that position by one of its neighbors, i.e. an element of . We are guaranteed that the are such that adjacency always works both ways, i.e. if , then . Words containing letters at positions where they have no neighbors i.e. where are omitted from the set of vertices. The question we seek to answer is, how many edges does this graph contain?
Here the set whose elements we seek to enumerate and classify is the set of vertices , and we need to classify the vertices according the number of letters having neighbors, so that:with the number of letters having one neighbor at their position, the number of letters having two neighbors at their position, etc.,because then the number of edges originating at is given by:
This is because indicates the presence of letters having neighbors in , which contribute edges but:
This process will count edges twice (once at each endpoint), finally giving the formula for the number of edges:
It remains to find . With this in mind we introduce the quantities, the number of letters at position having neighbors, i.e.:We will also need , the number of letters actually occurring at position , i.e.:(Recall that letters having no neighbors do not contribute to the set of possible vertices.)
Then the generating function is given by:
Computing the answer
It happens that can be computed explicitly, giving a simple and useful formula. This computation is based on the observation that:evaluates to:which simplifies to:and yields:
A simple example
Let , so that , and consider words (vertices) consisting of two letters, i.e. . The set of neighbor functions is given by:The generating function becomes:Carrying out the differentiation we find the following expression for ::or:so we may expect seven edges.
Indeed, these edges are:The graph is shown below.
The result matches what we obtain by substituting into the formula. We have and , and and giving:
pecial case
There is an important special case that yields a simpler formula for . This is the case of there not being any "inert" letters, i.e. all letters have neighbors or at all positions, which implies that for all . The simplified formula becomes:
Suppose, for example, that all letters are adjacent to those differing by one from their numerical value, independent of their position. Hence there are two letters having one neighbor (namely and ), and the remaining letters have two neighbors. Substitution then yields:
This example is from "Les-Mathematiques.net". Variations on this problem, including a considerable amount of additional material, can be found among the external links.
Worked example D: bivariate generating functions and digit sums
Ordinary generating functions are not limited to representing sequences that depend only on a single parameter. More parameters are possible, e.g. two parameters, or more, as seen in the previous example. It is also possible to mix types of generating functions, as in bivariate
probability generating function s, where an ordinary generating function generates an exponential one. These types of generating functions are often referred to as "super generating functions". Here we show an example of how to work with bivariate generating functions. Let "n" be a natural number and consider the integers from to , where those integers that have fewer than digits are padded with zeros on the left, so that all of them may be considered to have digits. E.g. for the range goes from to . We will use bivariate generating functions to answer the following question: what is the sum of those integers in whose first "n" digits sum to the same value as the last "n" digits, i.e. thedigit sum of the first half is equal to the digit sum of the second half. (The term "digital sum" is also used for digit sums.) We call these integers "balanced". E.g. the integer 124511 would contribute to the sum for , because 1+2+4=7=5+1+1. The value that it would contribute is simply 124511. It is certainly impossible to compute this sum by direct enumeration for large (take , for example).We let denote the desired sum, and introduce , which gives the number of integers "n" digits long (left-padding with zeros as before to obtain values) whose digits sum to "k", and , which is the sum of the integers "n" digits long whose digits sum to "k". The key observation is to note that:To see this, fix "k", the digit sum, and consider the set of balanced integers of length , the digit sum of the first and second half of which is "k". This set of integers is created by pairing any integer of length "n" and digit sum "k" with any other, so any particular value occurs times in the first half (multiplied by ), and times in the second half. Adding all of these integers yields The number of summands that contribute to is given by:
We now introduce the following two bivariate generating functions::(We require that and for , because is the maximum digit sum possible.)We will also require two auxiliary functions to keep the notation simple::Now from the definition of it follows immediately that:This is because the terms of represent the process of choosing one decimal digit for the first position on the left, one for the second, and so on. The exponents are added so that the term occurs every time the digits sum to "k".
The next key observation is that for ,:This simply says that the integers that contribute to can be obtained from those that contribute to , where "r" is a decimal digit, by shifting the latter one position to the left (multiplication by ten) and appending "r" (recall that there are integers that contribute to )
We now prepare to reconstitute by summing the above recurrence over . The term for , i.e. , will be missing from the sum on the left, so we compute it and add it in. (In what follows, we will use the coefficient-extraction operator for
formal power series .) We have:Adding everything, we find:and hence:or:which is a simple rational generating function.
Recall our earlier formula, which we may re-write as:We may now compute the , since we have closed forms for and This yields the following table for and :
1 495 2 3349665 3 27625972374 4 240801497591985 5 2162288199783771180 . ... 17 1185633898500558643116053969483499881436610149944135688394603051650 18 11525195623906119101843912373578899988474804376093880898156087626421100 19 112203312767859412537217211281711779998877966872321405874627827887182882200 20 1093844474149520613133628019194480743399890615552585047938686637198080551925660.Alternate explicit formula
An explicit formula for , which however is not as amenable to symbolic computation as the previous form, can be obtained by expanding the geometric series in the
partial fraction decomposition of and using the symmetry of to observe that:which gives:But:so that:Alternate recurrence
The astute reader will have observed that we obtained the recurrence for by appending the digit "r" to a contributor to . Of course it is entirely possible to prepend "r" to such contributors, which yields the alternate recurrence:Summing as before, we find:Solving this for produces, as it ought to, the same solution as before::
Verification
When working with generating functions, it is important to verify that they yield sensible values. By setting variables in multivariate ordinary generating functions to one, we obtain generating functions of superclasses of combinatorial structures or quantities, since one or more of the parameters disappear. E.g. is the generating function of the total count of "n"-digit nonnegative integers, where left-padding with zeros is used. Indeed we have:which is correct. Similarly, is the generating function of the sum of all "n"-digit nonnegative integers, again with left-padding by zeros. We have:Hence:This too is the correct value, since:
Additional material concerning this example, as well as a snapshot of how it evolved, can be found among the external links.
Worked Example E: pseudo-roman numerals
Consider a number system created by using a subset of the rules and letters of
roman numerals . Specifically, we have the letters I, V and X with values 1, 5, and 10, any sequence of which is considered a number, whose value is the sum of the individual digits. In other words, we have an alphabet:and consider elements of Every letter has a weight that corresponds to the number of bars required to draw that letter. We consider that "I" has weight one and "X" and "V" both have weight two, consisting of two crossed bars in the first case, and two adjacent bars with a common base point in the second. The weight of a word, i.e. number, is the sum of the weights of the constituent digits. E.g. the value of "XXVI" is 26 and its weight is "2 + 2 + 2 + 1 = 7." We now ask the following question: what is the expected value of the value of a number having weight "n"?We use the following ordinary generating function to answer this question::where the monomial represents a word of "n" bars (weight "n") and having value "k". Let By definition, we have:
Summing the recurrence over "n" we find:which gives the following equation for ::Solving for "G", we obtain:
The expected value "E(n)" of a word of weight "n" is given by the formula:where the numerator is the sum of the values of all words having weight "n", and the denominator is the number of such words.
Start with the denominator. We have:,so the number of words is:
Similarly,:so the sum of their values is:The conclusion is that the expected value is:
The expected value of a word/number is linear in the number of bars/weight of the number.The linearity is evident in the fact that the contribution of a digit is a constant value and independent of its position. Reasoning more carefully, we see that a word of weight "n" contains on average digits/letters whose average value is , giving an approximate expected value of , which is not quite exact because the digits are not equiprobable.
Additional material concerning this example, as well as a snapshot of how it evolved, can be found among the external links.
External links
* [http://www.cut-the-knot.org/ctk/GeneratingFunctions.shtml Generating Functions, Power Indices and Coin Change] at
cut-the-knot
* [http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf Generatingfunctionology (PDF)]
* Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, " [http://groups.google.com/group/es.ciencia.matematicas/browse_thread/thread/26328abc49e15dd9/88b7b522437223ce#88b7b522437223ce Suma de números equilibrados] , newsgroup es.ciencia.matematicas"
* Frederick Lecue; Riedel, Marko, et al., [http://les-mathematiques.u-strasbg.fr/phorum5/read.php?12,360025 Permutation] , "Les-Mathematiques.net", in French, title somewhat misleading.
* León-Sotelo, José H. Nieto, Marko Riedel, et al., " [http://groups.google.com/group/es.ciencia.matematicas/browse_thread/thread/f38395c3823cde0d#802a4ff297f52f10 Alfa-barras] , newsgroup es.ciencia.matematicas"
Wikimedia Foundation. 2010.