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
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.)