Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers Spring 2003 
Test #3 Possible Solutions 
Please write your solutions on one side only of each piece of paper you use, and please begin each solution on a new sheet of paper. You may use factorial notation as well as combination and permutation notation where appropriate (i.e., there is no need to expand 24!).You are to work alone on this test. You may not use anyone else's work nor may you refer to any materials as you complete the test. You may ask me questions.
Evaluation Criteria
You may earn up to 10 points on each of questions 1 through 6. For each question:
 6 points count toward a correct solution to the problem. I will evaluate the mathematics you use:
 Is it accurate and appropriate?
 Have you provided adequate justification?
 4 points count toward how you express your solution. I will evaluate how you communicate your results:
 Is your solution clear and complete?
 Have you expressed logical connections among components of your solution?
1. 
Respond to each question below 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 questions (a) through (e) on this page. a) Determine the number of derangements, expressed as a positive integer, for the elements in the set {a,b,c,d,e,f,g}, where the natural position for a is the first position, the natural position for b is the second position, and so on. (2 points) b) Answer the following questions for the recurrance relationship described by a(n)=2*a(n1) + 3*n^2 for n a positive integer, where a(1) = 3. (2 points) i) Determine a(4). c) In the expansion of (m+a+t+h)^110, state (2 points each): i) the number of uncollected terms d) Determine the number of collected terms in the expansion of (t+e)^n. (2 points) 

2. 
Solve each of the following counting problems. (2 points each) a) Sheila is deciding which shoes/socks matchup to wear to a costume party. How many different matchups are possible if Sheila has 21 different pairs of shoes and 43 different pairs of socks? Assume that Sheila does not break apart any matched pair of socks or any matched pair of shoes. b) Andie is arranging sports cards in her album. She has 20 cards to arrange and wants to place 4 cards on the first page of the album, according to the layout illustrated here (sample cards only). If Andie arranges 4 of her 20 cards on the front page, how many different 4card arrangements are possible?
c) A class roster has 21 distinct student names, including 8 males and 13 females. In how many ways can we create a team that contains 4 males and 5 females? d) Pat delivered mail to the faculty in the mathematics department. One day, Pat delivered 120 distinct pieces of mail to 42 different mailboxes in the department office, and into each mailbox Pat deposited at least one piece of mail. How many distinct ways exist for Pat to have distributed the mail that day, if our only concern is with the number of pieces in each box? e) Guests at the Honeyland Amusement Park and Playground in Youngstown began their night of celebration with a ride on the Park's stupendous Hovering Hive Roller Coaster, comprised of 40 cars hitched end to end. What is the minimum number of guests required so that when the guests entered the roller coaster cars, at least one car had 5 or more people in it? 

3. 
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 question (3). a) Suppose a recurrence relation s(n) is defined as s(n) = s(n1) + 3*s(n2) for n larger than 2 with s(1) = 3 and s(2) = 2. Determine the absolute difference between the largest and smallest values in the set {s(3), s(4), . . . , s(10)}. (3 points) For questions (b) and (c), assume a set contains an unlimited supply of the letters A, B, C, and D. b) How many ways exist to create a set of 4 letters that contains exactly two different letters? (3 points) c) How many ways exist to create a 50letter set under the following restrictions: There must be at least 3 As, at least 5 Bs, 2 or more Cs, and more than 5 Ds? (4 points) 

4. 
Use this difference table for parts (a) and (b).
a) Complete as many open rows of the table (D1, D2, D3, D4, D5) as necessary to determine the type of polynomial function that will model the relationship between the values in the first two rows of the table (x and f(x)). Write a brief explanation describing how you know what type of polynomial function this will be. (2 points) 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). (3 points) Here are the first few rows for an array of values. Use this for questions (c) and (d). 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 c) Write in entries for two more rows of the table. These are rows 6 and 7. (2 points) 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! (3 points) 

5. 
Bransford Performing Arts Center has one section of theatre seats, arranged with 44 seats in the first (front) row, 47 seats in the second row, 50 seats in the third row, and so on, with a total of 42 rows. The seats are numbered consecutively from left to right, with the first seat in the first row being #1, the first seat in the second row #45, and so on. a) Write a recurrence relation and an explicit formula for S(n), the number of seats in Row n. Be sure to include information about initial conditions. Use your results to determine the number of seats in the row farthest from the front of the theatre. (5 points) b) Write either an explicit formula or a recurrence relation for T(n), the total number of all seats from Row 1 through Row n. Use your result to determine the greatest (largest) seat number in the theatre. (5 points) 

6. 
a) Fifteen different people are standing in a single line to get halfprice tickets to a Broadway show. Lyle and Annabelle are two of the people in line, and there are exactly 4 people between Lyle and Annabelle. In how many distinct ways can such a lineup occur? (5 points) b) Generalize your solution to the problem above for Lyle and Annabelle being among p different people standing in line for tickets, with exactly b people between Lyle and Annabelle. (5 points) 





