Added to Favorites

Popular Searches

Definitions

Nearby Words

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## Worked example B: Fibonacci numbers

## 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 $m$ of a set $E$ according to several parameters $r\_0(m),\; ,\; r\_1(m),\; ,\; ldots$ through the correspondence $m\; leftrightarrow\; w\_0^\{r\_0(m)\}\; w\_1^\{r\_1(m)\}\; cdots$. Here the variables of the generating function are $w\_0,\; ,\; w\_1,\; ,\; ldots$ and the generating function $f$ is
### Computing the answer

### A simple example

### Special case

## Worked example D: bivariate generating functions and digit sums

### Alternate explicit formula

### Alternate recurrence

### Verification

## Worked Example E: pseudo-roman numerals

## External links

*
*

- $G(1;x)=sum\_\{n=0\}^\{infty\}\; x^n\; =\; frac\{1\}\{1-x\}$

and replacing $x$ with $2x$, we obtain

- $G(1;2x)=frac\{1\}\{1-2x\}\; =\; 1+(2x)+(2x)^2+cdots+(2x)^n+cdots=G(2^n;x).$

Consider the problem of finding a closed formula for the Fibonacci numbers 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:

- $$

& = & & & & & F_2x^2 & + & cdots & + & F_ix^i & +& cdotsend{array}

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 of partial fraction decomposition yields

- $$

These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula

- $$

- $f(w\_0,\; w\_1,\; ldots)\; =\; sum\_\{min\; E\}\; w\_0^\{r\_0(m)\}\; w\_1^\{r\_1(m)\}\; cdots$

- $c\; =\; [w\_0^\{r\_0\}\; w\_1^\{r\_1\}\; cdots]\; f(w\_0,\; w\_1,\; ldots),$

The example we will study concerns a undirected graph $G\; =\; (V,\; E)$ whose vertices $V$ correspond to words of length $t$ over an alphabet $Sigma$ containing exactly $l$ letters, i.e.

- $Sigma=\{a\_1,a\_2,\; ldots,a\_l\}$

Furthermore we are given a set of functions $p\_k:\; Sigma\; rightarrow\; 2^Sigma$ that determine which of the $l^t,$ possible vertices occur in the graph, and what the edges are. More precisely, $p\_k(lambda)$ specifies a set of possible replacements for $lambda$, if it occurs at position $k$. In that case, $lambda$ may be changed to any letter occurring in $p\_k(lambda)$, yielding an adjacent word, i.e., vertex. Edges exist between adjacent words, but only if they differ in exactly one position. Intuitively speaking, the $p\_k$ provide the neighbors of a particular letter occurring at position $k$, and the neighbors of a word are those words that may be obtained by selecting one position and replacing the letter $lambda$ at that position by one of its neighbors, i.e. an element of $p\_k(lambda)$. We are guaranteed that the $p\_k$ are such that adjacency always works both ways, i.e. if $mu\; in\; p\_k(lambda)$, then $lambda\; in\; p\_k(mu)$. Words containing letters at positions where they have no neighbors i.e. where $|p\_k(lambda)|=0$ 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 $V$, and we need to classify the vertices $m$ according the number of letters having $1,\; 2,\; 3\; ldots$ neighbors, so that

- $m\; leftrightarrow\; w\_1^\{r\_1(m)\}\; w\_2^\{r\_2(m)\}\; cdots,$

