CSE 321: Discrete Structures

Assignment #5

February 8, 2001

Due: Wednesday, February 14

Assignment #5

February 8, 2001

Due: Wednesday, February 14

**Reading Assignment:** Rosen, Sections 4.1 - 4.5

**Problems:**

- 1.
- How many functions are there from the integers in the range
[1,..,k] to the boolean values 0, 1?
- 2.
- How many ways can three distinct numbers be chosen from
1,2,...,100 such that their sum is even?
- 3.
- Use the product rule to show that there are 2
^{2n}different truth tables for propositions in n variables. - 4.
- Section 4.1, exercise 42.
- 5.
- Section 4.2, exercise 30.
- 6.
- Section 4.3, exercise 46.
- 7.
- What is the coefficient of
*a*^{4}*b*^{6}in (*a*^{2}+*b*)^{8}? - 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?