COS 341, October 8, 1997Handout Number 9
Homework Set 4
Reading Assignments Read Chapter 7.
Written Assignments Do exercises 34 and 35 in Section 5.7. Do exercises 2, 9, 14 and 29 in Section 6.6. (You should use the Inclusion-Exclusion technique to solve these problems in Section 6.6.)
Special Problem 1(Counted as 1 exercise)
A linear arrangment of the letters in 
is said to be pretty, if it does not contain
any of HE, ME, YOU as a substring. For example,
AYEMOHIU is pretty, but AMEYOUHI isn't. How many
pretty arrangments are there?
Special Problem 2 (to be counted as 2 exercises) In Mathville, there are exactly n one-way streets from west to east (named as Streets 1 to n), and n one-way streets from south to north (named as Avenues 1 to n). Let A be the south-west corner and B be the north-east corner of town (thus A is at the intersection of 1st Street and 1st Avenue, and B is at the intersection of nth Street and nth Avenue). Assume that Alice wants to go from point A to point B, and she obeys the one-way traffic regulation.
Note that the last leg of any path must be either the n-th Street or the n-th Avenue. Let X be the number of blocks that Alice travels on this last leg. Question: What is the expected value of X, assuming that all paths are equally likely to be taken? What is the variance of X? (Your answer should be a closed-form expression of n.)