CSE 321: Discrete Structures
February 8, 2001
Due: Wednesday, February 14
Reading Assignment: Rosen, Sections 4.1 - 4.5
- How many functions are there from the integers in the range
[1,..,k] to the boolean values 0, 1?
- How many ways can three distinct numbers be chosen from
1,2,...,100 such that their sum is even?
- Use the product rule to show that there are 22n different
truth tables for propositions in n variables.
- Section 4.1, exercise 42.
- Section 4.2, exercise 30.
- Section 4.3, exercise 46.
- What is the coefficient of a4b6 in (a2+b)8?
- Imagine a town with East-West streets numbered 1 through n, and
North-South avenues numbered 1 through m. A taxi cab picks up a
passenger at the corner of 1st street and 1st avenue. The passenger
wishes to be delivered to n-th street and m-th avenue. It is quite
clear that the passenger will be angry if the cab chooses a route
longer than (n-1)+(m-1) blocks, so we won't allow the cabby to take
a route longer than this. In other words, the cabby must always be
increasing his street number or his avenue number. Suppose that
there is an accident at i-th street and j-th avenue. How many routes
can the cabby take that avoid the intersection with the accident?