MPCS 50103 — Problem Set 5

Instructions

This problem set will not be graded. Solutions to Problems will be posted on Canvas after Friday February 7.

Problems

1. Here is one possible username policy:
   • first initial, always a lowercase letter,
   • possibly followed by a number from 2 to 999,
   • surname, made up of lowercase letters, possibly truncated if the entire username exceeds length 8.
   For example, a possible username for myself is tng or t4ng, but not tng73 (order is incorrect). However, since my surname is short, it is below length 8. If my surname were longer, it would get truncated if the length of the entire username exceeded 8 characters. Here, lowercase letters are specified, but one can equivalently consider uppercase and lowercase to be equivalent (i.e. the usernames t4ng and T4NG are the same). In other words, we don't need to consider different cases as different letters.
   How many possible valid usernames of length exactly 8 are there under this policy?
2. We say a string $w$ avoids a string $u$ if $u$ does not occur in $w$ as a substring. How many binary strings of length 6 avoid the string $00$?
3. A DNA strand can be viewed as a string over the alphabet $\Sigma = \{A,C,G,T\}$ of DNA bases. While DNA is a double-stranded structure, it is often enough to consider one of the two strands as a string because the other strand is uniquely determined by Watson-Crick base pairs. We define the Watson-Crick complement $\theta(w)$ of a string $w$ inductively by:
   • if $w = \varepsilon$, then $\theta(\varepsilon) = \varepsilon$,
   • if $w = a \in \{A,C,G,T\}$, then $\theta(A) = T, \theta(C) = G, \theta(G) = C, \theta(T) = A$,
   • if $w = xa$ for $x \in \{A,C,G,T\}^*$ and $a \in \{A,C,G,T\}$, then $\theta(w) = \theta(a)\theta(x)$.
   In other words, the Watson-Crick function $\theta$ swaps each letter representing a base to the corresponding complementary base and reverses the string. For example, $$\theta(ATTACG) = CGTAAT.$$ How many DNA strings of length $n$ are equal to their own Watson-Crick complement (i.e. $w = \theta(w)$)?
4. A circular permutation is an arrangement of objects that "wraps around" or is "in a circle" and are considered equivalent with respect to rotation. For example, for the set $\{A,B,C,D\}$, the permutations $$\begin{matrix}(A,B,C,D) & (B,C,D,A) & (C,D,A,B) & (D,A,B,C) \end{matrix}$$ are all equivalent.
   1. How many circular permutations of $n$ objects are there?
   2. How many circular $r$-permutations of $n$ objects are there?

Exercises

1. Rosen 6.1 Exercises 42, 43
2. Rosen 6.1 Exercises 48-51
3. Rosen 6.1 Exercises 55, 57, 61
4. Rosen 6.3 Exercises 13, 15, 17
5. Rosen 6.3 Exercises 19, 20
6. Rosen 6.3 Exercises 23, 24
7. Rosen 6.3 Exercises 35-37