- $left(sum\_\{j=1\}^\{l-1\}$

This is because $w\_q^\{r\_q\}$ indicates the presence of $r\_q$ letters having $q$ neighbors in $m$, which contribute $q\; ,\; r\_q$ edges but

- $q\; ,\; r\_q\; =\; q\; ,\; left(frac\{d\}\{d\; w\_q\}\; w\_q^\{r\_q\}\; right)\_\{w\_q=1\}.$

This process will count edges twice (once at each endpoint), finally giving the formula for the number $T$ of edges

- $T\; =\; frac\{1\}\{2\}$

It remains to find $f(w\_1,\; ldots,\; w\_\{l-1\})$. With this in mind we introduce the quantities $v\_k(q)$, the number of letters at position $k$ having $q$ neighbors, i.e.

- $v\_k(q)\; =\; [z^q]\; sum\_\{lambdainSigma\}\; z^$
>.

- $L\_k\; =\; l\; -\; v\_k(0).$

Then the generating function $f$ is given by

- $f(w\_1,\; ldots,\; w\_\{l-1\})\; =\; prod\_\{k=0\}^\{t-1\}\; sum\_\{q=1\}^\{l-1\}\; v\_k(q)\; w\_q.$

It happens that $T$ can be computed explicitly, giving a simple and useful formula. This computation is based on the observation that

- $left(frac\{d\}\{d\; w\_j\}$

- $$

- $prod\_\{k=0\}^\{t-1\}\; L\_k\; sum\_\{k=0\}^\{t-1\}\; frac\{v\_k(j)\}\{L\_k\},$

- $T\; =\; frac\{1\}\{2\}$

Let $Sigma=\{0,1,2\}$, so that $l=3$, and consider words (vertices) consisting of two letters, i.e. $t=2$. The set of neighbor functions $p\_k$ is given by

- $p\_0(0)=\{1\},\; ,\; p\_0(1)=\{0,2\},\; ,\; p\_0(2)=\{1\}$

- $(w\_1\; +\; w\_2\; +\; w\_1)\; (w\_1\; +\; w\_1)\; =$

- $frac\{1\}\{2\}$

- $frac\{1\}\{2\}$

Indeed, these edges are

- $$

The result matches what we obtain by substituting into the formula. We have $v\_0(1)\; =\; 2,\; ,\; v\_0(2)=1$ and $v\_1(1)\; =\; 2,$, and $L\_0\; =\; 3$ and $L\_1\; =\; 2,$ giving

- $frac\{1\}\{2\}$

There is an important special case that yields a simpler formula for $T$. This is the case of there not being any "inert" letters, i.e. all letters have neighbors or $v\_k(0)=0$ at all positions, which implies that $L\_k=l$ for all $k$. The simplified formula becomes

- $T\; =\; frac\{1\}\{2\}$

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 $0$ and $l-1$), and the remaining letters have two neighbors. Substitution then yields

- $T\; =\; frac\{1\}\{2\}$

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.

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 functions, 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 $0$ to $10^\{2n\}-1$, where those integers that have fewer than $2n$ digits are padded with zeros on the left, so that all of them may be considered to have $2n$ digits. E.g. for $n=3$ the range goes from $000000$ to $999999$. We will use bivariate generating functions to answer the following question: what is the sum of those integers in $[0,\; 10^\{2n\}-1]$ whose first n digits sum to the same value as the last n digits, i.e. the digit 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 $n=3$, 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 $n$ (take $n=20$, for example).

We let $E\_n$ denote the desired sum, and introduce $g\_\{n,\; k\}$, which gives the number of integers n digits long (left-padding with zeros as before to obtain $10^n$ values) whose digits sum to k, and $s\_\{n,\; k\}$, which is the sum of the integers n digits long whose digits sum to k. The key observation is to note that

- $E\_n\; =\; sum\_\{k=0\}^\{9\; n\}\; (10^n+1)\; s\_\{n,\; k\}\; ,\; g\_\{n,\; k\}.$

- $F\_n\; =\; sum\_\{k=0\}^\{9\; n\}\; g\_\{n,\; k\}^2.$

We now introduce the following two bivariate generating functions:

- $G(z,\; u)\; =\; sum\_\{n\; ge\; 1,\; ,k\; ge\; 0\}\; g\_\{n,\; k\}\; u^k\; z^n$

- $V(u)\; =\; sum\_\{r=0\}^9\; u^r$

- $G(z,\; u)\; =\; sum\_\{n\; ge\; 1\}\; V(u)^n\; z^n\; =$

The next key observation is that for $n>1,$,

- $s\_\{n,\; k\}\; =\; sum\_\{r=0\}^9\; (10\; s\_\{n-1,\; k-r\}\; +\; g\_\{n-1,\; k-r\}\; r).$

We now prepare to reconstitute $S(z,\; u)$ by summing the above recurrence over $n>1,,\; kge\; 0$. The term for $[z^1]\; S(z,\; u),$, i.e. $n=1$, 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

- $sum\_\{k\; ge\; 0\}\; s\_\{1,\; k\}\; u^k\; z\; =\; sum\_\{r=0\}^9\; r\; u^r\; z\; =\; W(u)\; z.$

Adding everything, we find

- $S(z,\; u)\; =\; z\; W(u)\; +\; 10z\; V(u)\; S(z,\; u)\; +\; z\; W(u)\; G(z,\; u),$

- $$

- $$

Recall our earlier formula, which we may re-write as

- $E\_n\; =\; sum\_\{k=0\}^\{9\; n\}\; (10^n+1)\; [z^n\; u^k]\; S(z,\; u)\; ,\; [z^n\; u^k]\; G(z,\; u).$

1 4952 33496653 276259723744 2408014975919855 2162288199783771180. ...17 118563389850055864311605396948349988143661014994413568839460305165018 1152519562390611910184391237357889998847480437609388089815608762642110019 11220331276785941253721721128171177999887796687232140587462782788718288220020 1093844474149520613133628019194480743399890615552585047938686637198080551925660.

An explicit formula for $E\_n$, 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 $S(z,\; u),$ and using the symmetry of $[z^n]\; G(z,\; u),$ to observe that

- $E\_n\; =\; (10^n+1)\; sum\_\{k=0\}^\{9\; n\}\; s\_\{n,\; k\}\; ,\; g\_\{n,\; 9n-k\},$

- $E\_n\; =\; (10^n+1)\; [u^\{9n\}]\; ([z^n]\; G(z,\; u)\; [z^n]\; S(z,\; u)).,$

- $[z^n]\; S(z,\; u)\; =$

- $E\_n\; =\; frac\{1\}\{9\}\; (100^n\; -\; 1)\; [u^\{9n\}]\; W(u)\; V(u)^\{2n-1\}.$

The astute reader will have observed that we obtained the recurrence for $s\_\{n,\; k\}$ by appending the digit r to a contributor to $s\_\{n-1,\; k-r\},$. Of course it is entirely possible to prepend r to such contributors, which yields the alternate recurrence

- $s\_\{n,\; k\}\; =\; sum\_\{r=0\}^9\; (10^\{n-1\}\; g\_\{n-1,\; k-r\}\; r\; +\; s\_\{n-1,\; k-r\}).$

- $S(z,\; u)\; =\; z\; W(u)\; +\; z\; W(u)\; G(10z,\; u)\; +\; z\; V(u)\; S(z,\; u),$

- $S(z,\; u)\; =\; z\; W(u)\; frac\{1\; +\; G(10z,\; u)\}\{1\; -\; z\; V(u)\}\; =$

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. $G(z,\; 1),$ is the generating function of the total count of n-digit nonnegative integers, where left-padding with zeros is used. Indeed we have

- $[z^n]\; G(z,\; 1)\; =\; [z^n]frac\{10z\}\{1-10z\}\; =\; 10^n,$

- $[z^n]\; S(z,\; 1)\; =\; [z^n]\; frac\{45\; z\}\{(1\; -\; 10z)(1-100z)\}\; =$

- $[z^n]\; S(z,\; 1)\; =\; frac\{1\}\{2\}\; 100^n\; -\; frac\{1\}\{2\}\; 10^n.$

- $sum\_\{k=0\}^\{10^n-1\}\; k\; =\; frac\{1\}\{2\}\; (10^n\; -\; 1)\; 10^n.$

Additional material concerning this example, as well as a snapshot of how it evolved, can be found among the external links.

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

- $Sigma\; =\; left\{\; I,\; V,\; X\; right\}$

We use the following ordinary generating function to answer this question:

- $G(z,\; u)\; =\; sum\_\{nge\; 1,\; ;\; kge\; 1\}\; u^k\; z^n$

- $$

Summing the recurrence over n we find

- $$

- $$

- $$

The expected value E(n) of a word of weight n is given by the formula

- $E(n)\; =$

Start with the denominator. We have

- $left.\; G(z,\; u)\; right|\_\{u=1\}\; =$

- $frac\{2\}\{3\}\; 2^n\; +\; frac\{1\}\{3\}\; (-1)^n.$

Similarly,

- $left.\; frac\{operatorname\{d\}\}\{operatorname\{d\}u\}\; G(z,\; u)\; right|\_\{u=1\}\; =$

- $$

- $$

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 $3/5\; n$ digits/letters whose average value is $17/3$, giving an approximate expected value of $17/5$, 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.

- Generating Functions, Power Indices and Coin Change at cut-the-knot
- Generatingfunctionology (PDF)
- Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
- Frederick Lecue; Riedel, Marko,
*et al.**,**Permutation**, Les-Mathematiques.net, in French, title somewhat misleading.* - León-Sotelo, José H. Nieto, Marko Riedel, et al., Alfa-barras, newsgroup es.ciencia.matematicas

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday June 19, 2008 at 19:59:21 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday June 19, 2008 at 19:59:21 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.