Difference between revisions of "Generating function"
m (Generating functions moved to Generating function: in keeping with general principle) |
|||
Line 1: | Line 1: | ||
+ | {{WotWAnnounce|week=Nov 15-21}} | ||
+ | |||
The idea behind '''generating functions''' is to create a [[power series]] whose [[coefficient]]s, <math>c_0, c_1, c_2, \ldots</math>, give the terms of a [[sequence]] which of interest. Therefore the power series (i.e. the generating function) is <math>c_0 + c_1 x + c_2 x^2 + \cdots </math> and the sequence is <math>c_0, c_1, c_2,\ldots</math>. | The idea behind '''generating functions''' is to create a [[power series]] whose [[coefficient]]s, <math>c_0, c_1, c_2, \ldots</math>, give the terms of a [[sequence]] which of interest. Therefore the power series (i.e. the generating function) is <math>c_0 + c_1 x + c_2 x^2 + \cdots </math> and the sequence is <math>c_0, c_1, c_2,\ldots</math>. | ||
Line 5: | Line 7: | ||
If we let <math>A(k)={n \choose k}</math>, then we have <math>{n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+</math><math>{n \choose n}x^n</math>. | If we let <math>A(k)={n \choose k}</math>, then we have <math>{n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+</math><math>{n \choose n}x^n</math>. | ||
− | This function can be described as the number of ways we can get <math> | + | This function can be described as the number of ways we can get <math>{k}</math> heads when flipping <math>n</math> different coins. |
The reason to go to such lengths is that our above polynomial is equal to <math>(1+x)^n</math> (which is clearly seen due to the [[Binomial Theorem]]). By using this equation, we can rapidly uncover identities such as <math>{n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n</math>(let <math>{x}=1</math>), also <math>{n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots</math>. | The reason to go to such lengths is that our above polynomial is equal to <math>(1+x)^n</math> (which is clearly seen due to the [[Binomial Theorem]]). By using this equation, we can rapidly uncover identities such as <math>{n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n</math>(let <math>{x}=1</math>), also <math>{n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots</math>. |
Revision as of 13:14, 15 November 2007
This is an AoPSWiki Word of the Week for Nov 15-21 |
The idea behind generating functions is to create a power series whose coefficients, , give the terms of a sequence which of interest. Therefore the power series (i.e. the generating function) is and the sequence is .
Simple Example
If we let , then we have .
This function can be described as the number of ways we can get heads when flipping different coins.
The reason to go to such lengths is that our above polynomial is equal to (which is clearly seen due to the Binomial Theorem). By using this equation, we can rapidly uncover identities such as (let ), also .
See also
- Combinatorics
- Polynomials
- Series
- generatingfunctionology a PDF version