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)

Solution: D(7) = 1854 po9ssible derangements Use D(n)=(n-1)*(D(n-2)+D(n-1) or D(n)=n!(1-1+1/2!-1/3!+1/4!-...+(-1)^n/n!)

b) Answer the following questions for the recurrance relationship described by a(n)=2*a(n-1) + 3*n^2 for n a positive integer, where a(1) = 3. (2 points)

i) Determine a(4).

Solution: a(4)=174 a(1)=3, a(2)=18, a(3)=63, a(4)=174

ii) Determine the smallest value of n such that a(n+2) - a(n) is greater than 1000.

Solution: n=5 Continuing from (a): a(5)=423, a(6)=954, a(7)=2055. The values a(5) and a(7) differ by more than 1000.

c) In the expansion of (m+a+t+h)^110, state (2 points each):

i) the number of uncollected terms

Solution: 4^110

ii) the coefficient C in the collected term Cm^11a^22t^33h^44.

Solution: 110!/(11!22!33!44!)

d) Determine the number of collected terms in the expansion of (t+e)^n. (2 points)

Solution: n+1

2.

Solve each of the following counting problems. (2 points each)

a) Sheila is deciding which shoes/socks match-up to wear to a costume party. How many different match-ups 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.

Solution: 21*43 Use the multiplication principle.

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 4-card arrangements are possible?

Solution: P(20,4)

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?

Solution: C(8,4)*C(13,5)

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?

Solution: C(119,41) This represents the number of positive integer solutions to the equation A(1)+A(2)+...+A(42)=120, so we use C(120-1,42-1).

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?

Solution: 161 Apply the pigeonhole principle. The worst case is that all 40 cars have 4 people in each. This represents 160 people. The 161st person would be the 5th person in one of the cars.

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(n-1) + 3*s(n-2) 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)

Solution: 936 s(1)=-3, s(2)=2, s(3)=-7, s(4)=-1, s(5)=-22, s(6)=-25, s(7)=-91, s(8)=-166, s(9)=-439, s(10)=-937. From among s(3) through s(10), we have s(4)=-1 as the largest value and s(10)=-937 as the smallest value. The absolute difference between these two values is 936.

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)

Solution: C(4,2)*3=18 First, choose exactly two of the four letters. This is done in C(4,2) ways. With each pair of letters chosen, their are 3 possible amounts of each letter: two of each, three of the first and one of the second, or one of the first and three of the second.

c) How many ways exist to create a 50-letter 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)

Solution: C(37,3) We begin by taking from 50 enough letters to meet minimum requirements: 3 As, 5 Bs, 2 Cs, and 6 Ds. This leave us with 34 objects to place among 4 categories, or equivalently, we seek the number of non-negative solutions to the equation A+B+C+D=34. There are C(34+4-1,4-1) such solutions.

4.

Use this difference table for parts (a) and (b).

x		1		2		3		4		5		6		7
f(x)		1		4		11		22		37		56		79
D1 --->
D2 --->
D3 --->
D4 --->
D5--->

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)

Solution: This is a quadratic relationship, because the first appearance of constant differences was in row D2. x 1 2 3 4 5 6 7 f(x) 1 4 11 22 37 56 79 D1 ---> 3 7 11 15 19 23 D2 ---> 4 4 4 4 4

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)

Solution: f(x)=2x^2-3x+2 Use the general quadratic difference table and compare corresponding parts of it to those in the specific difference table shown able.

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)

Solution: Rows 6: 256 289 324 361 400 441; Row 7: 484, 529, 576, 625, 676, 729, 784 The table entiries are squares of consecutive positive integers.

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)

Solution: The table row sums create a 5th-degree polynomial relationship. x 1 2 3 4 5 6 7 f(x) 1 13 77 294 855 2071 4403 D1 ---> 12 64 217 561 1216 2332 D2 ---> 52 153 344 655 1116 D3 ---> 101 191 311 461 D4 ---> 90 120 150 D5---> 30 30

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)

Solution: Recursive: S(n)=S(n-1)+3, where S(1)=44 Explicit: S(n)=44+3(n-1) = 3n+41; S(42)=167

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)

Solution: Resursive: T(n)=T(n-1)+[44+3(n-1)], with T(1)=44; Explicit: T(n)=(3/2)n^2+(85/2)n; T(42)=4431

6.

a) Fifteen different people are standing in a single line to get half-price 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 line-up occur? (5 points)

Solution: 10*2*13! With 15 in line and 4 people between Lyle and Annabelle, there are 10 places in line where this 6-person chunk could stand. There are two ways to arrange Lyle and Annabelle, as they can wsitch places with each other. There are 13! ways to arrange the remaining 13 people (those between as well as outside Lyle and and Annabelle)who are in line.

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)

Solution: (p-(b+1))*2*(p-2)! Here we generalize the pattern in the specific problem just solved.