Let P be a poem with n lines P1, . . . , Pn. A rhyming scheme for P is a string of letters a,b,c,d,e,... of length n which identifies which lines in the poem rhyme with each other. The letters are always used in sequence, so line P1 is always represented by a. P2 is represented by a or b, depending on whether P2 rhymes with P1 or not, and so forth. For instance, a five-line poem with no rhyming lines has rhyming scheme abcde. A 6-line poem in which ALL lines rhyme has rhyming scheme aaaaaa. A limerick, such as this poem by Edward Lear, has rhyming scheme aabba: There was an Old Man with a beard, Who said, It is just as I feared! Two Owls and a Hen, Four Larks and a Wren, Have all built their nests in my beard! Prove that there are exactly S(m, n) rhyming schemes for m-line poems which use exactly n different letters of the alphabet.

Problem 4 Let P be a poem with n lines P1,...,Pn. A rhyming scheme for P is a string of letters a,b,c,d,e,... of length n which identifies which lines in the poem rhyme with each other. The letters are always used in sequence, so line P is always represented by a. P2 is represented by a or b, depending on whether P2 rhymes with P or not, and so forth. For instance, a five-line poem with no rhyming lines has rhyming scheme abcde. A 6-line poem in which ALL lines rhyme has rhyming scheme aaaaaa. A limerick, such as this poem by Edward Lear, has rhyming scheme aabba: There was an Old Man with a beard, Who said, It is just as I feared! Two Owls and a Hen, Four Larks and a Wren, Have all built their nests in my beard! Prove that there are exactly S(m, n) rhyming schemes for m-line poems which use exactly n different letters of the alphabet. Problem 4 Let P be a poem with n lines P1,...,Pn. A rhyming scheme for P is a string of letters a,b,c,d,e,... of length n which identifies which lines in the poem rhyme with each other. The letters are always used in sequence, so line P is always represented by a. P2 is represented by a or b, depending on whether P2 rhymes with P or not, and so forth. For instance, a five-line poem with no rhyming lines has rhyming scheme abcde. A 6-line poem in which ALL lines rhyme has rhyming scheme aaaaaa. A limerick, such as this poem by Edward Lear, has rhyming scheme aabba: There was an Old Man with a beard, Who said, It is just as I feared! Two Owls and a Hen, Four Larks and a Wren, Have all built their nests in my beard! Prove that there are exactly S(m, n) rhyming schemes for m-line poems which use exactly n different letters of the alphabet