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)=(n1)*(D(n2)+D(n1) or
D(n)=n!(11+1/2!1/3!+1/4!...+(1)^n/n!)

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).
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
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)


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.
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 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?
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(1201,421).

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(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)
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
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)
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 nonnegative solutions to the
equation A+B+C+D=34. There are C(34+41,41) 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^23x+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 5thdegree
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(n1)+3, where S(1)=44 Explicit:
S(n)=44+3(n1) = 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(n1)+[44+3(n1)], 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 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)
Solution: 10*2*13!
With 15 in line and 4 people between Lyle and
Annabelle, there are 10 places in line where this
6person 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*(p2)!
Here we generalize the pattern in the specific
problem just solved.


