CS2214  Assignment #3

CS2214 
Assignment #3

Submission: on the OWL web site of the course
Format of the submission. You must submit a single file which must
be in PDF format. All other formats (text or Miscrosoft word format) will
be ignored and considered as null. You are strongly encouraged to type
your solutions using a text editor. To this end, we suggest the following
options:
1. Miscrosoft word and convert your document to PDF
2. the typesetting system LATEX; see https://www.latex-project.org/
and https://en.wikipedia.org/wiki/LaTeX#Example to learn about
LATEX; see https://www.tug.org/begin.html to get started
3. using a software tool for typing mathematical symbols, for instance
http://math.typeit.org/
4. using a Handwriting recognition system such as those equipping tablet
PCs
Hand-writing and scanning your answers is allowed but not encouraged:
1. if you go this route please use a scanning printer and do not take a
picture of your answers with your phone,
2. if the quality of the obtained PDF is too poor, your submission will
be ignored and considered as null.
Problem 1 (Counting tree leaves) [25 marks] The set of leaves and the
set of internal vertices of a full binary tree are defined recursively as follows:
Basis step: The root r is a leaf of the full binary tree with exactly one
vertex r. This tree has no internal vertices.
Recursive step: The set of leaves of the tree T = T1 · T2 is the union of
the sets of leaves of T1 and T2. The internal vertices of T are the root
r of T and the union of the set of internal vertices of T1 and the set
of internal vertices f T2.
Use structural induction to prove that `(T), the number of leaves of a full
binary tree T, is 1 more than i(T), the number of internal vertices of T.
1
Problem 2 (Summation) [15 marks] Use mathematical induction to show
that
Σ
2n
j=0(2j + 1) = (2 n + 1)2
,
for all positive integers n. Provide detailed justifications for your answer.
Problem 3 (Counting binary strings) [20 marks] Consider all bit strings
of length 15.
1. How many begin with 00?
2. How many begin with 00 and end with 11?
3. How many begin with 00 or end with 10?
4. How many have exactly ten 1’s?
5. How many have exactly ten 1’s such as none of these 1’s are adjacent
to each other?
Provide detailed justifications for your answers.
Problem 4 (Counting permutations) [20 marks] Solve the following counting problems:
1. How many permutations of the eight letters A, B, C, D, E, F, G, H have
A in the second position?
2. How many permutations of the eight letters A, B, C, D, E, F, G, H have
A in one of the first two positions?
3. How many permutations of the eight letters A, B, C, D, E, F, G, H have
the two vowels after the six consonants?
4. How many permutations of the eight letters A, B, C, D, E, F, G, H neither begin nor end with D?
5. How many permutations of the eight letters A, B, C, D, E, F, G, H do
not have the vowels next to each other?
Provide detailed justifications for your answer.
Problem 5 (Counting triominos) [20 marks] We saw in class that every
2
n × 2
n board, with one square removed, could be covered with triominos.
Determine a formula counting the number of triominos covering such a truncated 2
n × 2
n board. Prove this formula by induction.
2