Administrivia

• Your assignment must be submitted as a single PDF file through cuLearn
• Late assignments will not be accepted under any circumstances. If you're unable to complete the assignment due to a valid and documented medical or personal situation then the weight of this assignment can be shifted to the weight of the remaining assignments.
• You are encouraged to collaborate on assignments, but at the level of discussion only. When writing your solutions, you must do so in your own words.
• Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams.
• When writing your solutions:
  • You must justify your answers.
  • The answers should be concise, clear and neat.
  • When presenting proofs, every step should be justified.

Meat

1. ID

1. Make sure the first thing on page 1 of your assignment is your name and student number.

2. Non-Local Strings

For this question, a block is a sequence of 20 characters, where each character is one of the 26 lowercase letters a-z. For example, these are blocks:

iwpiybhunrplsovrowyt
rpulxfsqrixjhrtjmcrr
fxfpwdhwgxtdaqtmxmlf

1. How many different blocks are there?
2. A block is squarefree if no character appears two times consecutively. The first and third example above are squarefree, but the second example is not because of the two consecutive occurrences of r. How many squarefree blocks are there?
3. A block is non-local if the number of characters between any two occurrences of the same character is at least 2. The first example above is non-local. The second example is not, because there are two occurrences of r with no characters between them. The third example is not because there are two occurrences of m with only one character between them. How many non-local blocks are there?
4. A block is $k$-non-local if the number of characters between any two occurrences of the same character is at least $k$. Write a formula for the number of $k$-non-local blocks that is valid for any $k\in\lbrace 0,\ldots,20\rbrace$.

Sanity check: The formula you get for 2.4 gives the answer to 2.2 when $k=1$ and gives the answer to 2.3 when $k=2$.

3. Restricted Bitstrings

An $n$-bit binary string is a sequence of length $n$ over the alphabet $\lbrace 0,1\rbrace$.

1. How many $n$-bit binary strings are there?
2. How many $n$-bit binary strings $b_1,\ldots,b_{n}$ are there such that $b_1b_2\neq 00$? In other words, how many $n$-bit binary strings don't begin with $00$?
3. How many $n$-bit binary strings $b_1,\ldots,b_{n}$ are there such that $b_1b_2\neq 00$ and $b_2b_3\neq 11$?
4. How many $n$-bit binary strings $b_1,\ldots,b_{n}$ are there such that $b_1b_2\neq 00$ and such that $b_2b_3\neq 01$?

4. Bar Management

Molson currently sells 41 different brands of beer in Canada. Labatt currently sells 17 different brands.

1. The manager at Mike's Place needs to choose 5 Molson brands and 5 Labatt brands to sell. How many options do they have?
2. The 10 beers (5 Labatt, 5 Molson) selected in the previous question must be placed in a line on a display shelf so that no two Molson products are adjacent and no two Labatt products are adjacent. How many ways are there to do this?
3. Continuing from the previous question, suppose two of the brands selected by the manager were (Labatt) 50 and (Molson) Export. The display shelf can not have a bottle of 50 adjacent to a bottle of Export. How many ways are there to do this while still avoiding two adjacent Molson products and two adjacent Labatt products?
4. How many of the arrangements from the previous question have the bottle of 50 and the bottle of Export among the first (leftmost) 5 bottles?

5. ABC-Free Permutations

Consider permutations of the 26-character lowercase alphabet \[ \Sigma = \lbrace a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z \rbrace \enspace . \]

1. In how many of these permutations do $a,b,c$ occur consecutively and in that order?
2. In how many of these permutations does $a$ appear before $b$ and $b$ appear before $c$?

6. Imprecise Counting - Long Runs in Binary Strings

Let $n=2^k$ for some positive integer $k$ and consider the set $S_n$ of all $n$-bit binary strings.

1. Let $c$ be an integer in $\lbrace 0,\ldots,n-k\rbrace$. Consider any $j\in\lbrace 1,\ldots,n-k-c+1\rbrace$. How many strings $b_1,\ldots,b_n\in S_n$ have $b_j,b_{j+1},\ldots,b_{j+k+c-1}=00\ldots 0$? In other words, how many strings in $S_n$ have $k+c$ consecutive zeros beginning at position $j$?
2. For each $j\in\lbrace 1,\ldots,n-k+c+1\rbrace$, let $X_j$ be the subset of $S_n$ consisting only of the strings counted in the previous question. Show that \[ \sum_{j=1}^{n-k-c+1}|X_j| \le 2^n / 2^c \enspace . \] (Hint: Remember that $2^k=n$.)
3. This leads to the following conclusion: The number of $n$-bit binary strings containing a substring of $k+c$ consecutive zeros is at most $2^n/2^c$. Explain how to arrive at this conclusion.