MPCS 50103 — Problem Set 6

Instructions

This problem set is due on Wednesday February 19, 2020 at 17:00. Solutions to Problems should be submitted on Gradescope and will be graded. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

  1. How many non-negative integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 17$, where $x_i \geq 2$ for $i = 1,2,3,4$.
    1. Show that given any six natural numbers between 1 and 10, there are at least two which sum up to 11.
    2. Generalize the above result for natural numbers between 1 and $n$.
  3. Using a combinatorial argument, prove that $$\binom n k \binom k r = \binom n r \binom{n-r}{k-r}.$$
  4. Consider strings over the alphabet $\Sigma = \{0,1\}$. Recall that a word $w = uv$ is an abelian square if $|u|_a = |v|_a$ for all $a \in \Sigma$. In other words, $v$ contains exactly the same number of each symbol as $u$. For example, the string $011101$ is an abelian square with $u = 011$ and $v = 101$ and $|u|_0 = |v|_0 = 1$ and $|u|_1 = |v|_1 = 2$.
    How many abelian squares of length $n$ are there?

Exercises

  1. Prove Pascal's Identity algebraically.
  2. Prove the Binomial theorem via induction.
  3. Rosen 6.2 Exercises 5, 7
  4. Rosen 6.2 Exercises 27
  5. Rosen 6.2 Exercises 43
  6. Rosen 6.4 Exercises 9
  7. Rosen 6.4 Exercises 17
  8. Rosen 6.4 Exercises 21, 29
  9. Rosen 6.5 Exercises 29
  10. Rosen 6.5 Exercises 47-49
  11. Rosen 6.5 Exercises 59
  12. Rosen 6.5 Exercises 63

Reflection

Once in a while, there will be a reflection section attached to a problem set. These are meant to give you an opportunity to reflect on your relationship with the course and the things you're learning. I will be reading and responding to your submissions, so this will also allow us to establish a dialogue about your learning in this course.

Completion of this part is optional but is worth an extra 10 marks in total. These will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness".

  1. What has been your favourite result so far?
  2. What is something that you've learned or improved on since this class started?
  3. Think back to your goals for this class. How do you feel about your progress? Do you need to revise them? What do you think you would need to work on to meet them?
  4. Is there anything else you would like me to know at this point?