document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1176883>Question 1176883</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Part a: Suppose you owe 10 dollars to a friend. Each week you pay your friend at least 1 dollar back. Sometimes however you might pay your friend back 2 dollars in a week and other times you might pay your friend 5 dollars in a week. How many different payment sequences are possible? Here are a couple possible sequences:\r<BR>\n" );
document.write( "\n" );
document.write( "1-1-1-1-1-1-1-1-1-1  ,  5-5 , 5-2-2-1 , 2-2-1-5 , etc…\r<BR>\n" );
document.write( "\n" );
document.write( "Hint: Try to find a recursive function that answers this question for n-dollars and then use it on an n-value of 10.\r<BR>\n" );
document.write( "\n" );
document.write( "Part b: Give another function to answer part a, but this time your function must NOT be recursive. Hint: Think about the counting theory we learned this term.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( " </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #850552 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(1959)</B></A><img src=\"/images/stars/stars-12.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=850552\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Absolutely, let's break down this problem into parts.\r<BR>\n" );
document.write( "\n" );
document.write( "**Part a: Recursive Function**\r<BR>\n" );
document.write( "\n" );
document.write( "**1. Define the Recursive Function**\r<BR>\n" );
document.write( "\n" );
document.write( "Let `f(n)` be the number of different payment sequences to pay back `n` dollars.\r<BR>\n" );
document.write( "\n" );
document.write( "**2. Base Cases**\r<BR>\n" );
document.write( "\n" );
document.write( "* `f(0) = 1` (If you owe 0 dollars, there's 1 way: do nothing.)<BR>\n" );
document.write( "* `f(n) = 0` if `n < 0` (You can't pay back a negative amount.)\r<BR>\n" );
document.write( "\n" );
document.write( "**3. Recursive Step**\r<BR>\n" );
document.write( "\n" );
document.write( "To pay back `n` dollars, you can make the last payment 1, 2, or 5 dollars. So:\r<BR>\n" );
document.write( "\n" );
document.write( "* `f(n) = f(n-1) + f(n-2) + f(n-5)`\r<BR>\n" );
document.write( "\n" );
document.write( "**4. Calculate f(10)**\r<BR>\n" );
document.write( "\n" );
document.write( "Let's compute the values iteratively:\r<BR>\n" );
document.write( "\n" );
document.write( "* `f(0) = 1`<BR>\n" );
document.write( "* `f(1) = f(0) = 1`<BR>\n" );
document.write( "* `f(2) = f(1) + f(0) = 1 + 1 = 2`<BR>\n" );
document.write( "* `f(3) = f(2) + f(1) = 2 + 1 = 3`<BR>\n" );
document.write( "* `f(4) = f(3) + f(2) = 3 + 2 = 5`<BR>\n" );
document.write( "* `f(5) = f(4) + f(3) + f(0) = 5 + 3 + 1 = 9`<BR>\n" );
document.write( "* `f(6) = f(5) + f(4) + f(1) = 9 + 5 + 1 = 15`<BR>\n" );
document.write( "* `f(7) = f(6) + f(5) + f(2) = 15 + 9 + 2 = 26`<BR>\n" );
document.write( "* `f(8) = f(7) + f(6) + f(3) = 26 + 15 + 3 = 44`<BR>\n" );
document.write( "* `f(9) = f(8) + f(7) + f(4) = 44 + 26 + 5 = 75`<BR>\n" );
document.write( "* `f(10) = f(9) + f(8) + f(5) = 75 + 44 + 9 = 128`\r<BR>\n" );
document.write( "\n" );
document.write( "**Answer (Part a):** There are 128 different payment sequences.\r<BR>\n" );
document.write( "\n" );
document.write( "**Part b: Non-Recursive Function (Counting Theory)**\r<BR>\n" );
document.write( "\n" );
document.write( "**1. Break Down the Problem**\r<BR>\n" );
document.write( "\n" );
document.write( "We need to find the number of ways to express 10 as a sum of 1s, 2s, and 5s.\r<BR>\n" );
document.write( "\n" );
document.write( "**2. Consider Possible Combinations**\r<BR>\n" );
document.write( "\n" );
document.write( "We can systematically list the possible combinations:\r<BR>\n" );
document.write( "\n" );
document.write( "* **Only 1s:** 10 ones (1 way)<BR>\n" );
document.write( "* **Using 5s:**<BR>\n" );
document.write( "    * Two 5s (1 way)<BR>\n" );
document.write( "    * One 5:<BR>\n" );
document.write( "        * One 5, five 1s (1 way)<BR>\n" );
document.write( "        * One 5, two 2s, one 1 (number of ways to arrange them)<BR>\n" );
document.write( "* **Using 2s (without 5s):**<BR>\n" );
document.write( "    * Five 2s (1 way)<BR>\n" );
document.write( "    * Four 2s, two 1s (number of ways to arrange them)<BR>\n" );
document.write( "    * Three 2s, four 1s (number of ways to arrange them)<BR>\n" );
document.write( "    * Two 2s, six 1s (number of ways to arrange them)<BR>\n" );
document.write( "    * One 2, eight 1s (number of ways to arrange them)<BR>\n" );
document.write( "    * Ten 1s (1 way)\r<BR>\n" );
document.write( "\n" );
document.write( "**3. Use Combinations**\r<BR>\n" );
document.write( "\n" );
document.write( "We'll use combinations to count the arrangements:\r<BR>\n" );
document.write( "\n" );
document.write( "* **Two 5s:** 1 way<BR>\n" );
document.write( "* **One 5:**<BR>\n" );
document.write( "    * One 5, five 1s: 6! / (5!1!) = 6 ways<BR>\n" );
document.write( "    * One 5, two 2s, one 1: 4! / (1!2!1!) = 12 ways<BR>\n" );
document.write( "* **Only 2s:**<BR>\n" );
document.write( "    * Five 2s: 1 way<BR>\n" );
document.write( "    * Four 2s, two 1s: 6! / (4!2!) = 15 ways<BR>\n" );
document.write( "    * Three 2s, four 1s: 7! / (3!4!) = 35 ways<BR>\n" );
document.write( "    * Two 2s, six 1s: 8! / (2!6!) = 28 ways<BR>\n" );
document.write( "    * One 2, eight 1s: 9! / (1!8!) = 9 ways<BR>\n" );
document.write( "    * Ten 1s: 1 way\r<BR>\n" );
document.write( "\n" );
document.write( "**4. Sum the Combinations**\r<BR>\n" );
document.write( "\n" );
document.write( "1 + 6 + 12 + 1 + 15 + 35 + 28 + 9 + 1 = 128\r<BR>\n" );
document.write( "\n" );
document.write( "**Answer (Part b):** There are 128 different payment sequences.\r<BR>\n" );
document.write( "\n" );
document.write( "**Non-Recursive Function (Conceptual)**\r<BR>\n" );
document.write( "\n" );
document.write( "More generally, you'd need to:\r<BR>\n" );
document.write( "\n" );
document.write( "1.  Enumerate all possible combinations of 1s, 2s, and 5s that sum to 10.<BR>\n" );
document.write( "2.  For each combination, use the multinomial coefficient formula to determine the number of distinct arrangements: `n! / (n1! * n2! * n3!)` where `n` is the total number of payments, and `n1`, `n2`, and `n3` are the numbers of 1s, 2s, and 5s, respectively.<BR>\n" );
document.write( "3.  Sum up the results from step 2.<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );