Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers Spring 1999 
Possible Solutions for Test #3 
1. 
Respond to each of these questions by placing your solution in the blank. While you may show steps leading to your solution, you do not need to generate written explanations for parts (a) and (b) of question (1). a. In the expansion of , what is the value of K for the collected term ? 8!/(4!3!1!) b. How many solutions are there for the equation if each , i = 1,2,3,4, must be a nonnegative integer? C(41+41,41) = C(44,3) 

2. 
Respond to each of these questions by placing your solution in the blank. While you may show steps leading to your solution, you do not need to generate written explanations for parts (a) and (b) of question (2). a. A teacher intends to assign letter grades to one class of students according to the following distribution: 3 As, 6 Bs, 7 Cs, and 2 Ds. In how many ways can this grade assignment occur? a. 18!/(3!6!7!2!) b. Suppose a recurrence relation s(n) is defined as s(n) = s(n1)  2·s(n3) for n larger than 3 with s(1) = 2, s(2) = 5, and s(3) = 1. Determine the absolute difference between the largest and smallest values in the set {s(1), s(2), . . . , s(8)}.
These values for s(1) through s(8) generate a largest absolute difference of 32, i.e., the absolute difference s(6) = 15 and s(8) = 17. 

3. 
Here is a portion of Pascal's Triangle. Consider the sum C(4,0) + C(5,1) + C(6,2) + C(7,3) + C(8,4) = C(9,4). The components of this sum are outlined in the triangle above. a. In the triangle above, outline the following pattern, including the sum represented here with a question mark. Verify that you have included the correct sum. What is the sum, expressed as a combination? See above for outlined pattern. The question mark should be replaced by C(8,5). By straightforward arithmetic one can verify that the outlined values along the diagonal (1, 3, 6, 10, 15, 21) sum to the remaining value (56). b. Determine C(7,0) + C(8,1) + C(9,2) + . . . + C(27,20). Respond using combination notation. Using the pattern established above, this sum is C(28,20). We note that if the sum is represented by C(a,b), then a is the next positive integer in the sequence as determined by the first numbers in the combinations of the leftside expression. The value b in the sum is determined by the last (largest) second number in the combinations of the leftside expression. c. Determine C(7,7) + C(8,7) + C(9,7) + . . . + C(27,7). Respond using combination notation. Because C(n,k) = C(n,nk), we know that the expression here is equivalent to the expression provided in (b) above. Therefore, the sum is the same as the sum conjectured in (b): C(28,20) = C(28,8). BONUS! State and prove the general result that has been illustrated in the problem. This problem will be left "open" until after the semester exam! 

4. 
Use this difference table for parts (a) and (b). a. Complete as many open rows of the table (D1, D2, D3, D4) as necessary to determine the type of equation that will model the relationship between the values in the first two lines of the table (x and f(x)). Write a brief explanation describing how you know what type of equation this will be. See rows D1 and D2 in table above. With the first constant difference occurring in row D2, we can write a quadratic expression to represent the relationship among the (x,f(x)) pairs that are in the first two rows of the table. b. Use the information in the difference table to generate an explicit formula for the relationship between the values in the first two lines of the table, that is, between x and f(x). We use the difference table for the general quadratic expression ax^2 + bx + c.
Equating values from this table to the one abovem we compute that a = 2, that b = 1, and that c = 1. The function we seek is f(x) = 2x^2 + x  1. Here are the first few rows for a triangular table of values. Use this for questions (c) and (d). c. Write in entries for two more rows of the table. These are rows 4 and 5. See the additional rows in the table above. d. Use the method of finite differences to determine whether a polynomial exists that models the row sums for this table. If such a polynomial exists, state its degree. If a polynomial cannot be used, state why not. You are NOT required to determine any explicit formula here!
Because the first appearance of a constant differrence is in D3, the polynomial in question would be a thirddegree polynomial. 

5. 
Marco's Uncle Oscar gave him two mice, which he named Whiskers and Oscar. But Marco discovered he'd made a big mistake. Oscar should have been named Oscarella! She just had 8 babies, 4 males and 4 females! "Ten mice aren't so many," said Marco to his mother. "They're cute." "Yes," said his mother, "but these cute baby mice will breed when they are 6 weeks old, and continue breeding for a long time. Babies are born 3 weeks after breeding. Each mother mouse will have a litter of 8 babies, half males and half females. Today Marco has 10 mice: Whiskers, Oscarella, and 8 babies. a. How many mice will Marco have in (i) 3 weeks? (ii) 6 weeks? (iii) 9 weeks? (iv) 18 weeks?
b. Write a recurrence relationship for m(n), the number of mice Marco will have n weeks from today. Note that m(0) = 10 and that in part (a) you were asked to determine m(3), m(6), m(9), and m(18). The desired recurrence relation is m(n) = m(n3) + 4[m(n9)]. Today (week n), we have all the mice that existed three weeks ago ( m(n3) ) as well as the baby mice just born from fertile mice that were alive nine meeks ago. There were m(n9) mice alive nine weeks ago, and every pair produces 4 pairs of babies, so the number of babies today is just 4 times the number that were alive nine weeks ago. 

6. 
Many professional sports conduct tournaments to finish a season. Some sports have a singleelimination playoff concluding with a suddendeath championship, such as the National Football League's Super Bowl. Other sports, however, end the season with a multigame series between two teams. For instance, in Major League Baseball, the World Series is a bestof7 playoff. Two teams compete until one team wins four games. Thus, there may be as few as four games in the playoff or as many as seven. In 1998, the New York Yankees swept the San Diego Padres in four games. From the Yankees perspective, the series record was WWWW, where W represents a Yankee win. In 1997, the Florida Marlins defeated the Cleveland Indians four games to three. Their 7game series record was WLWLWLW, where W represents a Florida victory and L a Florida loss. For this type of bestof7 playoff, how many different wonloss records could there be, from the winner's perspective? There will be series that last 4 games, series that last 5 games, series that last 6 games, and series that last 7 games. There are some consistent factors across these four cases: (i) The team that wins the series win the final game. Thus, in the sequence of Ws and Ls that comprise a wonloss record, the last element must be a W. In other words, there is only one choice for that position in the sequence. (ii) Prior to the last game, the team that wins the series must have won three games and the team that loses the series must have won whatever other games have been played. So, if a series lasts g games, the team winning the series wins the last game and wins 3 of the (g1) games prior to that. The losing team wins [(g1)3] or g4 games. For the (g1) games prior to the final game, there are C(g1,3) ways to arrange the 3 Ws and the (g4) Ls that constitute the wonloss record for the g1 games prior to the final game of the series. With this information we can now count the possible sequences for g = 4,5,6,7 games. If g = 4, there is C(3,3) = 1 way to arrange the 3 Ws prior to the fourth W. That is, WWWW is the only way for a team to win the first four games. If g = 5, there are C(4,3) = 4 ways to arrange 3 Ws and 1 L prior to the fourth W. If g = 6, there are C(5,3) = 10 ways to arrange 3 Ws and 2 Ls prior to the fourth W. If g = 7, there are C(6,3) = 20 ways to arrange 3 Ws and 3 Ls prior to the fourth W. This generates 1 + 4 + 10 + 20 = 35 different wonloss records for this type of series playoff. 




