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?

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?

Well, we don't know how the flow and how to write this business case it will be a great help for us because we are stuck in are other assignments.1. Identify a company which is a major service provider for any of the mass marketed services in Bahrain operations and prepare an assignment on the following lines:a. The title of the assignment would...The COVID-19 Pandemic has highlighted the interdependence between countries and economies. While it is clear that it is having and may continue to have a significant economic impact on many (if not all)...ASSESSMENT BRIEFSubject Code and Title PUBH6008: Capstone A: Applied Research Project in Public HealthAssessment Assessment 3: Research proposalIndividual/Group IndividualLength 2,000 wordsLearning Outcomes...A33E33IVlEni I DnlErSubject Code and Title PUBH6013: Qualitative Research MethodsAssessment Assessment 3A: Investigation ReportIndividual/Group IndividualLength 1500 words (+/¦ 10%)Learning Outcomes This...Hi, I applied for one exam exemption at university for Bachelor Business Management and the student advisor told me that he needs -A description from the student with how they meet the learning objectives...Hi, I applied for one exam exemption at university for Bachelor Business Management and the student advisor told me that he needs -A description from the student with how they meet the learning objectives...**Show All Questions**