generatingfunctionology

Covers generating functions as a bridge between discrete mathematics, on the one hand, and continuous analysis (particularly complex variable theory) on the other.

**Tag(s):**
Discrete Mathematics

**Publication date**: 20 Dec 2005

**ISBN-10**:
1568812795

**ISBN-13**:
9781568812793

**Paperback**:
192 pages

**Views**: 17,299

generatingfunctionology

Covers generating functions as a bridge between discrete mathematics, on the one hand, and continuous analysis (particularly complex variable theory) on the other.

Terms and Conditions:

Book Excerpts:

This book is about generating functions and some of their uses in discrete mathematics. The subject is so vast that there is no attempt to give a comprehensive discussion. Instead this book tries only to communicate some of the main ideas.

Generating functions are a bridge between discrete mathematics, on the one hand, and continuous analysis (particularly complex variable theory) on the other. It is possible to study them solely as tools for solving discrete problems. As such there is much that is powerful and magical in the way generating functions give unified methods for handling such problems. The reader who wished to omit the analytical parts of the subject would skip chapter 5 and portions of the earlier material. To omit those parts of the subject, however, is like listening to a stereo broadcast of, say, Beethoven’s Ninth Symphony, using only the left audio channel.

The full beauty of the subject of generating functions emerges only from tuning in on both channels: the discrete and the continuous. See how they make the solution of difference equations into child’s play. Then see how the theory of functions of a complex variable gives, virtually by inspection, the approximate size of the solution. The interplay between the two channels is vitally important for the appreciation of the music. In recent years there has been a vigorous trend in the direction of finding bijective proofs of combinatorial theorems. That is, if we want to prove that two sets have the same cardinality then we should be able to do it by exhibiting an explicit bijection between the sets. In many cases the fact that the two sets have the same cardinality was discovered in the first place by generating function arguments. Also, even though bijective arguments may be known, the generating function proofs may be shorter or more elegant.

The bijective proofs give one a certain satisfying feeling that one "really" understands why the theorem is true. The generating function arguments often give satisfying feelings of naturalness, and "oh, I could have thought of that," as well as usually offering the best route to finding exact or approximate formulas for the numbers in question.

Herbert S. Wilf wrote:Reproduction of the downloaded version is permitted for any valid educational purpose of an institution of learning, in which case only the reasonable costs of reproduction may be charged. Reproduction for profit or for any commercial purposes is strictly prohibited. It is not permitted for a web site other than this one to offer the book directly for downloading. Other web sites are cordially invited to link to this page, but must not take the file and offer it themselves.

Book Excerpts:

This book is about generating functions and some of their uses in discrete mathematics. The subject is so vast that there is no attempt to give a comprehensive discussion. Instead this book tries only to communicate some of the main ideas.

Generating functions are a bridge between discrete mathematics, on the one hand, and continuous analysis (particularly complex variable theory) on the other. It is possible to study them solely as tools for solving discrete problems. As such there is much that is powerful and magical in the way generating functions give unified methods for handling such problems. The reader who wished to omit the analytical parts of the subject would skip chapter 5 and portions of the earlier material. To omit those parts of the subject, however, is like listening to a stereo broadcast of, say, Beethoven’s Ninth Symphony, using only the left audio channel.

The full beauty of the subject of generating functions emerges only from tuning in on both channels: the discrete and the continuous. See how they make the solution of difference equations into child’s play. Then see how the theory of functions of a complex variable gives, virtually by inspection, the approximate size of the solution. The interplay between the two channels is vitally important for the appreciation of the music. In recent years there has been a vigorous trend in the direction of finding bijective proofs of combinatorial theorems. That is, if we want to prove that two sets have the same cardinality then we should be able to do it by exhibiting an explicit bijection between the sets. In many cases the fact that the two sets have the same cardinality was discovered in the first place by generating function arguments. Also, even though bijective arguments may be known, the generating function proofs may be shorter or more elegant.

The bijective proofs give one a certain satisfying feeling that one "really" understands why the theorem is true. The generating function arguments often give satisfying feelings of naturalness, and "oh, I could have thought of that," as well as usually offering the best route to finding exact or approximate formulas for the numbers in question.

Tweet

About The Author(s)

Herbert Wilf (1931-2012) was the University of Pennsylvania Thomas A. Scott Emeritus Professor of Mathematics. He was the author of six books and more than 160 research articles. From the 1950's, he was a pioneer in the mathematical programming of early computers, beginning with his work at Nuclear Development Associates, which led to his book Mathematical Methods for Digital Computers, written with A. Ralston. His early work focused on numerical analysis and complex analysis, and led to numerous research papers as well as a textbook, Mathematics for the Physical Sciences.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors