Math 252: Presentation 2
Instructions:
• Sometime today I’ll release a google poll asking about your preferred time for your
presentation. I’ll schedule students first come, first serve, according to your preferences.
You’ll have 24 hours to respond.
• Your camera should be on, assuming you don’t have technical difficulties that prevent
it. You should log into the zoom office hours link for the course, which is posted at
the top in Coursesite a few minutes before your slot starts and wait in the waiting
room for me to get free. I will record the presentation in case I need to review it when
finalizing grading, but I will not post the video, and I will only keep the recording for
the couple of weeks after you get your grades back in case you have any questions.
• You should have a piece of paper and a dark pen or pencil or some other method to
be able to quickly draw or write something and show it to me if you want to.
• If you have technical difficulties connecting or talking, you should call my office number
at 610-758-4720 to make alternate arrangements.
• If you do not show up at your assigned time, you will lose 5 points on the exam.
Exceptions will definitely be made for unforeseen emergencies (illness or unexpected
Internet outage included) as long as you get in touch as soon as your circumstances
reasonably allow.
• You’ll have 20 minutes to “present” on two of the questions below. You’ll get to pick
one, and I’ll get to choose one. For a penalty of 4 points, you may pass on at most one
of my choices.
• While you can bring a few reminder notes to the exam on one side of half of a sheet
of standard paper, you will not get good marks for reading proofs or other remarks
off of a sheet of paper. You may prepare basic equations (but not text) on a separate
scanned page to share with me, as necessary, in advance by email. You’re encouraged
to do so for the (*)ed problem.
• To prepare for the exam, work through as much of each of the questions as you can
below. I do not expect that every student will be able to answer every question below
fully: if you’re unsure how to work through a problem or a subquestion, make sure
you understand all the definitions and the problem and think about how you might
approach it.
1
• You may ask clarification questions of me before the exam starts: I generally will not
give/hint at solutions the same way I sometimes do with homework when necessary.
You may (although you shouldn’t have to) look for solutions in other sources (text or
online) but note that you are unlikely to get many points for such a solution unless you
fully understand (rather than just reading or memorizing) the solution. You may not
post the questions on the exam on a website (like Chegg or Math Overflow) to ask for
help solving them or otherwise ask another outside person to help you solve the exam.
The basic questions are as follows. You should, as before, expect me to have some follow up
questions as we work through them:
1. Assume there is a small class with 12 students, and six teachers assigned to help the
class.
(a) How many ways are there for six teachers to each choose two students?
(b) How many ways can the 12 students each rate the 6 teachers by preference? (Assume
everyone rates every teacher, and there are no ties.)
(c) Assume the class is made up of 6 pairs of twins. How many ways can two students
be assigned to each teacher, so that at least one of the pairs of twins is separated?
(d) How many ways are there for the teachers to each choose two children, such that
no one gets a pair of twins?
2. Give a combinatorial proof of the following:
3. (*) A tile worker has 3 different styles of 1x1 tiles and 4 different styles of 2x1 tiles to
tile a nx1 accent stripe along a wall. Describe a recursion giving the number of ways, tn,
a worker can tile the stripe. Find the ordinary generating function whose coefficient of
x
n
encodes tn. Use the generating function to find a closed form for the number of such
tilings.
4. A local store sells widgets at a cost of $10 per pound, offering 4 possible widgets to their
customers. A salesman observes the following:
• Widget A is only sold in packs of two, and each widget weighs 4 pounds.
• Every project requires at least one of Widget B, but more than three such widgets
are not useful. Widget B weights one pound.
• There are no restrictions on Widgets C (which each weigh 1 pound) and D (which
each weigh 2 pounds), except that they only are useful if there are two C widgets
for every D widget.
Page 2
Let Sn be the number of ways a customer can spend exactly $n (not buy n items or n
pounds of items!) at this Widget supplier to get a useful number of widgets. Find the
generating function for the sequence
{|Sn| : n ≥ 0}.
5. Let dn denote the number of derangements of length n. Give a combinatorial proof that
for 0 ≤ k ≤ n: