CSE 321: Discrete Structures
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²ⁿ 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⁴b⁶ in (a²+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?