1.

a. If we label the rows of Pascal's Triangle
starting with n = 0 and the columns starting with k
= 0, what is the value of the entry in row 14,
column 11?
C(14,11)

b. Express P(18,3) in three different ways: (i)
as the product of three consecutive integers; (ii)
using factorial notation; and (iii) in terms
of C(18,3).
(i)
18*17*16
(ii)
18!/15!
(iii)
C(18,3)*3!

c. In how many ways can 12 donuts be distributed
to 6 people, allowing that some may receive no
donuts or that one person may get them all?
The problem
reduces to determining the number of nonnegative
integer solutions to the equation x1 + x2 + x3 + x4
+ x5 + x6 = 12. There are C(12 + 6  1,6  1) =
C(17,5) such ways.

d. A biologist plans to complete an experiment
with 14 mice, aptly numbered 1 through 14. Six of
the mice will receive a double dose of Vitamin E, 5
of the mice will receive a single dose of Vitamin
E, and the rest will receive no doses of Vitamin E.
In how many ways can this distribution take
place?
C(14,6)*C(8,5)*C(3,3)
= 14!/(6!5!3!)

e. A committee of three is to be formed from
among four men (Adam, Bill, Cal, and Dan) and four
women (Eve, Fran, Gert, and Hanna). In how many
ways can this be done if Adam and Eve refuse to
serve on it together?
There are
three disjoint cases to consider:
I) Neither
Adam nor Eve are on the committee: In this case, we
must select 3 from the remaining 6 possible
committee members: C(6,3).
II) Eve is on
the committee, Adam is not: We need to select 2
more committee members from the 6 remaining people:
C(6,2).
III) Eve is
not on the committee, Adam is: Same reasoning as
for (II): C(6,2).
This results
in C(6,3) + 2*C(6,2) different ways to create the
committee.



2.

The following conjecture is to be proven true by
induction or shown to be false using a counterexample: 1 + 2
+ . . . + (n1) + n + (n1) + . . . + 2 + 1 = n^2.
a. Describe and carry out the first step in the
induction process.
We need to
show that the result holds for the case n=1. Here,
when n = 1, we have 1 = 1^2, which is a true
statement.

b. Describe and carry out the second step in the
induction process.
We assume
that the result holds for the case when n = k. for
this problem, then, we assume that 1 + 2 + . . . +
(k1) + k + (k1) + . . . + 2 + 1 =
k^2.

c. Describe but do not carry out the
third step in the induction process.
In this step,
we show that, based on the assumption made in Step
2, the result holds for the case when n =
k+1.



3.

There are 6 men and 5 women on a committee. A
subcommittee of 6 is to be formed. The subcommittee must
have no less than two men and two women. In how many ways
can such a subcommittee be formed?
We must consider three
disjoint cases that represent all possible compositions of
the committee.
I) There are 2 men and
4 women on the committee. For this case, we choose 2 men
from 6 and 4 women from 5. We then match each possible group
of men with each possible group of women. This can be done
in C(6,2)*C(5,4) ways.
I) There are 3 men and
3 women on the committee. For this case, we choose 3 men
from 6 and 3 women from 5. We then match each possible group
of men with each possible group of women. This can be done
in C(6,3)*C(5,3) ways.
I) There are 4 men and
2 women on the committee. For this case, we choose 4 men
from 6 and 2 women from 5. We then match each possible group
of men with each possible group of women. This can be done
in C(6,4)*C(5,2) ways.
This gives us
C(6,2)*C(5,4) + C(6,3)*C(5,3) + C(6,4)*C(5,2) ways to form
the committee.


4.

A domino is a rectangle formed by two congruent squares.
Each square contains an orderly pattern of "pips" or dots
representing a number from zero through six. How many
different dominoes can be made under these restraints?
We consider two
different cases that are disjoint.
I) The domino has a
different number of pips in each of the two squares. In this
case, there are 7 numbers possible for one square and 7 for
the other. This yields 42 dominoes. Note, however, that the
domino 5:6 is not distinguishable from the domino 6:5.
Therefore, therefore half of the 42 dominoes counted here
will be duplicates. We have 21 different dominoes each with
a different pair of numbers.
II) The domino has the
same number of pips in each of the two squares. There are
seven such dominoes, from 0:0 to 6:6.
We have a total of 28
dominoes that can be created under the described
conditions.


5.

For some positive integer n, how many integers between 0
and 2n inclusive must you pick to be sure that at least one
of them is odd?
The set in question is
{0,1,2,3,4,...,2n1,2n}. There are n+1 even numbers in the
set, consisting of 0,2,4,...,2n. Thus, it is possible we
could pick n+1 values from the original set and still have
no even number. The next pick, however, would have to be an
odd number.
By the pigeonhole
principle, we need n+2 values to assure that at least one of
them is odd.


