0% found this document useful (0 votes)
263 views3 pages

Tutorial 9 Sols

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.

Uploaded by

Ravi Prasad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
263 views3 pages

Tutorial 9 Sols

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.

Uploaded by

Ravi Prasad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

MATH 236: Discrete Mathematics with Applications

TUTORIAL 9: 9 May, 2013


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

a0 + a1 x + a 2x2 + + ak xk +
1 + (3a0 + 2)x + (3a 1 + 2)x2 + + (3ak1 + 2)xk +
1 + (3a0 x + 3a1 x2 + + 3ak1 xk + ) + (2x + 2x2 + + 2xk + )
1 + 3x(a0 + a1 x + +) + 2x(1 + x + x2 + + xk1 + )
2x
1 + 3xG(x) + 1x

Solving for G(x), we have


G(x) =

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)

=
=
=
=
=

a0 + a1 x + a2 x2 + + ak xk +
1 + (3a0 + 1)x + (3a 1 + 4)x2 + + (3ak1 + 4k1 )xk +
1 + (3a0 x + 3a1 x2 + + 3ak1 xk + ) + (x + 4x2 + + 4k1 xk + )
1 + 3x(a0 + a1 x + +) + x(1 + 4x + 42 x2 + + 4k1 xk1 + )
x
1 + 3xG(x) + 14x

Solving for G(x), we have


G(x) =
Therefore,
G(x) =

1
.
1 4x

4k xk

k=0

and so ak = 4k for all k N.


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)

=
=
=
=
=
=

a0 + a1 x + a 2x2 + + ak xk +
a0 + a1 x + (5a1 6a0 )x2 + (5a2 6a1 )x3 + + (5ak1 6ak2 )xk +
2 + 5x + (5a1 x2 + 5a2 x3 + + 5ak1 xk + ) + (6a0 x2 6a1 x3 6ak2 xk )
2 + 5x + 5x(a1 x + + ak xk + ) 6x2 (a0 + a1 x + + ak xk + )
2 + 5x + 5x(G(x) a0 ) 6x2 G(x)
(5x 6x2 )G(x) + (2 5x)

Solving for G(x), we have


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.

You might also like