Applications of Inclusion -Exclusion principle theorem 3.15, theorem 3. 16,example, exercise Applications generating functions and Exponential generating functions e=1+x+x2/2!+.+x"/n!+…; x+x2/2!++xm/n!+,=ex-1 ex=1-x+x2/2!+…+(-1)"x"/n!+……; 1+x2+…+x2n(2n)+…=(ex+e)/2; x+x3/3!+…+x2am+1(2n+1)+…,=(ex-e-)2 +3. recurrence relation o Using Characteristic roots to solve recurrence relations USing Generating functions to solve recurrence relations ◆ example, exercise Applications of Inclusion-Exclusion principle  theorem 3.15,theorem 3.16,example,exercise  Applications generating functions and Exponential generating functions  e x=1+x+x2 /2!+…+xn /n!+…;  x+x2 /2!+…+xn /n!+…=ex -1;  e -x=1-x+x2 /2!+…+(-1)nx n /n!+…;  1+x2 /2!+…+x2n/(2n)!+…=(ex+e-x )/2;  x+x3 /3!+…+x2n+1/(2n+1)!+…=(ex -e -x )/2;  3. recurrence relation  Using Characteristic roots to solve recurrence relations  Using Generating functions to solve recurrence relations  example，exercise