
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Generating Functions in Discrete Mathematics
Generating functions provide a way to transform sequence problems into functions. They allow efficient manipulation and discovery of patterns. In this chapter, we will see the basics of generating functions and understand how these functions work. In addition, we will cover the various types generating functions and also how they are applied to solve mathematical problems.
What is a Generating Function?
A generating function makes a sequence of numbers as coefficients of a power series. It does not focus on individual elements in a sequence. We create a single function that represents the entire sequence in its series form.
For example, if we have a sequence like 2, 3, 5, 8, 12, … we can create a generating function like that "displays" these terms as coefficients in the power series −
$$\mathrm{2 \:+\: 3x \:+\: 5x^2 \:+\: 8x^3 \:+\: 12x^4 \:+\: \dots}$$
Here, each coefficient corresponds to a term in the sequence. Now the representation can simplify complex problems. And it helps us to use calculus and algebraic techniques to manipulate and understand the sequence.
Infinite Power Series
In generating functions, we often work with infinite power series. Infinite power series is essentially an infinite sum of terms in the form cnxn, where each cn is a constant −
$$\mathrm{\sum_{k=0}^{\infty}\: c_k x^k \:=\: c_0 \:+\: c_1 x \:+\: c_2 x^2 \:+\: c_3 x^3 \:+\: \dots}$$
Here, the sequence is generated by this series. It is simply the list of coefficients (c0, c1, c2,…). This allows us to focus on the sequence as a whole. Rather than individual terms. This can be useful for analysis.
Working with Generating Functions
Let us understand how generating functions represent sequences. Let us consider a simple example.
Example 1: Finding a Sequence from a Generating Series
Suppose we have the generating series −
$$\mathrm{3 \:+\: 8x^2 \:+\: x^3 \:+\: 17x^5 \:+\: 100x^6 \:+\: \dots}$$
To find the sequence, we simply look at the coefficients of each power of x. The sequence is thus −
$$\mathrm{3,\: 0,\: 8,\: 1,\: 0,\: 17,\: 100,\: \dots}$$
Note that each coefficient corresponds directly to a term in the sequence. It is starting from x0, and any term without a corresponding power of x is zero.
Building Generating Functions
Let us see how to construct generating functions for specific types of sequences. This idea provides ways to generate various sequences and opens up strategies to handle them efficiently.
Geometric Series
One of the simplest sequences is the constant sequence 1, 1, 1, 1, Its generating series is −
$$\mathrm{1 \:+\: x \:+\: x^2 \:+\: x^3 \:+\: \dots}$$
This is a classic geometric series, which has a closed-form solution −
$$\mathrm{\frac{1}{1 \:-\: x}}$$
From this formula we get values of x within the interval |x| < 1. However, in generating functions, we do not worry about convergence because we will not plug in specific values for x. The generating function 1/(1 - x) generates the constant sequence 1,1,1,…
Using Multiplication
From the geometric series generating functions by adjusting the terms, we can generate other sequences. For instance, if we want the sequence 2, 2, 2, 2, we can simply multiply our function by 2 −
$$\mathrm{\frac{2}{1 \:-\: x} \:=\: 2 \:+\: 2x \:+\: 2x^2 \:+\: 2x^3 \:+\: \dots}$$
This generates the sequence 2, 2, 2, 2, . Now similarly, to get the sequence 3, 9, 27, 81, we can multiply the series by 3, then replace x with 3x −
$$\mathrm{\frac{3}{1 \:-\: 3x} \:=\: 3 \:+\: 9x \:+\: 27x^2 \:+\: 81x^3 \:+\: \dots}$$
Example of Constructing a Sequence with Constant Differences
Let us make a generating function for the sequence 1, 3, 5, 7, 9, where each term increases by 2. The generating function for a constant sequence is simple. We need to account for the increasing difference. We will call the generating function A −
$$\mathrm{A \:=\: 1 \:+\: 3x \:+\: 5x^2 \:+\: 7x^3 \:+\: 9x^4 \:+\: \dots}$$
To find a function for this, we can adjust our approach. Here noting that adding the generating functions for each individual increment builds the complete sequence.
Solving through techniques like differencing helps us to find −
$$\mathrm{A \:=\: \frac{1 \:+\: x}{(1 \:-\: x)^2}}$$
This approach helps in constructing generating functions for sequences with constant differences.
Advanced Techniques with Generating Functions
We have learnt the idea of generating functions. They can also be used to represent sequences that follow specific rules or recurrence relations.
Recurrence Relations
For a sequence defined by a recurrence relation, such as −
$$\mathrm{a_n \:=\: 3a_{n-1} \:-\: 2a_{n-2}}$$
we can use generating functions to handle these patterns more systematically. With the recurrence relations, multiplying and shifting terms will give provision to transform the sequence algebraically and identify a compact generating function.
Example of Generating Function for a Recurrence Relation
Let us consider the sequence 1, 3, 7, 15, 31, 63, which follows the recurrence relation −
$$\mathrm{a_n \:=\: 3a_{n-1} \:-\: 2a_{n-2}}$$
We can find the generating function A by organizing terms and solving −
$$\mathrm{A \:=\: \frac{1}{1 \:-\: 3x \:+\: 2x^2}}$$
This function a way to generate terms in the sequence without manually finding each based on the previous terms.
Differentiation
Differentiation is another interesting technique for generating specific sequences. For example, if we start with 1/(1 x), differentiating it term by term generates the series −
$$\mathrm{1 \:+\: 2x \:+\: 3x^2 \:+\: 4x^3 \:+\: \dots \:=\: \frac{1}{(1 \:-\: x)^2}}$$
This is the generating function for the sequence 1, 2, 3, 4, which represents the sequence of natural numbers.
Differentiating again gives us −
$$\mathrm{\frac{2}{(1 \:-\: x)^3} \:=\: 2 \:+\: 6x \:+\: 12x^2 \:+\: 20x^3 \:+\: \dots}$$
Which represents the triangular numbers sequence. It is showing how derivatives helps to get more complex sequences.
Example of Using Differentiation for Triangular Numbers
To create a generating function for triangular numbers 1, 3, 6, 10, we differentiate the generating function for the natural numbers, yielding −
$$\mathrm{\frac{1 \:+\: x}{(1 \:-\: x)^3}}$$
This gives successive differentiation can uncover structured numerical patterns. It extends the utility of generating functions.
Applications of Generating Functions
As we have understood the generating functions are quite useful. They have many such applications in combinatorics, probability, and other areas where we work with sequences. They are used to solve counting problems. To analyze the complex patterns, and work with recurrence relations more effectively we use generating functions.
For example, in combinatorics, generating functions simplify the counting of objects like subsets and arrangements. In probability theory they model distributions of discrete random variables and analyze series over discrete sample spaces.
Conclusion
In this chapter, we explained the concept of generating functions in discrete mathematics. We covered how generating functions transform sequences into power series.
We reviewed examples of constructing generating functions for simple and complex sequences. It can use techniques like multiplication, differencing, and differentiation. Lastly, we understood the practical applications of generating functions in combinatory and probability.