6.

Suppose that Jay Cool and the Gingos are playing at the
Starlite Theatre. The theatre has one section of seats,
arranged with 70 seats in the first (front) row, 72 seats in
the second row, 74 seats in the third row, and so on, for a
total of 30 rows. The seats are numbered from left to right,
with the first seat in the first row being #1, the first
seat in the second row #71, and so on.
a. Write a recurrence relation and an explicit
formula for R(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 last (30th) row.
Recurrence
Relation: Each successive row contains 2 more
seats than the previous row. So if we begin with
R(1) = 70 as the initial condition, we get R(n) =
R(n1) + 2 as the recurrence
relation.
Explicit
Formula: This is a linear pattern, noting the
constant difference of 2 seats between each
consecutive pair of rows. The explicit formula is
R(n) = 68 + 2n, where n is the row number and n
spans the positive integers from 1 through
30.
Either
relationship yields the value R(30) = 128
seats.

b. Write either an explicit formula or a
recurrence relation for S(n), the sum of all seats
through Row n. Use that to determine the total
number of seats in the theatre.
Recurrence
Relation: We begin with S(1) = 70 as the
initial condition. Each successive sum will contain
all the seats prior to that row plus all the seats
in that row. The number of seats in any particular
row was determined above: R(n) = 68 + 2n. This
leads to S(n) = S(n1) + (68 + 2n) as a recurrence
relation for the row sums.
Explicit
Formula: This is a quadratic pattern,
determined using a difference table and observing
that the first constant difference occurs in the
second differences, that is, in line D2 of the
table. Associating this specific difference table
with the difference table for the general quadratic
results in an explicit formula of S(n) = n^2 +
69n.
Either
relationship yields the value S(30) = 2970
seats.



7.

The set of letters {A,A,A,B,B,B,B,C,C} is to be used to
create kelement subsets.
a. State the range of values for k that is
possible for this situation.
Allowing for
a subset that is empty as well as a subset
containing all elements for the set, k could be any
value in the set {0,1,2,...,9}.

b. How many subsets in all can be created?
If we allow
for duplicate letters to be used as appear in the
original set (i.e., one A is different from
another) there are 2^9 subsets.
If we do not
allow for this, for example, only one subset exists
of the form {A,B,C,C} no matter which of the As and
Bs are chosen, then there are 60 unique subsets.
This can be determined by brute force listing of
all unique subsets and can also be determined by
summing the coefficients of an appropriate
generating function.

Create a generating function that can be used to determine
the number of 6&endash;element subsets that will have at
least one A and at least two Bs.
c. Show the factors of the generating function
before expanding them. Explain what each factor
represents within the context of this problem.
The factors
are (x+x^2+x^3)(x^2+x^3+x^4)(1+x+x^2). Concentrate
on the exponents in the terms of each factor. The
first factor represents the possible number of As
we could include: 1,2, or 3. The second factor
represents the possible number of Bs to include:
2,3, or 4. The last factor represents the possible
number of Cs we could include: 0, 1, or
2.

d. Expand your response to part (c).
x^3 + 3x^4 +
6x^5 + 7x^6 + 6x^7 + 3x^8 + x^9

e. Use part (d) to determine the number of
6element subsets that will have at least one A and
at least two Bs. Include a brief explanation for
how you used part (d).
According to
the expansion in (d), there are 7 6element subsets
of {A,A,A,B,B,B,B,C,C} that include at least one A
and at least two Bs. This value is the coefficient
of the term in the expansion for which x is raised
to the 6th power, where the 6 represents the number
of elements in the subset.



8.

Determine numerical values for x, y, and z that make
a collected term in the expansion of .
We must have x+y+z=k
and we must have k!/(x!y!z!)=210. By trial and error, one
set of values that satisfies these conditions is k=7 and
x,y,z matched with elements of the set {2,2,3}. Can you come
up with other sets, or show that this is the only
solution?


9.

a. How many positive integers are there that are
composed of n digits such that each digit is
1, 2, or 3?
For an
ndigit number, each digit could be one of three
values, either 1, 2, or 3. This means there are 3^n
positive integers that meet the desired
condition.

b. Of these, how many contain all three of the
digits 1, 2, and 3 at least once?
We apply the
inclusion/exclusion principle here to eliminate the
positive integers counted above that DO NOT contain
each of 1, 2, and 3 at least once. We consider ways
to create ndigit numbers that are missing at least
one of 1, 2, and 3.
Begin by
answering the following question: How many ways are
there to create an ndigit number composed of no
more than two of the values 1, 2, or
3?
Each of the n
values in such a number can be selected from only
two choices, so there are 2^n such numbers. Thus,
if we want an ndigit number with only 1s or 2s in
it (i.e., 3 is not included), there are 2^n ways to
create it. This would be true for an ndigit number
with only 1s or 3s in it (i.e., 2 is not included),
as well as for an ndigit number with only 2s or 3s
in it (i.e., 1 is not included). Therefore, there
are 3*2^n ndigit numbers, from the set determined
in (a) above, that have at most two different
digits in them.
But this
collection of ndigit numbers includes some
duplication, for some of the ndigit numbers have
only one unique digit in them, and we have counted
those twice. So we must add back the number of
ndigit positive integers that contain only one
unique digit from the set {1,2,3}. There are just
three such numbers, an ndigit number composed of
all 1s, an ndigit number composed of all 2s, and
an ndigit number composed of all
3s.
So, by the
inclusion/exclusion principle, we have 3^n  3*2^n
+ 3 ndigit numbers that contain each of the three
digits 1,2, and 3, at least once.



10.

My nephew Seth noticed that Kellogg's cereals offers a
set of 5 cartoon characters in its current cereal
selections. One cartoon character is in each specially
marked box of cereal and the cartoon characters are equally
distributed among the cereal boxes currently coming off the
production line.
Seth has been around me enough so that he can figure out
some probabilities. He knows that the probability of getting
a complete set by purchasing less than five boxes is 0. He
also explained how to determine the probability he could get
a complete set by buying exactly 5 boxes of cereal. He said
that there are 5! ways he could buy 5 boxes and get all
different characters. He also told me that there were 5^5
different ways to get a set of 5 characters, not necessarily
all different. The probability of getting a complete set in
the first five purchases is 5!/(5^5).
Here's where he needs your help: What's the probability
that it takes exactly 6 boxes of cereal to collect a
complete set of 5 cartoon characters?
For it to require
exactly 6 boxes to assemble a complete set of 5 cartoon
characters, two conditions must hold.
 Among the first 5
boxes purchased, there must be exactly 4 different
cartoon characters. This means there are two of one type
and one each of three other types.
 The sixth box
purchased must contain the missing, or fifth,
character.
We determine in how
many ways each of these conditions can occur.
The second condition
is straightforward in determination: There are 5 different
characters that could occupy the last position in the line
up, that is, be in the sixth box.
For each of those 5
possibilities in the last position, we now determine ways to
meet the first condition. Two things need to be considered:
(a) Which or the four remaining letters will be repeated
among the first five boxes opened? (b) What is the
arrangement of the five letters (four unique letters) once
(a) has been determined?
For (a), there are 4
choices, because one letter has already been used as the
last (sixth box). For (b), a way to think of this is to
determine the number of arrangements of a 5letter word
composed of 4 different letters, such as 5letter words
composed on 4 letters from the set {A,B,C,D}. One such word
is ABCDA, and another is DCBBA. This is a problem we've
solved several times. We know there are 5!/(2!1!1!1!)
arrangements of those letters.
Associating the
results from considering these conditions, we have
5*4*[5!/(2!1!1!1!)] or 1200 such arrangements of the
cartoon characters.
In all, there are 5^6
different ways to get cartoon characters in the first six
boxes, for with each box there are 5 items than could be in
it.
Our desired
probability is 5*4*[5!/(2!1!1!1!)]/(5^6) or
1200/(5^6), approximately 7.65%. This is just less than
double the probability Seth determined for the first 5
boxes, which was 3.84%.


BONUS!

Each week two World Professional Tennis Organizations
determine who are the #1 players in the world for both
womens' and mens' professional tennis.
a. Steffi Graf was #1 in womens' tennis without
interruption over the period Monday, August 17,
1987, until Sunday, March 10, 1991. This is the
greatest number of consecutive weeks that any woman
or man has been #1 in the professional
rankings. How many consecutive weeks were there in
Steffi Graf's record? Clearly show your work in
solving the problem.

b.Steffi Graf was also ranked #1 during these
time periods:
 August 5 to August 11, 1991
 August 19 to September 8, 1991
 June 7, 1993, to February 5, 1995
 February 20 to February 26, 1995
 April 10 to April 30, 1995
Including your response to (a), for how many
total weeks of her career, through 30 April 1995,
was Steffi Graf ranked #1?

The solution to
this problem will appear soon. Keep trying!

