MATH 1043 Discrete Mathematics Assignment

QUESTIONS

1. To do this question, please refer to the notes I wrote for our course, specifically to Proposition 15 on page 75, and Proposition 16 on page 77, and examples that follow.

Find the theta notation for each item below, and justify your answers based on Propositions 15 and 16.

1. f(n) = 1 + 2n + 3n^2.
2. g(n) = (2n + 3)(4 + 5 ln n).
3. h(n) = n^3 + 2n^2 + 5 /5n^2 + n + 1

[5+5+5=15 marks]

2. A jeweler is commissioned to craft a necklace containing six precious or semi precious stones: Amethyst, Beryl, Citrine, Diamond, Emerald, and Friedelite (yes, these are real gemstones). These stones will be arranged sequentially in a circular pattern, in some order.

How many possible different necklaces can the jeweler craft? Justify your answer. [10 marks]

3. Let’s anagram! Justify your answers.

1. How many anagrams are there of the word SUBJECT?
2. My friend had a cat named REGRET (seriously). How many anagrams?
3. How many anagrams can we make from the characters of the word APPROPRIATE if we are only allowed to use four characters?

[2 + 2 + 6 = 10 marks]

4. A regular die has six faces, numbered 1 to 6. Roll the die seven times consecutively, and record the (ordered) sequence of die rolls; we call that an outcome.

1. How many outcomes are there in total?
2. How many outcomes are there where 3 is not present?
3. How many outcomes are there where 3 is present exactly once?
4. How many outcomes are there where 3 is present at least twice?
5. How many outcomes are there where 1 is present exactly once, 2 is present exactly twice, and 4 is present exactly four times?

[2 + 2 + 2 + 2 + 2 = 10 marks]

5. Consider the equation x1 + x2 + x3 = 20, where x1, x2, and x3 are integers. How many solutions are there

1. if x1, x2, x3 ? 0?
2. if x1, x2, x3 ? 1?
3. if 0 <=x1 <=3, x2 >=0, x3 >=0?

[5+5+5=15 marks]

6. Solve the recurrence relation
an+2 - 2an+1 -15an = 0, a0 = 3, a1 = -1.

[10 marks]

7. You borrow $300,000 to buy a house. The finance rate is 4% per year. You will make payments over 10 years. At the end of each month you will repay an amount b (in dollars), to be determined. Let an be the amount of money you owe at the end of month n. Every month that goes by will increase the amount you owe (because of interest), but as you pay the amount b, the amount you owe will decrease. Your first payment will be at the end of the fifirst month. Please answer the following questions.

1. Explain (in English, no formulas are necessary) why we should put a0 = 300, 000.
2. Explain why a120 = 0.
3. What is the monthly interest rate?
4. How much money will you owe at the end of the first month, before you make your payment? How much money will you owe at the end of the first month after you make your payment?
5. Find a recurrence relation for the amount you owe. Your formula will contain an+1, an, the interest rate (in some way), and the unknown value b. Use as a model the example I described in class of money that you deposit in a bank account.
6. Write down the solution formula for your recurrence relation. (You may use the solution formula we developed during lectures, but be careful to adapt it correctly.)
7. Determine the value of b, using the available information.

[20 marks]

8. The matrix
 Is the adjacency matrix of a graph G.

1. Draw a picture of this graph, labeling the vertices from 1 to 4.
2. What is the degree of each vertex?

[5 + 5 = 10 marks]