MATH 239: Assignment 4
Submission due: February 10 at 11:00AM EST
Every question has 1 mark dedicated to presentation.
Question 1. (9 marks) Let $S$ be the set of binary strings that contain only blocks of length one or two and that have no two consecutive blocks of length one.
(a) (3 marks) Let $S_{0}, S_{1}, S_{00}, S_{11}$ denote the set of binary strings in $S$ that end with the block $0,1,00$, and 11 respectively. Prove that these sets satisfy the following relations.
$$
\begin{aligned}
S &={\varepsilon} \cup S_{0} \cup S_{1} \cup S_{00} \cup S_{11} \
S_{0} &=\left({\varepsilon} \cup S_{11}\right){0} \
S_{1} &=\left({\varepsilon} \cup S_{00}\right){1} \
S_{00} &=\left({\varepsilon} \cup S_{1} \cup S_{11}\right){00} \
S_{11} &=\left({\varepsilon} \cup S_{0} \cup S_{00}\right){11} .
\end{aligned}
$$
(b) (3 marks) How many binary strings are there in $S$ with length $n$ ? Express your answer as the coefficient of a generating series. Your generating series should be of closed form. (You do not need to justify that the expressions (1)-(5) are unambiguous.)
(c) (2 marks) Find a linear recurrence with initial conditions for the number of binary strings in $S$ of length $n$.
Question 2. (6 marks) Let $S$ be the set of binary strings which do not have 1011 as a substring. Let $T_{1}$ be the set of binary strings that have exactly one copy of 1011 occurring in the last four bits. Let $T_{2}$ be the set of binary strings that have exactly two copies of 1011 occurring in the last seven bits.
(a) (3 marks) Determine three unambiguous recursive relations between $S, T_{1}$, and $T_{2}$. Justify your equations and the unambiguity. (Alternatively, you may write three syntactic recursive expressions for $\mathrm{S}, \mathrm{T}{1}$, and $\mathrm{T}{2}$ which produce sets $S, T_{1}$, and $T_{2}$ respectively. You do not need to justify that $\mathrm{S}, \mathrm{T}{1}$, and $\mathrm{T}{2}$ produce $S, T_{1}$, and $T_{2}$.)
(b) (2 marks) Using part (a), determine the generating series for $S$ with respect to the lengths of the strings.
Question 3. (9 marks) Eastern grey squirrels are native to Waterloo. They breed up to two times per year and their litter size is usually between 1 and 4, but can be up to 8. Female squirrels do not usually mate until they are at least 1 year old. For simplicity, let us assume that female squirrels produce 3 female children per year, unless it is the first year after they were born, in which they do not produce any offspring. That is, if a female squirrel is born in year $n$, then it has no children until year $n+2$. If a female squirrel is born in year $n$ we refer to it as a child in year $n+1$ and then an adult in year $n+2$ (when it has children for the first time). Lastly, we assume that no squirrels die.
Suppose we have a contained population of squirrels with 2 females (one adult, one child) to start and always a sufficient number males. Let $a_{n}$ denote the number of female squirrels at the end of year $n$. So $a_{0}=2$ and year 1 begins with 1 female adult and 1 female child.
(a) (1 mark) Determine $a_{1}$ and write a recursive formula for $a_{n}$ where $n \geq 2$.
(b) (2 marks) Let $A(x)=\sum_{n \geq 0} a_{n} x^{n}$. Express this generating series as a rational function (i.e. in closed form).
(c) (4 marks) Determine $\left[x^{n}\right] A(x)$ in terms of $n$, in closed form. (Hint: use partial fractions.)
(d) (1 mark) How many female squirrels are there after 8 years? You can use a calculator. (Eastern grey squirrels live about 6 years on average, but in ideal conditions can live up to 20 . Since this population is contained somehow, the assumption that no squirrels die seems reasonable when we are looking for $a_{8}$.) Note. This problem is motivated by Fibonacci’s rabbit problem which appeared in Fibonacci’s book Liber Abaci (1202). The solution to the rabbit problem is what we know today as the Fibonacci sequence.
Introduction to graph theory: colourings, matchings, connectivity, planarity. Introduction to combinatorial analysis: generating series, recurrence relations, binary strings, plane trees. [Note: Offered: F,W,S]Course ScheduleSpring 2022Winter 2022Fall 2021Spring 2021SectionClassEnrolledTimeDateLocationInstructorLEC 0015957115/12011:30 AM – 12:20 PMMTWThFSSuRCH 103Jane GaoLEC 0025958115/1201:30 PM – 2:20 PMMTWThFSSuRCH 103Debbie LeungLEC 0036183110/12011:30 AM – 12:20 PMMTWThFSSuMC 4061Kanstantsin PashkovichLEC 00487540/200LEC 0049670113/1204:30 PM – 5:20 PMMTWThFSSuMC 4021Shayla RedlinTUT 101595954/608:30 AM – 9:20 AMMTWThFSSuMC 4042TUT 102596056/609:30 AM – 10:20 AMMTWThFSSuMC 4042TUT 103618459/603:30 PM – 4:20 PMMTWThFSSuMC 4058TUT 104962057/6010:30 AM – 11:20 AMMTWThFSSuMC 4042TUT 105962158/6012:30 PM – 1:20 PMMTWThFSSuMC 4041TUT 106962257/603:30 PM – 4:20 PMMTWThFSSuMC 4041TUT 107967155/609:30 AM – 10:20 AMMTWThFSSuMC 4058TUT 108967256/601:30 PM – 2:20 PMMTWThFSSuMC 4058TST 2015966453/4804:30 PM – 6:20 PMMTWThFSSuMar 10th
