Name:
Math 481 Final Exam Apr 27, 2021
Answer all questions 1–8 below (total 150 points). Show your work, or briefly explain the reasoning behind your answers.
You may leave answers in terms of symbols like n!,n, etc., except when directed to k
simplify in terms of arithmetic operations +, −, ×, ÷ only.
1. The following table is set with 6 plates, each either white, blue, or red:
a. (10pt) How many ways to choose colors white, blue, or red for the 6 plates? example: 2 white plates at the ends, 4 red plates in the middle.
b. (10pt) How many ways to arrange 3 white and 3 blue plates in the 6 places?
c. (10pt) How many ways to choose white, blue, or red for the 6 plates, with the restriction that two red plates may not be directly across from each other (in positions 1&5, 2&4, 3&6)?
d. (5pt) Let Γ be the symmetry group of geometric rotations and reflections of the table, considered as permutations of the 6 plates. Write each element of Γ in cycle notation.
e. (5pt) How many ways to choose colors white, blue, or red for the 6 plates, counting symmetric arrangements as the same (using the symmetry group above)?
2. (10pt) A deck has 52 cards of 13 face values and 4 suits. I deal a hand with 6 cards, consisting of three pairs, each pair having the same face value.
example: {2♥,2♦,5♠,5♦,J♣,J♥}.
How many possible three-pair hands? Briefly justify your reasoning and simplify your
answer in terms of arithmetic operations only.
3. (10pt) Let ak count the number of sets S ⊂ {1, 2, 3, 4, 5} whose sum is k. example: a6 = 3, counting the sets S = {1,5},{2,4},{1,2,3} which add to k = 5.
Find a simple product formula for the generating function f(x) = k≥0 akxk.
Hint: For Step 1, analyze the process of choosing S ⊂ {1,…,5} into a sequence of independent simple choices. Do NOT go on to Step 2; do NOT find a formula for ak.
4. Find the Taylor series f(x) = k≥0 akxk of the following functions. Show your work to make clear your methods.
a. (5pt) f(x) = (1 − 2x)6. Simplify to give ak in terms of arithmetic operations only. b. (5pt) f(x) = 1 , Simplify to an explicit formula for ak.
1−3x+2×2
5. Let G be a subdivision of the complete graph K5, meaning we place extra vertices
on some of the edges, turing these edges into paths.
a. (10pt) How many possible such G are there having a total of n vertices?
example: For n = 6, we can place one extra vertex on any of the 10 edges, so there are 10 such subdivisons.
b. (10pt) Draw an example of such a G which is bipartite.
c. (10pt) Draw an example of such a G which is planar, or show that G must be non-
planar using results we have covered.
6. (10pt) In the following table, the 9 boxes represent pairs of conditions on a graph T. If a given pair of conditions guarantees that T is a tree, write “Tree” in the box. Otherwise, draw an example of a graph which satisfies both conditions, but is not a tree.
T connected
T +e has cycle, any e∈/T
T has n vert, n−1 edges
T acyclic
T−e disconn, any e∈T
T has n vert, n−1 edges
7. (10pt) Give the Prufer sequence of the following tree:
1
/\ 23 /\/\
4567
8. (10pt) Let G be a graph with 6 vertices and all vertex degrees deg(v) = 4.
a. (10pt) Determine the number of edges of G, justifying your answer.
b. (10pt) Let the above G be planar. How many regions must a planar drawing have?
c. (10pt) Draw a graph G with the above properties (planar with 6 vertices of degree 4). Your drawing need not be planar: you may draw it as the edge-graph of a polyhedron.