Next: About this document ...
Up: My Home Page
Computer Science 547 - Discrete Mathematics
Prof. Steven Skiena
Spring 1999
Homework 3
Due Thursday, March 11, 1999
Each of the problems should be solved on a separate
sheet of paper to facilitate grading.
Limit the solution of each problem to one sheet of paper.
Staple all these sheets together!
Please don't wait until the last minute to look at the problems.
Do the following exercises in Graham, Knuth, and Patashnik:
- 1.
- Warmup exercises 5:1-5. (DO NOT HAND IN)
- 2.
- Exercise 5-38.
- 3.
- Warmup exercises 6:1-10. (DO NOT HAND IN)
- 4.
- Exercise 6-27.
- 5.
- Exercise 6-39.
- 6.
- Warmup exercises 7:1-5. (DO NOT HAND IN)
- 7.
- Give combinatorial proofs of the identities (6.15) and (6.16)
in Graham-Knuth-Patashnik.
- 8.
- How many rhyme schemes are there for an n line stanza?
For 1 line, there is only one, call it A.
For 2 lines, if the first line rhymes with the second, we have AA.
If it doesn't, we have AB for a total of two rhyme schemes.
For 3 lines, the possibilities are AAA (all lines rhyme),
AAB (only first two rhyme), ABA (first and last rhyme),
ABB (only last two rhyme), and ABC (no rhyming lines) - for a total of five.
For 4 lines, the possibilities are AAAA, AAAB, AABA, AABB, AABC, ABAA,
ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD.
Give a formula or recurrence for computing the number of rhyme schemes
using Stirling numbers.
Show why your formula works!
Next: About this document ...
Up: My Home Page
Steve Skiena
1999-01-13