Generating Functions
Generating Functions
- Generating Functions represents sequences where each term of a sequence is expressed as a coefficient of a variable x in a formal power series.
- Mathematically, for an infinite sequence, say a0,a1,a2,…,ak,…,
- the generating function will be −
- Gx=a0+a1x+a2x2+⋯+akxk+⋯=∑k=0∞akxk
- Some Areas of Application
- Generating functions can be used for the following purposes −
- For solving a variety of counting problems. For example, the number of ways to make change for a Rs. 100 note with the notes of denominations Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 and Rs.50
- For solving recurrence relations
- For proving some of the combinatorial identities
- For finding asymptotic formulas for terms of sequences
- Problem 1
- What are the generating functions for the sequences {ak}
- with ak=2 and ak=3k ?
- Solution
- When ak=2 , generating function, G(x)=∑∞k=02xk=2+2x+2x2+2x3+…
- When ak=3k, G(x)=∑∞k=03kxk=0+3x+6x2+9x3+……
- Problem 2
- What is the generating function of the infinite series; 1,1,1,1,… ?
- Solution
- Here, ak=1 , for 0≤k≤∞
- Hence, G(x)=1+x+x2+x3+…⋯=1(1−x)
- Some Useful Generating Functions
- For ak=ak,G(x)=∑∞k=0akxk=1+ax+a2x2+……⋯=1/(1−ax)
- For ak=(k+1),G(x)=∑∞k=0(k+1)xk=1+2x+3x2……⋯=1(1−x)2
- For ak=cnk,G(x)=∑∞k=0cnkxk=1+cn1x+cn2x2+……⋯+x2=(1+x)n
- For ak=1k!,G(x)=∑∞k=0xkk!=1+x+x22!+x33!……⋯=ex