CMSC 27100 — Problem Set 5

Instructions

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

Problems

  1. A DNA strand can be viewed as a string over the alphabet $\Sigma = \{A,C,G,T\}$ of DNA bases.
    1. We say a string $w$ avoids a string $u$ if $u$ does not occur in $w$ as a substring. How many DNA strings of length 6 avoid the string $CC$?
    2. 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)$)?
  2. Canada held federal elections recently on October 21, 2019. The House of Commons comprises 338 seats, each representing a geographic district colloquially called a riding or circonscription depending on which official language you like. There are three major federal parties who run candidates in every riding in the country.
    1. How many different Parliaments can be formed assuming all elected members to the Commons belong to one of the three major parties?
    2. Canada is a parliamentary democracy, in which who gets to form government is contingent on who can hold the confidence in the House of Commons. Practically, this means controlling at least 50% + 1 of the seats in the Commons. Currently, this means the magic number is $\frac{338}{2} + 1 = 170$. How many different Parliaments result if one of the parties wins exactly 170 seats?
    3. Since there are three major parties, it can sometimes happen that no single party controls enough seats to form government on their own (in fact, this just happened). A possible but unlikely scenario involves each party getting approximately one third of the seats. With 338 seats, this means two parties would win 113 seats each and one would win 112. How many such Parliaments are there?
    4. In the province of Québec, there is a fourth major party, the souverainiste Bloc Québécois. The Bloc are a regional party, in that they only run candidates in the 78 ridings in Québec. How many different Parliaments can be formed when including the possibility of Bloquistes getting elected?
    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.
  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.2 Exercises 6, 7
  5. Rosen 6.2 Exercises 27
  6. Rosen 6.3 Exercises 13, 15, 17
  7. Rosen 6.3 Exercises 19, 20
  8. Rosen 6.3 Exercises 23, 24
  9. Rosen 6.3 Exercises 35-37