10. Rappers use rhyme schemes to describe which lines of a rap rhyme. The rhyme at the end of each line is denoted by a letter of the alphabet, with the same letter given to two lines that rhyme. For example, to say that a rap has the rhyming scheme ABABCDED, indicates that the first and the third lines rhyme, the second and the fourth lines rhyme, and the sixth- and eighth-lines rhyme, but no others. More precisely, the first line of the rap is given the letter A. If a subsequent line rhymes with an earlier line, it is given the same letter; otherwise, it is given the first unused letter. (For the purposes of this question, you can assume that we have an infinite supply of "letters", not just the 26 letters of the alphabet.) (a) The purpose of this question is to investigate how many different rhyme schemes there are for raps of n lines. We write in for this number. There are five different rhyming schemes for raps of three lines, i.e. r3 = 5. List them. [1 marks] (b) Let Sn.k denote the number of rhyming schemes for raps with n lines that use exactly k different rhymes at the end of the line. For example, $3,2 = 3 because the three rhyming schemes that use 3 lines and 2 different rhymes at the end of the line are AAB, ABA and ABB. What is Sn, 1 for n > 1? What is Sn,n? Explain both answers. [2 marks] (c) Suppose that 1 < k < n. By considering the rhyme at the end of the final line of a rhyming scheme, explain why this is the case that Sn,k = Sn-1.k-1 + k Sn-1.k- [5 marks] (d) Explain how it is possible to calculate rn in terms of Sn,k. Hence calculate r4. [5 marks] (e) Give a formula for Sn,2 in terms of n (for n > 2). Justify your answer. [3 marks]