RHYME SCHEMES

With poems of one line there is just one way to do it: a
With poems of two lines, there are two ways to do it:  aa, ab
With poems of three lines, there are five ways to do it:  aaa, aab, aba, abb, abc

Given a poem of n lines, how many rhyme schemes are there?

Derive a second, related problem.

How many ways are there to come up with a poem of EXACTLY l lines and EXACTLY r rhymes?

f(1,1) = 1
f(2,1) = 1
f(2,2) = 1
f(3,1) = 1
f(3,2) = 3
f(3,3) = 1

f(l,r):  Either the last line rhymes with a previous line or it does not.

So, let's suppose the last line rhymes with a previous line.

f(l-1,r) counts all the poems with one line less, not containing my last line.  My last line can rhyme with any of the r rhyme patterns already established.

So, this gives me r f(l-1,r).

If the last line does not rhyme with a previous line.  Then the previous l-1 lines contain a total of r-1 rhyme patterns.  So, this gives me another f(l-1,r-1) possibilities.

So, f(l,r) = r f(l-1,r) + f(l-1,r-1)

Let f(n) be the number of distinct rhyme schemes on a poem of n lines
f(n) = SUM[r=1,n] f(n,r)