Math 344, Fall 2020: Final
There are nine questions, each worth 10 points.
Best of Luck!
Question 1 (10 points; 1 point for each question; There is no need to show work)
1. How many subsets of {1,...,n} have an even number of elements?
2. How many words can you form with 1 a, 2 b’s, 3 c’s and 4 d’s, assuming that you have to use all theletters?
3. We have a huge jar with 1000 marbles each of 10 different colors (making 10,000 marbles in total). Wepick out 50 marbles at random. How many possibilities are there for the set of marbles we pick?
4. We have the jar of marbles as above. An unfortunate individual is given the tedious job of arrangingall the 10,000 marbles in a line. How many different possible lines can this person create?
5. Assume that n = k. How many injective functions are there from the set {1,...,n} to the set {1,...,k}?
6. How many integer partitions of n are there into at least n - 2 parts?
7. How many integer partitions of n are there into at most at most 3 parts?
8. You have two identical red beads and ten identical blue beads. In how many ways can you arrangethem in a circle?
9. Given a fixed value of n, what is the value(s) of k such that is the largest possible.
10. Which number is larger: p(1000) or 21000?
Question 2
Prove that for all positive n 1, we have
.
Question 3
How many n × n square matrices are there, with entries 0 or 1, such that each row and each column has an even sum.
Question 4
Let an be the number of compositions of n into parts that are at least 2. (So a3 = 1 since we can only write 3 = 3, and a4 = 2 since 4 = 2 + 2 = 4.) Give a formula relating an, an-1, and an-2.
Question 5
Let An be the total number parts that are equal to 1 in all compositions of n. So A1 = 1, A2 = 2, A3 = 5, and A4 = 12. Prove that for all n = 2, we have An+1 = 2An + 2n-2.
Question 6 (10 points; 1 point for each part; There is no need to show work)
1. Let G be a simple graph. Express the sum of the degrees of the vertices of G in terms of the number of edges.
2. True or False : Let G be a simple connected graph with an Eulerian walk. Then there exists a vertex v of G, such that the graph obtained by removing v from G also has an Eulerian walk.
3. Let n = 2 and k = n be fixed. How many edges does a forest with n vertices and k connected components have?
4. True or False : Let G be a simple connected graph, and let e1 and e2 be two edges of G. There exists a spanning tree for G that contains the edges e1 and e2.
5. True or False : A simple bipartite graph on 16 vertices must have = 60 edges.
6. True or False : Every simple graph has two vertices of the same degree.
7. True or False : Every tree is 2-colorable.
8. What can you say (in one sentence) about cycles in a simple bipartite graph?
9. True or False : The graph K2,100 is not planar.
10. Let n be an integer. How many nonisomorphic trees on n vertices have an Eulerian trail?
Question 7
Let G be a connected simple graph that is regular, i.e., every vertex of G has the same degree d. Assume that d is even. Let e be any edge of G. Prove that the graph G - e, obtained by deleting e from G, is still connected.
Question 8
Let G = (V,E) be a bipartite graph, where V = X ? Y , and the edges connect vertices of X with vertices of Y . Assume that for all T ? X, we have |N(T)| = |T| - 1, where N(T) denotes the set of neighbors of T. Prove that G contains a matching of size |X| - 1. (I.e., there exists a set of vertex disjoint edges of size
|X| - 1.)
Question 9
Does there exist a simple planar graph each of whose vertices has degree 6?