# 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!