This document provides solutions to discrete mathematics problems involving generating functions and graph theory concepts. Generating functions are used to solve recurrence relations and find explicit formulas for sequences. Graph theory questions involve identifying properties of specific graphs like the number of vertices, edges, degrees and determining if a sequence represents a valid degree sequence of some graph. Bipartite graphs and properties of regular graphs are also discussed.
This document provides solutions to discrete mathematics problems involving generating functions and graph theory concepts. Generating functions are used to solve recurrence relations and find explicit formulas for sequences. Graph theory questions involve identifying properties of specific graphs like the number of vertices, edges, degrees and determining if a sequence represents a valid degree sequence of some graph. Bipartite graphs and properties of regular graphs are also discussed.
Original Description:
Discrete Mathematical Structures with Recurrence Realtions
This document provides solutions to discrete mathematics problems involving generating functions and graph theory concepts. Generating functions are used to solve recurrence relations and find explicit formulas for sequences. Graph theory questions involve identifying properties of specific graphs like the number of vertices, edges, degrees and determining if a sequence represents a valid degree sequence of some graph. Bipartite graphs and properties of regular graphs are also discussed.
This document provides solutions to discrete mathematics problems involving generating functions and graph theory concepts. Generating functions are used to solve recurrence relations and find explicit formulas for sequences. Graph theory questions involve identifying properties of specific graphs like the number of vertices, edges, degrees and determining if a sequence represents a valid degree sequence of some graph. Bipartite graphs and properties of regular graphs are also discussed.
1. If G(x) is the generating function for the sequence {ak }, what is the generating function for each of these sequences? (1) 0, 0, 0, a3 , a4 , a5 , (assuming that terms follow the pattern of all but the first three terms) (2) a0 , 0, a1 , 0, a2 , 0, (3) a0 , 2a1 , 4a2 , 8a3 , 16a4 , Solution. (1) Define a new sequence {bn }nN as follows:
0, if 0 n 2; bn = an , if n 3. Then the generating function for {bn } is G(x) =
bn xn =
n=0
bn xn = a3 x3 + a4 x4 + + an xn + .
n=3
(2) Define a new sequence {bn } as follows:
0, if n = 2k + 1; bn = ak , if n = 2k. Then the generating function for {bn } is G(x) =
bn xn =
bn xn =
neven
n=0
b2k x2k =
k=0
ak x2k .
k=0
(3) We define bn = 2 an . Then the generating function for {bn } is
G(x) =
bn x n =
2n an xn
n=0
n=0
2. Using generating function to solve the recurrence relation ak = 7ak1 with the initial condition a0 = 6. 3. Using generating function to solve the recurrence relation ak = 3ak1 + 2 with the initial condition a0 = 1. Solution. Let G(x) = G(x)
= = = = =
k=0
ak xk be the generating function for the sequence {ak }. Then
1+x A B (A + B) x(3A + B) = + = . (1 x)(1 3x) 1 x 1 3x (1 x)(1 3x)
Hence
A+B 3A + B 1
= 1 = 1
Solving this system of linear equations, we obtain that
A = 1 B = 2. Hence G(x) =
k=0
k=0
k=0
X X X 1 2 + = xk + 2 3k xk = (2 3k 1)xk . 1 x 1 3x
Thus ak = 2 3 1 for k N. 4. Using generating function to solve the recurrence relation ak = 3ak1 +4k1 with the initial condition a0 = 1. P Solution. Let G(x) = k=0 ak xk be the generating function for the sequence {ak }. Then G(x)
5. Using generating function to solve the recurrence relation ak = 5ak1 6ak2 with the initial conditions a0 = 2 and a1 = 5. P Solution. Let G(x) = k=0 ak xk be the generating function for the sequence {ak }. Then G(x)
2 5x 2 5x A B (A + B) x(3A + 2B) = = + = . 6x2 5x + 1 (1 2x)(1 3x) 1 2x 1 3x (1 2x)(1 3x)
Hence
A+B = 2 3A + 2B = 5 Solving this system of linear equations, we obtain that
A = 1 B = 1. Hence G(x) =
k=0
k=0
k=0
X X X 1 1 + = 2k xk + 3k xk = (2k + 3k )xk . 1 2x 1 3x
Thus ak = 2k + 3k for k N. 6. Using generating function to solve the recurrence relation ak = ak1 + 2ak2 + 2k with the initial conditions a0 = 4 and a1 = 12. 7. Use generating functions to find an explicit formula for the Fibonacci numbers. 8. Draw the following graphs: (1) K6 (2) K3,4 (3) 3K3 (4) K2,2 + K3 (5) K2,3 . (6) A graph with vertex set {v1 , v2 , v3 , v4 , v5 } and edge set {v1 v2 , v1 v3 , v2 v4 , v2 v5 , v4 v5 } 9. In each of the graphs in Question 8 above, find the number of vertices, the number of edges, and the degree of each vertex. Identify all isolated vertices, end-vertices and remote vertices? 10. Write down the degree sequences of the graphs in Question 8. 11. How many edges does a complete bipartite graph Km,s have? What is the degree sequence of Km,n ? 12. Prove that if a graph G is a regular bipartite graph with partite sets V1 and V2 , then |V1 | = |V2 |. 13. Determine whether or not the following sequences are graphical. If so, construct a graph with the appropriate degree sequence. (1) 5, 5, 5, 3, 3, 2, 2, 2, 2, 2 (2) 4, 4, 3, 2, 1, 0 (3) 3, 3, 2, 2, 2, 2 (4) 3, 3, 2, 2, 2, 2, 1, 1 (5) 7, 4, 3, 3, 2, 2, 2, 1, 1, 1 14. Answer the following questions: (1) If G is a graph with 15 edges and G has 13 edges, how many vertices does G have? (2) How many vertices does a regular graph of degree four with 10 edges have? 15. Answer the following questions: (1) If the degree sequence of the graph G is 4, 3, 3, 2, 2, what is the degree sequence of G? (2) If the degree sequence of the graph G is d1 , d2 , , dn what is the degree sequence of G? 16. Let and let (1) (2)
G be a graph with v vertices and e edges. Let M be the maximum degree of the vertices of G m be the minimum degree of the vertices of G. Show that 2e/v m 2e/v M.
