Try our Free Online Math Solver!

MATH 145 SAMPLE PROBLEMS FOR EXAM 2
Problems
(1) Let a_{n} denote the number of strings of n digits from
{0, 1, 2}, containing no consecutive 1s or 2s. Find
a_{1}, a_{2}, a_{3}. Derive a second order homogeneous linear recurrence for a_{n}.
(2) Let d_{n} be the derangement sequence. Using the
asymptotic fact that converges rapidly to
1/e , find
a good approximation to the probability that a random shuffling of a 52card
deck will leave at most two
cards in their original position.
(3) Use bubble sort to arrange the list of numbers 7,4,6,3
in increasing order . List all the intermediate stages
of this process.
(4) In determining the generating function for the Catalan
numbers, we came up with the quadratic equation
, where f(x) is regarded as the unknown . The
quadratic formula then gave us
, an ambiguous result. Explain how to make
the correct choice for f(x).
(5) Show that if you remove any edge from a tree with at least two vertices , you create a disconnected graph.
(6) A certain graph G has n red vertices, n white
vertices, and n blue vertices. What is the maximum
number of edges it can have if no edge has both of its end vertices the same
color?
(7) A spanning tree T for a graph G is a tour if each
vertex of the tree has degree ≤ 2. Give a_{n} example of
a graph with no tour. Show that K_{n} has a tour.
(8) What is the total number of simple graphs you can make
with three vertices? How about 4 vertices? Is
there a way of counting the number of graphs on n + 1 vertices, once you know
the number for n vertices?
9 Let , be the simple
graph with vertices where the edges are
Is bipartite? How about planar?
Solutions
(1) Let a_{n} denote the number of strings of n digits from
{0, 1, 2}, containing no consecutive 1s or 2s. Find
a_{1}, a_{2}, a_{3}. Derive a second order homogeneous linear recurrence for a_{n}.
a_{1} = 3, a_{2} = 7, a_{3} = 17. Call a string good if it contains
no consecutive 1s or 2s. Each
string of length n + 1 is formed by adding a digit to the end of a string of
length n. Let
be the number of good strings of length n
that end in 0, 1, 2, respectively. Then
Now it is clear that
; goodness is neither ruined nor created by
affixing a 0. The only way to create a good (n + 1)length string ending in a 1
is for the n
string you affix the 1 to to be good and to end in either 0 or 2. This tells us
Likewise, . Clearly, by symmetry (switch 1s
and 2s in any given string),
. Let this number be
. Then
This gives us the initial value recurrence ,
(2) Let d_{n} be the derangement sequence. Using the
asymptotic fact that converges rapidly to
1/e , find
a good approximation to the probability that a random shuffling of a 52card
deck will leave at most two
cards in their original position.
The probability P is exactly
To get the desired approximation, we replace each by , obtaining
(3) Use bubble sort to arrange the list of numbers 7,4,6,3
in increasing order. List all the intermediate stages
of this process.
(4) In determining the generating function for the Catalan
numbers, we came up with the quadratic equation
, where f(x) is regarded as the unknown.
The quadratic formula then gave us
, a_{n} ambiguous result. Explain how to make
the correct choice for f(x).
Let . Then, as x > 0,
the denominator converges to 0, while the numerator
converges to 2. Then . Since every power
series in x is defined at x = 0,
g cannot be the generating function for . The
other possibility is . As
x > 0, both numerator and denominator converge to 0; so we may use
rule to
obtain
(5) Show that if you remove any edge from a tree with at least two vertices, you create a disconnected graph.
Suppose T be the tree in question; say T has p≥2 vertices.
Then the number of edges is
p − 1. Let the resulting graph be G. Then it has p vertices and p − 2 edges, so
cannot be a
tree. However, since removal of edges does not create cycles, G can have no
cycles; hence, if
it were connected, it would have to be a tree. We conclude that G cannot be
connected.
(6) A certain graph G has n red vertices, n white
vertices, and n blue vertices. What is the maximum
number of edges it can have if no edge has both of its end vertices the same
color?
Let the vertex set V be the disjoint union
, where R = W = B = n. Then
there are n^2 possible edges between vertices in R and vertices in W; likewise
for R and B ;
likewise for W and B. No two edge sets have any edges in common ; so the total
possible
number of edges is 3n^2.
(7) A spanning tree T for a graph G is a tour if each
vertex of the tree has degree ≤ 2. Give an example of
a graph with no tour. Show that has a tour.
The triod has no tour.
In fact, any tree with a vertex of degree ≥ 3 has no tour. As for
, list its vertices as
. Then there is a unique edge from
for each
1 ≤ i < n, and this path gives us a tour.
(8) What is the total number of simple graphs you can make
with three vertices? How about 4 vertices? Is
there a way of counting the number of graphs on n + 1 vertices, once you know
the number for n vertices?
Let be the number of
simple graphs on the vertices . Then
; since
there are no loops, there is just one vertex and no edges. With two vertices,
they’re either
adjacent or they aren’t; so . For three
vertices, you have either no edges (1 way), one
edge (3 ways), two edges (3 ways), or three edges (1 way). Hence
. Suppose we want
to count the number of simple graphs on vertex set
. We may specify any
such graph by determining the adjacency structure on vertices
and
then pick a set of vertices from to form a_{n}
edge with . Thus
. ( Solving this recurrence gives us
. Another way to get this result is
to line up the pairs of vertices ( ways) and
to decide which of these pairs are to receive
an edge (2 ways for each). This also gives us .)
9 Let , be the simple
graph with vertices , where the edges are
Is bipartite? How about planar?
The graph is not bipartite because it has a cycle
of odd length 3. It is
planar because it contains no subdivision of .
(This latter fact may be determined
by induction.)
Prev  Next 