Problem 1 (Counting tree leaves) [25 marks] The set of leaves and the set of internal vertices of a full binary tree are de ned 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
2j=0n(2j + 1) = (2 n + 1)2;
for all positive integers n. Provide detailed justi cations for your answer.
Problem 3 (Counting binary strings) [20 marks] Consider all bit strings of length 15.
How many begin with 00?
How many begin with 00 and end with 11?
How many begin with 00 or end with 10?
How many have exactly ten 1’s?
How many have exactly ten 1’s such as none of these 1’s are adjacent to each other?
Provide detailed justi cations for your answers.
Problem 4 (Counting permutations) [20 marks] Solve the following count-ing problems:
How many permutations of the eight letters A; B; C; D; E; F; G; H have A in the second position?
How many permutations of the eight letters A; B; C; D; E; F; G; H have A in one of the rst two positions?
How many permutations of the eight letters A; B; C; D; E; F; G; H have the two vowels after the six consonants?
How many permutations of the eight letters A; B; C; D; E; F; G; H nei-ther begin nor end with D?
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 justi cations for your answer.
Problem 5 (Counting triominos) [20 marks] We saw in class that every 2n 2n board, with one square removed, could be covered with triominos. Determine a formula counting the number of triominos covering such a trun-cated 2n 2n board. Prove this formula by induction.
2
