maths.free › Combinatorics & Graph Theory › Generating Functions › Basic Notation and Terminology
Basic Notation and Terminology
With a sequence \sigma=\{a_n:n\ge0\} of real numbers, we associate a function F(x) defined by \[\begin{aligned}\end{aligned}\] The word function is put in quotes as we do not necessarily care about substituting a value…
Basic Notation and Terminology
With a sequence \(\sigma=\{a_n:n\ge0\}\) of real numbers, we associate a function \(F(x)\) defined by \[\begin{aligned}\end{aligned}\] The word function is put in quotes as we do not necessarily care about substituting a value of \(x\) and obtaining a specific value for \(F(x)\). In other words, we consider \(F(x)\) as a formal power series and frequently ignore issues of convergence.
It is customary to refer to \(F(x)\) as the generating function of the sequence \(\sigma\). As we have already remarked, we are not necessarily interested in calculating \(F(x)\) for specific values of \(x\). However, by convention, we take \(F(0)=a_0\).
Example
Consider the constant sequence \(\sigma=\{a_n:n\ge0\}\) with \(a_n=1\) for every \(n\ge0\). Then the generating function \(F(x)\) of \(\sigma\) is given by \[\begin{aligned}\end{aligned}\], which is called the infinite geometric series.
You may remember that this last expression is the Maclaurin series for the function \(F(x)=1/(1-x)\) and that the series converges when \(|x|\lt 1\). Since we want to think in terms of formal power series, let's see that we can justify the expression \[\begin{aligned}\end{aligned}\] without any calculus techniques. Consider the product \[\begin{aligned}\end{aligned}\] and notice that, since we multiply formal power series just like we multiply polynomials (power series are pretty much polynomials that go on forever), we have that this product is \[\begin{aligned}\end{aligned}\] Now we have that \[\begin{aligned}\end{aligned}\] or, more usefully, after dividing through by \(1-x\), \[\begin{aligned}\end{aligned}\]
The method of can be adapted to address the finite geometric series \(\sum_{j=0}^n x^j\). In that case, we look at \[\begin{aligned}(1-x) \sum_{j=0}^nx^j \amp= \sum_{j=0}^n x^j - \sum_{j=0}^n x^{j+1} \\ \amp= (1+x+\cdots + x^n) - (x+x^2+\cdots x^n + x^{n+1})\end{aligned}\]. Looking carefully, we see that everything cancels in the final expression except \(1-x^{n+1}\). Dividing both sides by \(1-x\) gives us \[\begin{aligned}\end{aligned}\] as the formula for the sum of a finite geometric series.
For reference, we state the following elementary result, which emphasizes the form of a product of two power series.
Condensed: the full section is in Keller & Trotter, Applied Combinatorics.
አሁን ምንም ዓይነት መሳሪያ ይህን አይቆጣጠርም፤ ነገር ግን ክፍሎቹ ሊቆጠሩ ይችላሉ። በታች ያለውን ይሞክሩ ወይም የራሳችሁን ይጻፉ።
ፊደላት
ለሙሉ መግለጫ፣ ምስል፣ እና በውስጡ ያለውን ፊደል ትርጓሜ ለማየት ማንኛውንም ምልክት ይጫኑ።
ጥያቄዎች
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
የዚህ ገጽ ክፍሎች ከ Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). እዚህ የተቀረጸና የተተረጎመ፤ ስህተቶች የእኛ ናቸው፡፡
በ Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs