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?

Assessment 1 InformationSubject Code: MBA600Subject Name: Capstone: StrategyAssessment Title Assessment Type: Competitive Advantage Video Project Individual Recorded VideoLength: 10 minutes (no more)Weighting:...In assessment two students are required to write a 2,000 word essay and a 50-100 word reflection relating to the given case study (see detailed instructions below) and submit it via the assessment two...[Assignment 2] Explain Cost of quality project planning in a company. Prepare a project plan for implementing cost of quality for the company you choose which has at least one ISO. The plan should give...HOLMES INSTITUTEFACULTY OFHIGHER EDUCATIONAssessment Details and Submission GuidelinesTrimester T1 2021Unit Code HS1031Unit Title Introduction to ProgrammingAssessment Type IndividualAssessment Title Individual...CRIT3000 S1_2021 Complex Nursing Practice 1: Skills Assessment (Report) Marking Rubric What do we need to do?Unit Learning Outcome assessed:Use clinical knowledge and skills to conduct a comprehensive...Due DateTo Turnitin by Week 8, 10:00 pm Sydney, Australia Time, Thursday, 22 April 2021.Length1200 words. The 1200-word limit includes all text added to the template, including main text, title, heading,...Assessment 2: Case StudyDue date: Session 12Group/individual: IndividualWord count / Time provided: 2500 WordsWeighting: 30%Unit Learning Outcomes: ULO3, ULO4, ULO5Assessment Details:The case study will...**Show All Questions**