Instructions
This problem set is due on Friday November 15, 2019 at 23:59. 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
- 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?
- Using a combinatorial argument, prove that $$\binom n k \binom k r = \binom n r \binom{n-r}{k-r}.$$
- How many distinguishable permutations of the string "MISSISSAUGA" are there?
- 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$.
Exercises
- Prove Pascal's Identity algebraically.
- Prove the Binomial theorem via induction.
- Rosen 6.4 Exercises 9
- Rosen 6.4 Exercises 17
- Rosen 6.4 Exercises 21, 29
- Rosen 6.5 Exercises 29
- Rosen 6.5 Exercises 47-49
- Rosen 6.5 Exercises 59
- Rosen 6.5 Exercises 63
- Rosen Chapter 6 Supplementary Exercises 52