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?

BUS368Innovation Management and DigitalTransformationTutor-Marked AssignmentJuly 2022 PresentationBUS368 Tutor-Marked AssignmentSINGAPORE UNIVERSITY OF SOCIAL SCIENCES (SUSS) Page 2 of 5TUTOR-MARKED ASSIGNMENT...The student should present his/her work for each section using both text and images.The sources can be from class lectures, assignments, etc., or from other sources. Don't forget to cite the sources.One...Page 1 of 3COM10007 Professional Communication PracticeAssessment: WorksheetIndividual: Individual AssignmentDue Date: Week 8Upload either Word file or PDF file on Canvas(check date on Canvas)Mark: 20%...Assignment – Semester 2, 2022© Governance Institute of Australia 1 AssignmentSemester 2, 2022Applied Corporate LawInstructions1 Your assignment should address the question(s) and stated learning outcomes...STRUCTURE OF THE FINAL PAPER and DELIVERABLESThis is a guideline to build your paper. Thus, a solid structure will look like organized in the following sections. A good paper should generally include all...CSCI 620 Homework 2 Fall 20221CSCI 620 Homework 2Due: September 23, 2022Points: 35Do the following problems; show your work:Problem A (3 Points)Consider a 2 MB 4-way set associative cache. Suppose a block...Activity Submission 2Research some recent company cyber security breaches and choose two of these companies where data breaches have occurred. Explain the reasons for these breaches and discuss how they...**Show All Questions**