Discrete Structures Anna Karlin
CSE 321, Spring 2000

Homework #6
Due Wednesday, May 17

Reading: Rosen, Sections 4.4 - 4.5, 6.1, 6.5

1.
Rosen, Section 4.1, problem 16.

2.
How many functions are there from the integers in the range [1,..,k] to the boolean values {0, 1}?

3.
How many ways can 3 exams be scheduled on a 5-day period such that no two exams are held the same day?

4.
How many ways are there to seat 5 children in a row of 12 chairs?

5.
How many ways can three distinct numbers be chosen from 1,2,...,100 such that their sum is even?

6.
How many ways are there of seating n people around a circular table? (Two seatings are considered the same if one is simply a circular shift of the other.)

7.
Rosen, Section 4.2, problem 4.

8.
How many ways are there to arrange the letters in the word MISSISSIPPI?

9.
A palindrome is a word that reads the same forwards and backwards (e.g., ``Anna''). How many six-letter palindromes can be made from the English alphabet?

10.
How many 5 card hands (from a 52 card deck) have the same number of Spades and Hearts?

11.
What is the coefficient of a4b6 in (a+b)10?

12.
What is the coefficient of a4b6 in (a2+b)8?

13.
Extra Credit: Prove that

\begin{displaymath}\sum_{1\le i \le n} i \left(\begin{array}{c}n\\ i\end{array}\right) = n2^{n-1}.\end{displaymath}

Hint: Use the binomial theorem.

14.
Extra Credit: 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?

15.
Extra Credit: 23 people come to a dinner party. They are to be seated at a circular table. Suppose that there is a nametag at each place at the table and suppose that nobody sits down in their correct place. Show that it is possible to rotate the table so that at least two people are sitting in the correct place. (Hint: the pigeonhole principle.)