Editing Generating function (section)

====Example: Spanning trees of fans and convolutions of convolutions====

A ''fan of order {{mvar|n}}'' is defined to be a graph on the vertices {{math|{0, 1, ..., ''n''}<nowiki/>}} with {{math|2''n'' − 1}} edges connected according to the following rules: Vertex 0 is connected by a single edge to each of the other {{mvar|n}} vertices, and vertex <math>k</math> is connected by a single edge to the next vertex {{math|''k'' + 1}} for all {{math|1 ≤ ''k'' < ''n''}}.<ref>{{harvnb|Graham|Knuth|Patashnik|1994|loc=Example 6 in §7.3}} for another method and the complete setup of this problem using generating functions. This more "convoluted" approach is given in Section 7.5 of the same reference.</ref> There is one fan of order one, three fans of order two, eight fans of order three, and so on. A [[spanning tree]] is a subgraph of a graph which contains all of the original vertices and which contains enough edges to make this subgraph connected, but not so many edges that there is a cycle in the subgraph. We ask how many spanning trees {{math|''f<sub>n</sub>''}} of a fan of order {{mvar|n}} are possible for each {{math|''n'' ≥ 1}}.

As an observation, we may approach the question by counting the number of ways to join adjacent sets of vertices. For example, when {{math|''n'' {{=}} 4}}, we have that {{math|''f''<sub>4</sub> {{=}} 4 + 3 · 1 + 2 · 2 + 1 · 3 + 2 · 1 · 1 + 1 · 2 · 1 + 1 · 1 · 2 + 1 · 1 · 1 · 1 {{=}} 21}}, which is a sum over the {{mvar|m}}-fold convolutions of the sequence {{math|''g<sub>n</sub>'' {{=}} ''n'' {{=}} [''z<sup>n</sup>''] {{sfrac|''z''|(1 − ''z'')<sup>2</sup>}}}} for {{math|''m'' ≔ 1, 2, 3, 4}}. More generally, we may write a formula for this sequence as
<math display="block">f_n = \sum_{m > 0} \sum_{\scriptstyle k_1+k_2+\cdots+k_m=n\atop\scriptstyle k_1, k_2, \ldots,k_m > 0} g_{k_1} g_{k_2} \cdots g_{k_m}\,, </math>
from which we see that the ordinary generating function for this sequence is given by the next sum of convolutions as
<math display="block">F(z) = G(z) + G(z)^2 + G(z)^3 + \cdots = \frac{G(z)}{1-G(z)} = \frac{z}{(1-z)^2-z} = \frac{z}{1-3z+z^2}\,,</math>
from which we are able to extract an exact formula for the sequence by taking the [[partial fraction expansion]] of the last generating function.