Math
142
Practice Midterm
#1
Sept.
29, 2003
______________________
Professor
Jackson’s class
Name
1.
Six
different dice are rolled.
a)
What is the probability that exactly one 6 occurs?
b)
What
is the probability that exactly one 6 and exactly one 1 occurs?
2.
A man orders 25 cookies from a shop that has 10 types of cookies.
How many different orders are possible if he orders
a)
at
least one cookie of each kind?
b)
at least two cookies of each kind?
c)
at least one and at most five cookies of each kind?
Hint: Use a generating function.
3.
In the California lottery 6 different numbers from the set {1,2,…,49}
are chosen at random.
What is the probability that the highest number chosen is
a)
greater
than or equal to 40?
b)
exactly equal to 40 and the lowest number is exactly equal to 10?
4.
Eight different toys are distributed to three different children.
a)
How many different distributions are possible?
b)
How many different distributions are possible if each child receives at
least one toy?
Hint: Use an exponential generating function.
c)
How
many different distributions are possible if each child receives at least two
toys?
5.
How many different arrangements of the 11 letters in COMBINATION have
a)
the
first O appearing to the left of the first I?
b)
no two consecutive I’s and no two consecutive O’s?
6.
Find a generating function for the number of partitions of an integer n
a)
into summands no larger than 4.
b)
whose highest summand is 4?
c)
whose highest summand is 4 and lowest summand is 1?
Extra
Credit: (5 points) Find the number of different arrangements of the 11 letters
in MATHEMATICS with no two consecutive vowels.
The End
Practice Midterm #2
Nov.
10, 2003
______________________
Professor
Jackson’s class Name
One
page of notes and a calculator allowed.
Total
= 60 points, show your work for full credit.
1.
A stack of coins is made from pennies, nickels, and dimes (all coins of
the same type are considered identical).
a)
Let an be the number of different stacks of n coins with no
two consecutive pennies.
Find a recurrence relation for an.
b)
Let bn be the number of different stacks of coins worth n
cents that don’t contain two consecutive pennies.
Find a recurrence relation for bn.
2.
Let an be the sequence described by an = 2an-1
+ 3an-2, with a0 = 1 and a1 = 3.
Find a formula for an.
3.
Let an be the sequence described by an = 2an-1
+ 3n, with a0 = 1.
Find a formula for an.
4.
Consider the arrangements of all 11 letters in MISSISSIPPI.
Find the number of different arrangements with either 4 consecutive
S’s, 4 consecutive I’s, or 2 consecutive P’s.
5.
Two hundred identical chairs are distributed to six different classrooms
with at least 30 chairs and no more then 40 chairs in each classroom.
How many different distributions are possible?
Hint: Let xi be the number of chairs distributed to classroom
i. Then
x1 + x2 + … + x6 = 200, 30 £
xi £
40.
6.
The edges of a regular hexagon are colored using 4 colors.
a) How many different colorings are possible if two colorings, which
differ by a rotation or a flip are considered identical?
b) How many different colorings are possible if each of the four colors
is used at least once?
7.
How many different 13-card bridge hands contain at least one ace, at
least one king, at least one queen, and at least one jack?
8.
[10 points] The squares of a 4 x 4 chessboard are colored red, white,
blue, and gold.
If two chessboards that differ by a rotation are considered identical a)
how many different colorings are possible?
b) how many different colorings with 4 squares of each color are
possible?
The End
Math
142 Practice
Final
(Worth
15 points extra credit if turned in by Dec. 8)
Final
Exam Fri. Dec. 12
9:45-12:00
90 points
Covers
chapters 1-3 and 5-9
One
page of notes and a calculator allowed.
1.
Find the number of nonnegative integer solutions of x1+x2+x3+x4+x5+x6
= 60 satisfying a) xi ³
2, i = 1,2,3,4,5,6.
b) xi even, i = 1,2,3,4,5,6.
2.
Fifteen married couples attend a dance.
If two lines are formed male dancers on one side, each facing a female
dancer on the other side, in how many ways can they line up so that no husband
and wife are facing each other?
3.
Find the number of ways to distribute 25 (or fewer) identical balls to 6
different children so that each child receives at least 3 balls.
4.
a) In how many ways can 12 different toys be distributed to 6 different
needy children so that each child receives at least one toy?
b) Repeat a) if instead there are 6different types of toys, 2 toys of
each type, and no child receives two identical toys.
5.
Find a generating function (but do not solve) for cn , the
number of unordered partitions of an integer n into a) summands no larger than
5.
b) exactly 5 summands.
6.
a) Find an exponential generating function for an, the number
of sequences of length n that can be constructed from the letters {A,B,C,D,E} if
A occurs an even number of times and B,C each occur at least once.
b) Find a formula for a25.
7.
Find the probability that a six-card poker hand contains a) a
four-of-a-kind (four cards of one rank, any two other cards).
b) a full house (three cards of one rank, two or more cards of another
rank, but not four cards of any rank).
8.
Find a recurrence relation (but do not solve) for dn, the
number of ways to flip a single coin n times so that no more than 3 consecutive
heads occur.
9.
a) Find a recurrence relation for an, the number of ways to
place n ft. of colored flags on a flagpole using red flags that are 1 ft. high
and white and blue flags that are 2 ft. high.
b) Repeat a) if instead no two blue flags are adjacent.
10.
Find
a generating function for the number of ways to distribute n identical objects
to six different boxes where a) box 1 and box 2 each receive an even number of
objects.
b) the total number of objects distributed to boxes 1 and 2 is even.
11.
a)
Find a particular solution of the nonhomogeneous recurrence an = 3an-1
+ 4an-2 +n+2.
b) Find the general solution of the recurrence in a).
12.
Show
that every tree with at least 2 vertices of degree 2, 3 vertices of degree 3,
and 4 vertices of degree 4 has more than 20 vertices.
13.
Let
G be any connected graph and suppose V(G) = V1 È
V2 is a partition of the vertices of G.
Show that any spanning tree of G has at least one edge joining a vertex
in V1 and a vertex in V2.
14.
Let
G be any k-regular bipartite graph with bipartition (X,Y).
a) If k > 1 show that |X| = |Y|.
b) If k > |X|/2, show that G is connected.
15.
a)
Show that every 5-regular graph has an even number of vertices.
b) Show that every 5-regular graph with 12 vertices has the same number
of edges.
The End