How can I learn about generating functions?
Clash Royale CLAN TAG#URR8PPP
$begingroup$
The intent of this question is to provide a list of learning resources for people who are new to generating functions and would like to learn about them.
I'm personally interested in combinatorics, and I sometimes use generating functions in answers to combinatorial questions on stackexchange, but I know many readers are not familiar with these objects. I hope this list will help those readers and provoke interest in GFs generally.
I will provide an answer below, but feel free to edit my answer or provide your own answer. Initially it will be a short list, but maybe it will grow over time. Please regard this question and its answers as a community resource.
Acknowledgement: In asking this self-answered question I was prompted by helpful advice provided by this discussion on mathematics meta stackexchange, users quid and John Omielan in particular. Thank you.
combinatorics generating-functions
$endgroup$
add a comment |
$begingroup$
The intent of this question is to provide a list of learning resources for people who are new to generating functions and would like to learn about them.
I'm personally interested in combinatorics, and I sometimes use generating functions in answers to combinatorial questions on stackexchange, but I know many readers are not familiar with these objects. I hope this list will help those readers and provoke interest in GFs generally.
I will provide an answer below, but feel free to edit my answer or provide your own answer. Initially it will be a short list, but maybe it will grow over time. Please regard this question and its answers as a community resource.
Acknowledgement: In asking this self-answered question I was prompted by helpful advice provided by this discussion on mathematics meta stackexchange, users quid and John Omielan in particular. Thank you.
combinatorics generating-functions
$endgroup$
1
$begingroup$
I might also be worth noticing that the generating function is practically the same thing as the (very used in signal processing) Z-transform, which in turn is the discrete analog of the Laplace transform. math.stackexchange.com/questions/137178/…
$endgroup$
– leonbloy
Mar 11 at 13:46
add a comment |
$begingroup$
The intent of this question is to provide a list of learning resources for people who are new to generating functions and would like to learn about them.
I'm personally interested in combinatorics, and I sometimes use generating functions in answers to combinatorial questions on stackexchange, but I know many readers are not familiar with these objects. I hope this list will help those readers and provoke interest in GFs generally.
I will provide an answer below, but feel free to edit my answer or provide your own answer. Initially it will be a short list, but maybe it will grow over time. Please regard this question and its answers as a community resource.
Acknowledgement: In asking this self-answered question I was prompted by helpful advice provided by this discussion on mathematics meta stackexchange, users quid and John Omielan in particular. Thank you.
combinatorics generating-functions
$endgroup$
The intent of this question is to provide a list of learning resources for people who are new to generating functions and would like to learn about them.
I'm personally interested in combinatorics, and I sometimes use generating functions in answers to combinatorial questions on stackexchange, but I know many readers are not familiar with these objects. I hope this list will help those readers and provoke interest in GFs generally.
I will provide an answer below, but feel free to edit my answer or provide your own answer. Initially it will be a short list, but maybe it will grow over time. Please regard this question and its answers as a community resource.
Acknowledgement: In asking this self-answered question I was prompted by helpful advice provided by this discussion on mathematics meta stackexchange, users quid and John Omielan in particular. Thank you.
combinatorics generating-functions
combinatorics generating-functions
edited Mar 10 at 16:21
John Omielan
4,7862216
4,7862216
asked Mar 10 at 13:47
awkwardawkward
6,89011026
6,89011026
1
$begingroup$
I might also be worth noticing that the generating function is practically the same thing as the (very used in signal processing) Z-transform, which in turn is the discrete analog of the Laplace transform. math.stackexchange.com/questions/137178/…
$endgroup$
– leonbloy
Mar 11 at 13:46
add a comment |
1
$begingroup$
I might also be worth noticing that the generating function is practically the same thing as the (very used in signal processing) Z-transform, which in turn is the discrete analog of the Laplace transform. math.stackexchange.com/questions/137178/…
$endgroup$
– leonbloy
Mar 11 at 13:46
1
1
$begingroup$
I might also be worth noticing that the generating function is practically the same thing as the (very used in signal processing) Z-transform, which in turn is the discrete analog of the Laplace transform. math.stackexchange.com/questions/137178/…
$endgroup$
– leonbloy
Mar 11 at 13:46
$begingroup$
I might also be worth noticing that the generating function is practically the same thing as the (very used in signal processing) Z-transform, which in turn is the discrete analog of the Laplace transform. math.stackexchange.com/questions/137178/…
$endgroup$
– leonbloy
Mar 11 at 13:46
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Here are some resources to get you started on generating functions. With one exception, which is clearly designated, any of the items mentioned here should be suitable to provide a gentle introduction to GFs for total newbies.
generatingfunctionology by Herbert S. Wilf is probably the best introductory text. You can find this book in pdf format for free, online, but I think it's worth adding a hard copy to your library. The writing style is breezy and entertaining. First sentence: "A generating function is a clothesline on which we hang up a sequence of numbers for display."An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet is another fine introduction. Despite its title, the book is mostly about generating functions. Coursera has a free online course from Princeton University based on this book, with Professor Sedgewick as the instructor,so here is your chance to sit at the feet of the Master, figuratively: Coursera Analysis of Algorithms. There is also a follow-on course on Analytic Combinatorics: Coursera Analytic Combinatorics. The analytic combinatorics course is based on the book Analytic Combinatorics by the same two authors, which is a fine book, but I don't think it's the best starting point for most beginners. (Of course, you might be the exception, and it really is a wonderful book with encyclopedic coverage.) Both Coursera courses are selective in their coverage and do not attempt to cover the entire contents of their respective books, especially the course on analytic combinatorics.
While we are on the subject of free online materials, Bogart's Introductory Combinatorics (pdf) includes an introduction to generating functions. Bogart leads the reader to discover ideas and methods for himself through a series of problems. In fact, the book is almost entirely composed of problems.
Schaum's Outline of Theory and Problems of Combinatorics by V.K. Balakrishnan includes a good introduction to generating functions and is noteworthy for being inexpensive by comparison with other texts (around $20 on Amazon the last time I checked). I find this book useful both for reference and as a learning resource. Coverage includes some relatively advanced topics, such as rook polynomials and the Polya Enumeration Theorem, but you can skip those parts on a first reading.
- Do you find yourself overwhelmed by the amount of material on generating functions in the above books? Maybe you would like a short, down-to-earth introduction, just the basics. Then you might like Chapter Six of Applied Combinatorics by Alan Tucker.
- And there are many others, I am sure. Many books on combinatorics include sections on generating functions.
As for prerequisites, many applications of GFs require only a knowledge of polynomials. But many others require infinite series, so you need some exposure to series like infinite geometric series, the series for $e^x$, and the Binomial Theorem for negative and fractional exponents. Interestingly enough, we can often (but not always) ignore questions of convergence, because we view the series as formal objects and don't worry about evaluating them. It is frequently useful to differentiate or integrate a generating function, so you need calculus skills. (In fact, part of the fascination of generating functions is that they take a problem in discrete mathematics, where the normal tools are addition, multiplication, subtraction and division, and transform the problem into the realm of the continuous, where tools like differential and integral calculus apply.) Some applications do use differential equations or complex analysis, but you can go a long way without these.
A computer algebra system, such as Wolfram Alpha, though not essential, is sometimes useful to take the drudgery out of calculations that would otherwise be tedious. I used to feel guilty when I used a computer to multiply two long polynomials, but I've gotten over the guilt and now feel that to the combinatorialist, computer algebra is a basic tool like a calculator.
To pique your interest in GFs, here is how the statistician Frederick Mosteller described his initial exposure to generating functions.
A key moment in my life occurred in one of those classes during my
sophomore year. We had the question: When three dice are rolled what
is the chance that the sum of the faces will be 10? The students in
this course were very good, but we all got the answer largely by
counting on our fingers. When we came to class, I said to the teacher,
"That's all very well - we got the answer - but if we had been asked
about six dice and the probability of getting 18, we would still be
home counting. How do you do problems like that?" He said, "I don't
know, but I know a man who probably does and I'll ask him." One day I
was in the library and Professor Edwin G Olds of the Mathematics
Department came in. He shouted at me, "I hear you're interested in the
three dice problem." He had a huge voice, and you know how libraries
are. I was embarrassed. "Well, come and see me," he said, and I'll
show you about it." "Sure, " I said. But I was saying to myself, "I'll
never go." Then he said, "What are you doing?" I showed him. "That's
nothing important," he said. "Let's go now."
So we went to his office, and he showed me a generating function. It
was the most marvelous thing I had ever seen in mathematics. It used
mathematics that, up to that time, in my heart of hearts, I had
thought was something that mathematicians just did to create homework
problems for innocent students in high school and college. I don't
know where I had got ideas like that about various parts of
mathematics. Anyway, I was stunned when I saw how Olds used this
mathematics that I hadn't believed in. He used it in such an unusually
outrageous way. It was a total retranslation of the meaning of the
numbers. [Albers, More Mathematical People].
$endgroup$
add a comment |
$begingroup$
One of the treasures which might fit the needs is Concrete Mathematics
by R.L. Graham, D.E. Knuth and O. Patashnik.
A starting point could be section 5.4 Generating Functions where we can read:
- We come now to the most important idea in this whole book, the
notion of a generating function. ...
The book provides a wealth of instructive examples devoting chapter 7 Generating Functions entirely to the subject of interest.
$endgroup$
1
$begingroup$
I agree entirely, the book is a treasure. I would just like to add that if the reader is impatient to learn about GFs, it is possible to skip directly to the material on GFs without absorbing all the information in the early chapters. (I recall reading someone's complaint that he was directed to CM to learn about GFs, but he bogged down somewhere in the earlier chapters, which do contain a lot of material. Not that any of the book should be neglected, it's all valuable.)
$endgroup$
– awkward
Mar 11 at 12:10
$begingroup$
@awkward: I agree in that all of the book is highly informative and a great pleasure to read. :-) I think I've just added the hint you have in mind by indicating section 5.4 as starting point. Section 5.4 provides some basic material which is helpful to grasp chapter 7 afterwards.
$endgroup$
– Markus Scheuer
Mar 11 at 12:23
add a comment |
$begingroup$
Nicholas Loehr's Bijective Combinatorics, 1st edition includes the best treatment of formal power series I have ever seen in the combinatorics literature. (It has been watered down in the 2nd edition, which has recently appeared under the name Combinatorics.)
Herbert Wilf's generatingfunctionology goes farther than any other text I know into the usage of generating functions (but is sloppier at setting the stage).
A lot of other texts focus on uses of generating functions without formally defining them. For example: Aigner or Wagner or Hulpke or MacGillivray. For best effects, combine them with some text on abstract algebra.
$endgroup$
add a comment |
$begingroup$
One book which is worth mentioning is Irresistible Integrals by George Boros and Victor Moll. It touches a bit on GFs, especially in relation to their use in the evaluation of series and integrals, as well as their connections to the study of polynomials and recurrence relations.
One of the first chapters uses the recursive definition of the Fibonacci numbers in order to find their generating function, namely $$sum_ngeq0F_nx^n=frac11-x-x^2$$
But the use of GF's is consistent throughout the book. I highly recommend it if you also want to learn about series, integrals, and polynomials.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3142386%2fhow-can-i-learn-about-generating-functions%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here are some resources to get you started on generating functions. With one exception, which is clearly designated, any of the items mentioned here should be suitable to provide a gentle introduction to GFs for total newbies.
generatingfunctionology by Herbert S. Wilf is probably the best introductory text. You can find this book in pdf format for free, online, but I think it's worth adding a hard copy to your library. The writing style is breezy and entertaining. First sentence: "A generating function is a clothesline on which we hang up a sequence of numbers for display."An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet is another fine introduction. Despite its title, the book is mostly about generating functions. Coursera has a free online course from Princeton University based on this book, with Professor Sedgewick as the instructor,so here is your chance to sit at the feet of the Master, figuratively: Coursera Analysis of Algorithms. There is also a follow-on course on Analytic Combinatorics: Coursera Analytic Combinatorics. The analytic combinatorics course is based on the book Analytic Combinatorics by the same two authors, which is a fine book, but I don't think it's the best starting point for most beginners. (Of course, you might be the exception, and it really is a wonderful book with encyclopedic coverage.) Both Coursera courses are selective in their coverage and do not attempt to cover the entire contents of their respective books, especially the course on analytic combinatorics.
While we are on the subject of free online materials, Bogart's Introductory Combinatorics (pdf) includes an introduction to generating functions. Bogart leads the reader to discover ideas and methods for himself through a series of problems. In fact, the book is almost entirely composed of problems.
Schaum's Outline of Theory and Problems of Combinatorics by V.K. Balakrishnan includes a good introduction to generating functions and is noteworthy for being inexpensive by comparison with other texts (around $20 on Amazon the last time I checked). I find this book useful both for reference and as a learning resource. Coverage includes some relatively advanced topics, such as rook polynomials and the Polya Enumeration Theorem, but you can skip those parts on a first reading.
- Do you find yourself overwhelmed by the amount of material on generating functions in the above books? Maybe you would like a short, down-to-earth introduction, just the basics. Then you might like Chapter Six of Applied Combinatorics by Alan Tucker.
- And there are many others, I am sure. Many books on combinatorics include sections on generating functions.
As for prerequisites, many applications of GFs require only a knowledge of polynomials. But many others require infinite series, so you need some exposure to series like infinite geometric series, the series for $e^x$, and the Binomial Theorem for negative and fractional exponents. Interestingly enough, we can often (but not always) ignore questions of convergence, because we view the series as formal objects and don't worry about evaluating them. It is frequently useful to differentiate or integrate a generating function, so you need calculus skills. (In fact, part of the fascination of generating functions is that they take a problem in discrete mathematics, where the normal tools are addition, multiplication, subtraction and division, and transform the problem into the realm of the continuous, where tools like differential and integral calculus apply.) Some applications do use differential equations or complex analysis, but you can go a long way without these.
A computer algebra system, such as Wolfram Alpha, though not essential, is sometimes useful to take the drudgery out of calculations that would otherwise be tedious. I used to feel guilty when I used a computer to multiply two long polynomials, but I've gotten over the guilt and now feel that to the combinatorialist, computer algebra is a basic tool like a calculator.
To pique your interest in GFs, here is how the statistician Frederick Mosteller described his initial exposure to generating functions.
A key moment in my life occurred in one of those classes during my
sophomore year. We had the question: When three dice are rolled what
is the chance that the sum of the faces will be 10? The students in
this course were very good, but we all got the answer largely by
counting on our fingers. When we came to class, I said to the teacher,
"That's all very well - we got the answer - but if we had been asked
about six dice and the probability of getting 18, we would still be
home counting. How do you do problems like that?" He said, "I don't
know, but I know a man who probably does and I'll ask him." One day I
was in the library and Professor Edwin G Olds of the Mathematics
Department came in. He shouted at me, "I hear you're interested in the
three dice problem." He had a huge voice, and you know how libraries
are. I was embarrassed. "Well, come and see me," he said, and I'll
show you about it." "Sure, " I said. But I was saying to myself, "I'll
never go." Then he said, "What are you doing?" I showed him. "That's
nothing important," he said. "Let's go now."
So we went to his office, and he showed me a generating function. It
was the most marvelous thing I had ever seen in mathematics. It used
mathematics that, up to that time, in my heart of hearts, I had
thought was something that mathematicians just did to create homework
problems for innocent students in high school and college. I don't
know where I had got ideas like that about various parts of
mathematics. Anyway, I was stunned when I saw how Olds used this
mathematics that I hadn't believed in. He used it in such an unusually
outrageous way. It was a total retranslation of the meaning of the
numbers. [Albers, More Mathematical People].
$endgroup$
add a comment |
$begingroup$
Here are some resources to get you started on generating functions. With one exception, which is clearly designated, any of the items mentioned here should be suitable to provide a gentle introduction to GFs for total newbies.
generatingfunctionology by Herbert S. Wilf is probably the best introductory text. You can find this book in pdf format for free, online, but I think it's worth adding a hard copy to your library. The writing style is breezy and entertaining. First sentence: "A generating function is a clothesline on which we hang up a sequence of numbers for display."An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet is another fine introduction. Despite its title, the book is mostly about generating functions. Coursera has a free online course from Princeton University based on this book, with Professor Sedgewick as the instructor,so here is your chance to sit at the feet of the Master, figuratively: Coursera Analysis of Algorithms. There is also a follow-on course on Analytic Combinatorics: Coursera Analytic Combinatorics. The analytic combinatorics course is based on the book Analytic Combinatorics by the same two authors, which is a fine book, but I don't think it's the best starting point for most beginners. (Of course, you might be the exception, and it really is a wonderful book with encyclopedic coverage.) Both Coursera courses are selective in their coverage and do not attempt to cover the entire contents of their respective books, especially the course on analytic combinatorics.
While we are on the subject of free online materials, Bogart's Introductory Combinatorics (pdf) includes an introduction to generating functions. Bogart leads the reader to discover ideas and methods for himself through a series of problems. In fact, the book is almost entirely composed of problems.
Schaum's Outline of Theory and Problems of Combinatorics by V.K. Balakrishnan includes a good introduction to generating functions and is noteworthy for being inexpensive by comparison with other texts (around $20 on Amazon the last time I checked). I find this book useful both for reference and as a learning resource. Coverage includes some relatively advanced topics, such as rook polynomials and the Polya Enumeration Theorem, but you can skip those parts on a first reading.
- Do you find yourself overwhelmed by the amount of material on generating functions in the above books? Maybe you would like a short, down-to-earth introduction, just the basics. Then you might like Chapter Six of Applied Combinatorics by Alan Tucker.
- And there are many others, I am sure. Many books on combinatorics include sections on generating functions.
As for prerequisites, many applications of GFs require only a knowledge of polynomials. But many others require infinite series, so you need some exposure to series like infinite geometric series, the series for $e^x$, and the Binomial Theorem for negative and fractional exponents. Interestingly enough, we can often (but not always) ignore questions of convergence, because we view the series as formal objects and don't worry about evaluating them. It is frequently useful to differentiate or integrate a generating function, so you need calculus skills. (In fact, part of the fascination of generating functions is that they take a problem in discrete mathematics, where the normal tools are addition, multiplication, subtraction and division, and transform the problem into the realm of the continuous, where tools like differential and integral calculus apply.) Some applications do use differential equations or complex analysis, but you can go a long way without these.
A computer algebra system, such as Wolfram Alpha, though not essential, is sometimes useful to take the drudgery out of calculations that would otherwise be tedious. I used to feel guilty when I used a computer to multiply two long polynomials, but I've gotten over the guilt and now feel that to the combinatorialist, computer algebra is a basic tool like a calculator.
To pique your interest in GFs, here is how the statistician Frederick Mosteller described his initial exposure to generating functions.
A key moment in my life occurred in one of those classes during my
sophomore year. We had the question: When three dice are rolled what
is the chance that the sum of the faces will be 10? The students in
this course were very good, but we all got the answer largely by
counting on our fingers. When we came to class, I said to the teacher,
"That's all very well - we got the answer - but if we had been asked
about six dice and the probability of getting 18, we would still be
home counting. How do you do problems like that?" He said, "I don't
know, but I know a man who probably does and I'll ask him." One day I
was in the library and Professor Edwin G Olds of the Mathematics
Department came in. He shouted at me, "I hear you're interested in the
three dice problem." He had a huge voice, and you know how libraries
are. I was embarrassed. "Well, come and see me," he said, and I'll
show you about it." "Sure, " I said. But I was saying to myself, "I'll
never go." Then he said, "What are you doing?" I showed him. "That's
nothing important," he said. "Let's go now."
So we went to his office, and he showed me a generating function. It
was the most marvelous thing I had ever seen in mathematics. It used
mathematics that, up to that time, in my heart of hearts, I had
thought was something that mathematicians just did to create homework
problems for innocent students in high school and college. I don't
know where I had got ideas like that about various parts of
mathematics. Anyway, I was stunned when I saw how Olds used this
mathematics that I hadn't believed in. He used it in such an unusually
outrageous way. It was a total retranslation of the meaning of the
numbers. [Albers, More Mathematical People].
$endgroup$
add a comment |
$begingroup$
Here are some resources to get you started on generating functions. With one exception, which is clearly designated, any of the items mentioned here should be suitable to provide a gentle introduction to GFs for total newbies.
generatingfunctionology by Herbert S. Wilf is probably the best introductory text. You can find this book in pdf format for free, online, but I think it's worth adding a hard copy to your library. The writing style is breezy and entertaining. First sentence: "A generating function is a clothesline on which we hang up a sequence of numbers for display."An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet is another fine introduction. Despite its title, the book is mostly about generating functions. Coursera has a free online course from Princeton University based on this book, with Professor Sedgewick as the instructor,so here is your chance to sit at the feet of the Master, figuratively: Coursera Analysis of Algorithms. There is also a follow-on course on Analytic Combinatorics: Coursera Analytic Combinatorics. The analytic combinatorics course is based on the book Analytic Combinatorics by the same two authors, which is a fine book, but I don't think it's the best starting point for most beginners. (Of course, you might be the exception, and it really is a wonderful book with encyclopedic coverage.) Both Coursera courses are selective in their coverage and do not attempt to cover the entire contents of their respective books, especially the course on analytic combinatorics.
While we are on the subject of free online materials, Bogart's Introductory Combinatorics (pdf) includes an introduction to generating functions. Bogart leads the reader to discover ideas and methods for himself through a series of problems. In fact, the book is almost entirely composed of problems.
Schaum's Outline of Theory and Problems of Combinatorics by V.K. Balakrishnan includes a good introduction to generating functions and is noteworthy for being inexpensive by comparison with other texts (around $20 on Amazon the last time I checked). I find this book useful both for reference and as a learning resource. Coverage includes some relatively advanced topics, such as rook polynomials and the Polya Enumeration Theorem, but you can skip those parts on a first reading.
- Do you find yourself overwhelmed by the amount of material on generating functions in the above books? Maybe you would like a short, down-to-earth introduction, just the basics. Then you might like Chapter Six of Applied Combinatorics by Alan Tucker.
- And there are many others, I am sure. Many books on combinatorics include sections on generating functions.
As for prerequisites, many applications of GFs require only a knowledge of polynomials. But many others require infinite series, so you need some exposure to series like infinite geometric series, the series for $e^x$, and the Binomial Theorem for negative and fractional exponents. Interestingly enough, we can often (but not always) ignore questions of convergence, because we view the series as formal objects and don't worry about evaluating them. It is frequently useful to differentiate or integrate a generating function, so you need calculus skills. (In fact, part of the fascination of generating functions is that they take a problem in discrete mathematics, where the normal tools are addition, multiplication, subtraction and division, and transform the problem into the realm of the continuous, where tools like differential and integral calculus apply.) Some applications do use differential equations or complex analysis, but you can go a long way without these.
A computer algebra system, such as Wolfram Alpha, though not essential, is sometimes useful to take the drudgery out of calculations that would otherwise be tedious. I used to feel guilty when I used a computer to multiply two long polynomials, but I've gotten over the guilt and now feel that to the combinatorialist, computer algebra is a basic tool like a calculator.
To pique your interest in GFs, here is how the statistician Frederick Mosteller described his initial exposure to generating functions.
A key moment in my life occurred in one of those classes during my
sophomore year. We had the question: When three dice are rolled what
is the chance that the sum of the faces will be 10? The students in
this course were very good, but we all got the answer largely by
counting on our fingers. When we came to class, I said to the teacher,
"That's all very well - we got the answer - but if we had been asked
about six dice and the probability of getting 18, we would still be
home counting. How do you do problems like that?" He said, "I don't
know, but I know a man who probably does and I'll ask him." One day I
was in the library and Professor Edwin G Olds of the Mathematics
Department came in. He shouted at me, "I hear you're interested in the
three dice problem." He had a huge voice, and you know how libraries
are. I was embarrassed. "Well, come and see me," he said, and I'll
show you about it." "Sure, " I said. But I was saying to myself, "I'll
never go." Then he said, "What are you doing?" I showed him. "That's
nothing important," he said. "Let's go now."
So we went to his office, and he showed me a generating function. It
was the most marvelous thing I had ever seen in mathematics. It used
mathematics that, up to that time, in my heart of hearts, I had
thought was something that mathematicians just did to create homework
problems for innocent students in high school and college. I don't
know where I had got ideas like that about various parts of
mathematics. Anyway, I was stunned when I saw how Olds used this
mathematics that I hadn't believed in. He used it in such an unusually
outrageous way. It was a total retranslation of the meaning of the
numbers. [Albers, More Mathematical People].
$endgroup$
Here are some resources to get you started on generating functions. With one exception, which is clearly designated, any of the items mentioned here should be suitable to provide a gentle introduction to GFs for total newbies.
generatingfunctionology by Herbert S. Wilf is probably the best introductory text. You can find this book in pdf format for free, online, but I think it's worth adding a hard copy to your library. The writing style is breezy and entertaining. First sentence: "A generating function is a clothesline on which we hang up a sequence of numbers for display."An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet is another fine introduction. Despite its title, the book is mostly about generating functions. Coursera has a free online course from Princeton University based on this book, with Professor Sedgewick as the instructor,so here is your chance to sit at the feet of the Master, figuratively: Coursera Analysis of Algorithms. There is also a follow-on course on Analytic Combinatorics: Coursera Analytic Combinatorics. The analytic combinatorics course is based on the book Analytic Combinatorics by the same two authors, which is a fine book, but I don't think it's the best starting point for most beginners. (Of course, you might be the exception, and it really is a wonderful book with encyclopedic coverage.) Both Coursera courses are selective in their coverage and do not attempt to cover the entire contents of their respective books, especially the course on analytic combinatorics.
While we are on the subject of free online materials, Bogart's Introductory Combinatorics (pdf) includes an introduction to generating functions. Bogart leads the reader to discover ideas and methods for himself through a series of problems. In fact, the book is almost entirely composed of problems.
Schaum's Outline of Theory and Problems of Combinatorics by V.K. Balakrishnan includes a good introduction to generating functions and is noteworthy for being inexpensive by comparison with other texts (around $20 on Amazon the last time I checked). I find this book useful both for reference and as a learning resource. Coverage includes some relatively advanced topics, such as rook polynomials and the Polya Enumeration Theorem, but you can skip those parts on a first reading.
- Do you find yourself overwhelmed by the amount of material on generating functions in the above books? Maybe you would like a short, down-to-earth introduction, just the basics. Then you might like Chapter Six of Applied Combinatorics by Alan Tucker.
- And there are many others, I am sure. Many books on combinatorics include sections on generating functions.
As for prerequisites, many applications of GFs require only a knowledge of polynomials. But many others require infinite series, so you need some exposure to series like infinite geometric series, the series for $e^x$, and the Binomial Theorem for negative and fractional exponents. Interestingly enough, we can often (but not always) ignore questions of convergence, because we view the series as formal objects and don't worry about evaluating them. It is frequently useful to differentiate or integrate a generating function, so you need calculus skills. (In fact, part of the fascination of generating functions is that they take a problem in discrete mathematics, where the normal tools are addition, multiplication, subtraction and division, and transform the problem into the realm of the continuous, where tools like differential and integral calculus apply.) Some applications do use differential equations or complex analysis, but you can go a long way without these.
A computer algebra system, such as Wolfram Alpha, though not essential, is sometimes useful to take the drudgery out of calculations that would otherwise be tedious. I used to feel guilty when I used a computer to multiply two long polynomials, but I've gotten over the guilt and now feel that to the combinatorialist, computer algebra is a basic tool like a calculator.
To pique your interest in GFs, here is how the statistician Frederick Mosteller described his initial exposure to generating functions.
A key moment in my life occurred in one of those classes during my
sophomore year. We had the question: When three dice are rolled what
is the chance that the sum of the faces will be 10? The students in
this course were very good, but we all got the answer largely by
counting on our fingers. When we came to class, I said to the teacher,
"That's all very well - we got the answer - but if we had been asked
about six dice and the probability of getting 18, we would still be
home counting. How do you do problems like that?" He said, "I don't
know, but I know a man who probably does and I'll ask him." One day I
was in the library and Professor Edwin G Olds of the Mathematics
Department came in. He shouted at me, "I hear you're interested in the
three dice problem." He had a huge voice, and you know how libraries
are. I was embarrassed. "Well, come and see me," he said, and I'll
show you about it." "Sure, " I said. But I was saying to myself, "I'll
never go." Then he said, "What are you doing?" I showed him. "That's
nothing important," he said. "Let's go now."
So we went to his office, and he showed me a generating function. It
was the most marvelous thing I had ever seen in mathematics. It used
mathematics that, up to that time, in my heart of hearts, I had
thought was something that mathematicians just did to create homework
problems for innocent students in high school and college. I don't
know where I had got ideas like that about various parts of
mathematics. Anyway, I was stunned when I saw how Olds used this
mathematics that I hadn't believed in. He used it in such an unusually
outrageous way. It was a total retranslation of the meaning of the
numbers. [Albers, More Mathematical People].
edited Mar 14 at 12:26
answered Mar 10 at 13:47
awkwardawkward
6,89011026
6,89011026
add a comment |
add a comment |
$begingroup$
One of the treasures which might fit the needs is Concrete Mathematics
by R.L. Graham, D.E. Knuth and O. Patashnik.
A starting point could be section 5.4 Generating Functions where we can read:
- We come now to the most important idea in this whole book, the
notion of a generating function. ...
The book provides a wealth of instructive examples devoting chapter 7 Generating Functions entirely to the subject of interest.
$endgroup$
1
$begingroup$
I agree entirely, the book is a treasure. I would just like to add that if the reader is impatient to learn about GFs, it is possible to skip directly to the material on GFs without absorbing all the information in the early chapters. (I recall reading someone's complaint that he was directed to CM to learn about GFs, but he bogged down somewhere in the earlier chapters, which do contain a lot of material. Not that any of the book should be neglected, it's all valuable.)
$endgroup$
– awkward
Mar 11 at 12:10
$begingroup$
@awkward: I agree in that all of the book is highly informative and a great pleasure to read. :-) I think I've just added the hint you have in mind by indicating section 5.4 as starting point. Section 5.4 provides some basic material which is helpful to grasp chapter 7 afterwards.
$endgroup$
– Markus Scheuer
Mar 11 at 12:23
add a comment |
$begingroup$
One of the treasures which might fit the needs is Concrete Mathematics
by R.L. Graham, D.E. Knuth and O. Patashnik.
A starting point could be section 5.4 Generating Functions where we can read:
- We come now to the most important idea in this whole book, the
notion of a generating function. ...
The book provides a wealth of instructive examples devoting chapter 7 Generating Functions entirely to the subject of interest.
$endgroup$
1
$begingroup$
I agree entirely, the book is a treasure. I would just like to add that if the reader is impatient to learn about GFs, it is possible to skip directly to the material on GFs without absorbing all the information in the early chapters. (I recall reading someone's complaint that he was directed to CM to learn about GFs, but he bogged down somewhere in the earlier chapters, which do contain a lot of material. Not that any of the book should be neglected, it's all valuable.)
$endgroup$
– awkward
Mar 11 at 12:10
$begingroup$
@awkward: I agree in that all of the book is highly informative and a great pleasure to read. :-) I think I've just added the hint you have in mind by indicating section 5.4 as starting point. Section 5.4 provides some basic material which is helpful to grasp chapter 7 afterwards.
$endgroup$
– Markus Scheuer
Mar 11 at 12:23
add a comment |
$begingroup$
One of the treasures which might fit the needs is Concrete Mathematics
by R.L. Graham, D.E. Knuth and O. Patashnik.
A starting point could be section 5.4 Generating Functions where we can read:
- We come now to the most important idea in this whole book, the
notion of a generating function. ...
The book provides a wealth of instructive examples devoting chapter 7 Generating Functions entirely to the subject of interest.
$endgroup$
One of the treasures which might fit the needs is Concrete Mathematics
by R.L. Graham, D.E. Knuth and O. Patashnik.
A starting point could be section 5.4 Generating Functions where we can read:
- We come now to the most important idea in this whole book, the
notion of a generating function. ...
The book provides a wealth of instructive examples devoting chapter 7 Generating Functions entirely to the subject of interest.
edited Mar 11 at 7:30
answered Mar 10 at 19:54
Markus ScheuerMarkus Scheuer
64k460152
64k460152
1
$begingroup$
I agree entirely, the book is a treasure. I would just like to add that if the reader is impatient to learn about GFs, it is possible to skip directly to the material on GFs without absorbing all the information in the early chapters. (I recall reading someone's complaint that he was directed to CM to learn about GFs, but he bogged down somewhere in the earlier chapters, which do contain a lot of material. Not that any of the book should be neglected, it's all valuable.)
$endgroup$
– awkward
Mar 11 at 12:10
$begingroup$
@awkward: I agree in that all of the book is highly informative and a great pleasure to read. :-) I think I've just added the hint you have in mind by indicating section 5.4 as starting point. Section 5.4 provides some basic material which is helpful to grasp chapter 7 afterwards.
$endgroup$
– Markus Scheuer
Mar 11 at 12:23
add a comment |
1
$begingroup$
I agree entirely, the book is a treasure. I would just like to add that if the reader is impatient to learn about GFs, it is possible to skip directly to the material on GFs without absorbing all the information in the early chapters. (I recall reading someone's complaint that he was directed to CM to learn about GFs, but he bogged down somewhere in the earlier chapters, which do contain a lot of material. Not that any of the book should be neglected, it's all valuable.)
$endgroup$
– awkward
Mar 11 at 12:10
$begingroup$
@awkward: I agree in that all of the book is highly informative and a great pleasure to read. :-) I think I've just added the hint you have in mind by indicating section 5.4 as starting point. Section 5.4 provides some basic material which is helpful to grasp chapter 7 afterwards.
$endgroup$
– Markus Scheuer
Mar 11 at 12:23
1
1
$begingroup$
I agree entirely, the book is a treasure. I would just like to add that if the reader is impatient to learn about GFs, it is possible to skip directly to the material on GFs without absorbing all the information in the early chapters. (I recall reading someone's complaint that he was directed to CM to learn about GFs, but he bogged down somewhere in the earlier chapters, which do contain a lot of material. Not that any of the book should be neglected, it's all valuable.)
$endgroup$
– awkward
Mar 11 at 12:10
$begingroup$
I agree entirely, the book is a treasure. I would just like to add that if the reader is impatient to learn about GFs, it is possible to skip directly to the material on GFs without absorbing all the information in the early chapters. (I recall reading someone's complaint that he was directed to CM to learn about GFs, but he bogged down somewhere in the earlier chapters, which do contain a lot of material. Not that any of the book should be neglected, it's all valuable.)
$endgroup$
– awkward
Mar 11 at 12:10
$begingroup$
@awkward: I agree in that all of the book is highly informative and a great pleasure to read. :-) I think I've just added the hint you have in mind by indicating section 5.4 as starting point. Section 5.4 provides some basic material which is helpful to grasp chapter 7 afterwards.
$endgroup$
– Markus Scheuer
Mar 11 at 12:23
$begingroup$
@awkward: I agree in that all of the book is highly informative and a great pleasure to read. :-) I think I've just added the hint you have in mind by indicating section 5.4 as starting point. Section 5.4 provides some basic material which is helpful to grasp chapter 7 afterwards.
$endgroup$
– Markus Scheuer
Mar 11 at 12:23
add a comment |
$begingroup$
Nicholas Loehr's Bijective Combinatorics, 1st edition includes the best treatment of formal power series I have ever seen in the combinatorics literature. (It has been watered down in the 2nd edition, which has recently appeared under the name Combinatorics.)
Herbert Wilf's generatingfunctionology goes farther than any other text I know into the usage of generating functions (but is sloppier at setting the stage).
A lot of other texts focus on uses of generating functions without formally defining them. For example: Aigner or Wagner or Hulpke or MacGillivray. For best effects, combine them with some text on abstract algebra.
$endgroup$
add a comment |
$begingroup$
Nicholas Loehr's Bijective Combinatorics, 1st edition includes the best treatment of formal power series I have ever seen in the combinatorics literature. (It has been watered down in the 2nd edition, which has recently appeared under the name Combinatorics.)
Herbert Wilf's generatingfunctionology goes farther than any other text I know into the usage of generating functions (but is sloppier at setting the stage).
A lot of other texts focus on uses of generating functions without formally defining them. For example: Aigner or Wagner or Hulpke or MacGillivray. For best effects, combine them with some text on abstract algebra.
$endgroup$
add a comment |
$begingroup$
Nicholas Loehr's Bijective Combinatorics, 1st edition includes the best treatment of formal power series I have ever seen in the combinatorics literature. (It has been watered down in the 2nd edition, which has recently appeared under the name Combinatorics.)
Herbert Wilf's generatingfunctionology goes farther than any other text I know into the usage of generating functions (but is sloppier at setting the stage).
A lot of other texts focus on uses of generating functions without formally defining them. For example: Aigner or Wagner or Hulpke or MacGillivray. For best effects, combine them with some text on abstract algebra.
$endgroup$
Nicholas Loehr's Bijective Combinatorics, 1st edition includes the best treatment of formal power series I have ever seen in the combinatorics literature. (It has been watered down in the 2nd edition, which has recently appeared under the name Combinatorics.)
Herbert Wilf's generatingfunctionology goes farther than any other text I know into the usage of generating functions (but is sloppier at setting the stage).
A lot of other texts focus on uses of generating functions without formally defining them. For example: Aigner or Wagner or Hulpke or MacGillivray. For best effects, combine them with some text on abstract algebra.
answered Mar 11 at 15:54
darij grinbergdarij grinberg
11.5k33168
11.5k33168
add a comment |
add a comment |
$begingroup$
One book which is worth mentioning is Irresistible Integrals by George Boros and Victor Moll. It touches a bit on GFs, especially in relation to their use in the evaluation of series and integrals, as well as their connections to the study of polynomials and recurrence relations.
One of the first chapters uses the recursive definition of the Fibonacci numbers in order to find their generating function, namely $$sum_ngeq0F_nx^n=frac11-x-x^2$$
But the use of GF's is consistent throughout the book. I highly recommend it if you also want to learn about series, integrals, and polynomials.
$endgroup$
add a comment |
$begingroup$
One book which is worth mentioning is Irresistible Integrals by George Boros and Victor Moll. It touches a bit on GFs, especially in relation to their use in the evaluation of series and integrals, as well as their connections to the study of polynomials and recurrence relations.
One of the first chapters uses the recursive definition of the Fibonacci numbers in order to find their generating function, namely $$sum_ngeq0F_nx^n=frac11-x-x^2$$
But the use of GF's is consistent throughout the book. I highly recommend it if you also want to learn about series, integrals, and polynomials.
$endgroup$
add a comment |
$begingroup$
One book which is worth mentioning is Irresistible Integrals by George Boros and Victor Moll. It touches a bit on GFs, especially in relation to their use in the evaluation of series and integrals, as well as their connections to the study of polynomials and recurrence relations.
One of the first chapters uses the recursive definition of the Fibonacci numbers in order to find their generating function, namely $$sum_ngeq0F_nx^n=frac11-x-x^2$$
But the use of GF's is consistent throughout the book. I highly recommend it if you also want to learn about series, integrals, and polynomials.
$endgroup$
One book which is worth mentioning is Irresistible Integrals by George Boros and Victor Moll. It touches a bit on GFs, especially in relation to their use in the evaluation of series and integrals, as well as their connections to the study of polynomials and recurrence relations.
One of the first chapters uses the recursive definition of the Fibonacci numbers in order to find their generating function, namely $$sum_ngeq0F_nx^n=frac11-x-x^2$$
But the use of GF's is consistent throughout the book. I highly recommend it if you also want to learn about series, integrals, and polynomials.
answered Mar 11 at 16:00
clathratusclathratus
5,1041439
5,1041439
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3142386%2fhow-can-i-learn-about-generating-functions%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I might also be worth noticing that the generating function is practically the same thing as the (very used in signal processing) Z-transform, which in turn is the discrete analog of the Laplace transform. math.stackexchange.com/questions/137178/…
$endgroup$
– leonbloy
Mar 11 at 13:46