Description

CS 70 Discrete Mathematics and Probability Theory

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Strings
How many different strings only contains A,B,C? And how many such strings contains at least one of each characters?
2 Palindromes
How many 5-digit palindromes are there? (A palindrome is a number that reads the same way forwards and backwards. For example, 27872 and 48484 are palindromes, but 28389 and 12541 are not.)
3 Maze in general and Trees too!!!
Given an maze of sidelength n where one starts at (0,0) and goes to (n,n).
(a) How many shortest paths are there that go from (0,0) to (n,n)?
(b) Extending the width by 1, how many shortest paths are there that go from (0,0) to (n−1,n+1).
(c) Now consider shortest paths that meet the conditions which only use to points (x,y) where y ≤ x. That is, the path cannot cross line y = x.
i. Give an expression using part (a) and (b), that counts the number of paths. (Hint: consider what happens after a shortest that crosses y = x at (i,i), that is, the remaining path starting from (i,i+1) and then continuing to (n,n). If in the remainder of the path, one exchanges the y-direction moves with x-direction moves and vice versa, where does one end up?
ii. A different tack is to derive a recursive formula. We call these paths n-legal paths for a maze of sidelength n, and let Fn be the number of n-legal paths.
Consider a path, and let i < n be the largest value where the path contains (i,i), argue the number of paths is then Fi ∗Fn−i−1.
(Hint: if i = 0, what are your first and last moves, and where is the remainder of the path allowed to go.)
iii. Give a recursive formula for the number of spanning trees of a complete graph Kn for n ≥ 3, where each non-root node has degree 3 or 1, and at most 1 node has degree 2?
Two trees are different if and only if either left-subtree is different or right-subtree is different.
(Notice something about your formula and the maze problem. Neat!)