Permutations and combinations Permutations of sets combinations of sets circular permutation Permutations and Combinations of multisets Formulae o inclusion-exclusion principle generating functions integral solutions of the equation ◆ example, exercise
2. Permutations and Combinations Permutations of sets, Combinations of sets circular permutation Permutations and Combinations of multisets Formulae inclusion-exclusion principle generating functions integral solutions of the equation example，exercise
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
YIlI Graphs 1. Graph terminology The degree of a vertex, 8(G),A(G), Theorem 5.1 5.2 k-regular, spanning subgraph, induced subgraph by v∈V the complement of a graph g, connected, connected components strongly connected, connected directed weakly connected
III Graphs 1. Graph terminology The degree of a vertex，(G), (G), Theorem 5.1 5.2 k-regular, spanning subgraph, induced subgraph by V'V the complement of a graph G, connected, connected components strongly connected, connected directed weakly connected
2. connected. Euler and hamilton paths e Prove g is connected (1)there is a path from any vertex to any other vertex .(2 )Suppose G is disconnected +1) connected components(k>1) 2There exist u, v such that is no path between uv
2. connected, Euler and Hamilton paths Prove: G is connected (1)there is a path from any vertex to any other vertex (2)Suppose G is disconnected 1) k connected components(k>1) 2)There exist u,v such that is no path between u,v