|
|
|
|
Please check here regularily for any new announcements.
Jan. 10: Assignment 1 is now posted below. A link to last years MA344 webpage has been added below. Although the course was quite different last year (in particular no graph theory) this page contains a lot of resources which you may wish to browse through.
Jan. 11: Assignment 2, on the material for the week of Jan 14, is now posted. The first quiz will be at 2:10 Tues Jan 22.
Jan. 16: The first quiz will cover material from the first assignment only.
Jan. 23: The tutorial is now scheduled Thursdays 2:10-3:00 in RW 143, starting next week (Jan. 31). My office hours will be Thursday 11:10 to 12:00, starting this week.
Jan. 25: Solutions to Assignment 2 will be posted tomorrow (Saturday).
Jan. 29: There will be a supplementary
quiz on Thursday on assignments 1 and 2 (and not on the pigeonhole principle!).
Your grade for quiz 2 will be the max of Tuesday's and Thursday's grades.
The solution given in class today
for the problem with 15 books and 4 people was wrong and I know
of no way of doing the problem
without using inclusion-exclusion (section 7.6).
Feb. 7: On today's quiz a number of people gave
the answers only. This will be accepted but in future you must explain
your reasoning.
Some corrections to Soluttions 2 and 3 are now posted.
A "pigeonhole link" has been added below.
Feb. 25: The test is coming up next Tuesday. It will be written in EM 119 from 2:10 to 4:00. It will cover roughly the material in assignments 1 through 5. Be aware that Emmanuel College is a longish walk from Sydney Smith so allow extra time to get there before 2:10. There will be no quiz next week.
Mar13: This week's quiz will be on the material up to and including Assignment 6. S olutions to it are now posted.
Apr. 4: An error in problem C in solutions to ps9 has
been fixed. These solutions were incorrectly headed
Solutions 7, which has also been fixed A number of other
assignment and solution sets are incorrectly
headed but the links on the webpage are all correctly
named so just make the necessary correction when
you print anything out. The solution to problem A in
ps9 promises a link on the webpage to a diagram
which I have not had time to post yet. It will appear
next week. There will be one more assignmnent in the
course which will be posted next week,with solutions
appearing the week after at the latest.
Apr. 5: There will be a final quiz on Thursday Apr.
11 class on the material up to Assignment 10,
inclusive.
Apr 8: In response to several questions, your lowest
three quiz marks (including missed quizzes) will be dropped. I don't
know exactly how many quizzes there will be altogether, probably 9 or 10.
Remember
that the 2 quizzes written on the same week count as
only one, that is,for that week your quiz grade is
the higher of your two grades.
Solutions for the test are now posted.
Apr. 19: Solutions 11 are now posted and also the
diagram for Solutions 9. I will have office hours on Wed.
May 1, 2:00-4:00 and there will be tutorials on Fri.
May 3, 2:00-4:00 and Mon. May 5, 2:00-4:00.
Apr.. 22: There will be tutorials on Friday
May 3, 2:00-4:00 and on Mon. May 6, 2:00-4:00, both in
SS5017A. Friday's tutorial will be run by Joe Callaghan
and I will take the Monday tutorial. I will also
have office hours (SS5016D) On Wed. May 1, 2:00-4:00.
Quizzes are not yet graded. Watch here for an announcement of when and
where you can pick them up.
May 1: Quizzes 8,9
and 10 are now available for pickup in a box outside my office
door (SS 5016D).
Introduction
Welcome to Math 344, Combinatorics. This may well be the most interesting and challenging math course you take as an undergraduate. Unlike some disciplines in mathematics, combinatorics is a very concrete subject. For example we will learn how to answer questions like (to give only a few examples): What is the probability of getting a full house in poker? How many different ``words'' (i.e. sequences of letters) can you form by scrambling the letters of the word ``abracadabra''? How can you find the shortest route from one town to another? Is it possible to plow all the roads in a town without ever having to go over the same road twice, and, if so, how do you find a route which does the trick?
The concreteness of the subject
makes it attractive and accessible. On the other hand (overstating the
case somewhat) no two problems in the subject look the same. This is what
makes the subject challenging. Although we will learn some basic principles
which can be applied in a variety of situations often an individual problem
requires some ingenious idea or insight of its own. Often this insight
is a way of looking at the problem which shows that it is actually the
same kind of problem as a seemingly unrelated one. For example the following
two problems are really the same (why?).
Text: Discrete Mathematics
by Dossey et al., 4th edition, published by Addison Wesley.
Time permitting we will cover the
following sections of the book.
In several places we will go
a little beyond what the book covers. It is essential that you attend lectures
or at least be informed about what is covered in lectures.
Tests, quizzes, assignments and grading scheme
There will be one test on Tues March 5 from 2 to 4 in EM 119 (Emanuel College). There will be 10 weekly quizzes on Tuesdays beginning in the third week of classes and skipping the week of the test. Problem sets will be assigned weekly and posted on this page. Problem sets are not to be handed in, as we don't have sufficient marking resources, but it is of course essential that you do them. Outline solutions to some of the harder problems will be posted on this page.
Your term mark will consist of 60% for the test and 40% for the quizzes. Your grade for the course will be a floating 60-40 average of your term and final exam marks, that is G=3/5max(T,F) + 2/5min(T,F).
Tutorials
There is an unofficial tutorial 2:10 to 3:00 on Thursdays, starting Jan. 31., in RW 143. Try to make use of it regularily, not just before the test.
Assignments
These files are all in PDF format.To
read and print PDF files you need the acrobat reader software which can
be downloaded by clicking here
Get
Adobe Acrobat Reader
| Assignment 1 | Solutions 1 |
| Assignment 2 | Solutions 2 |
| Assignment 3 | Solutions 3 |
| Assignment 4 | Solutions 4 |
| Assignment 5 | Solutions 5 |
| Assignment 6 | Solutions 6 |
| Assignment 7 | Solutions 7 |
| Assignment 8
Notes on Ramsey's theorem |
Solutions 8 |
| Assignment 9 | Solutions 9 |
| Diagram for Solutions 9 (trees)
N.B. This will probably be highly magnified on your monitor but should print O.K. |
|
| Assignment 10 | Solutions 10 |
| Assignment 11 | Solutions 11 |
| Test Solutions | |
Links
| Last years MA344 webpage | Pigeonhole principle |
| "Proof" of 4-colour theorem | Proof of 4-colour theorem |
