Solving Generating Function Problems - How to Get the Answer

  • Thread starter mansi
  • Start date
  • Tags
    Functions
In summary, the conversation revolved around generating functions and their application in solving problems, particularly in combinatorics. The main purpose of a generating function is to represent the solutions to a problem, and it has proven to be a useful tool in various fields. Some examples of where generating functions are used include branching processes and the expansion of (1+x)^n. A recommended resource for further understanding of generating functions is the book "Generatingfunctionology" by Wilf.
  • #1
mansi
61
0
We are about to begin this topic soon in class...
I'd like to know all about generating functions and their application. I tried reading it up...One thing I'd like to know is, once you have a generating function...then what? You get some information...but what is it?
I tried to find no. of ways of colouring a 1 by n chessboard in 3 colours say red, blue & green if an even no. of squares must be red,even no. of squares must be blue & odd no. of squares must be green...

I think the generating function turns out to be (f(x))^-1 where f(x)= ((1-x^2)^2)*(1-x^3)). So now, what do I do to get the Required answer and why??
Thanks for the help.
 
Physics news on Phys.org
  • #2
Do you mean that the generating function is
[tex]\frac{1}{f(x)}= \frac{1}{(1-x)^2(1-x^3)}[/tex]?

The whole point of a "generating function" is that the coeffient of xn in its power series expansion is nth value you are looking for. Do you know how to find the power series for this function?
 
  • #3
I meant f(x) is that expression and not (f(x))^-1.
But well...I just got to know that the problem can be solved not using ordinary generating functions but will require "something" called exponential generating functions.
Can Someone here please give me a motivation for the concept of generating functions?
 
  • #4
A generating function is just another way to represent the solutions to a problem.

This representation has proven that it can often be useful, therefore it becomes something every budding combinatorist should learn!
 
  • #5
That's precisely what my professor said in class!Can you give me examples where they're used?
 
  • #7
Thanks,Sir...that was a big help :-)
 
  • #8
Generatingfunctionology

If your professor isn't already using it, I recommend Wilf's wonderful little book http://www.math.upenn.edu/~wilf/DownldGF.html" [Broken].
 
Last edited by a moderator:

What is a generating function?

A generating function is a mathematical tool used to represent a sequence of numbers or coefficients in a compact form. It is typically expressed as a power series, where each term represents a term in the original sequence.

What types of problems can be solved using generating functions?

Generating functions can be used to solve a variety of problems in combinatorics, number theory, and analysis. Some common examples include counting the number of ways to arrange objects, finding the coefficients of a polynomial, and determining the probability of a particular event.

How do I find the generating function for a given sequence?

The generating function for a sequence can be found by expressing the sequence as a power series and then manipulating the terms to simplify the expression. This may involve using algebraic operations, such as addition, multiplication, and substitution, to transform the series into a known form.

What is the purpose of using generating functions to solve problems?

Generating functions allow for a more efficient and elegant solution to many mathematical problems. They provide a systematic way to represent and manipulate sequences, making it easier to analyze and derive properties and relationships between different sequences.

Are there any limitations to using generating functions?

While generating functions are a powerful tool, they may not always provide an exact solution to a problem. In some cases, the resulting power series may be difficult to manipulate or may converge slowly. Additionally, some problems may not have a closed-form generating function, making it challenging to find an exact solution using this method.

Similar threads

Replies
5
Views
485
  • Linear and Abstract Algebra
Replies
2
Views
946
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
2K
Replies
3
Views
788
  • Linear and Abstract Algebra
Replies
12
Views
2K
  • Precalculus Mathematics Homework Help
Replies
15
Views
524
Replies
1
Views
757
  • Precalculus Mathematics Homework Help
Replies
7
Views
273
  • Linear and Abstract Algebra
Replies
2
Views
1K
Back
Top