Course Guidelines

Combinatorics

University of Puget Sound

Math 420

Fall 2016

Dr. Beezer

Texts

There are numerous open textbooks for combinatorics and graph theory, and I am working on an introductory manuscript about block designs. So course material will be backed by a variety of sources. I will keep you informed in class about particular sections that I recommend for each topic. Electronic versions of this syllabus contain links to each book, other than the first one. Those books with useful HTML versions contain an additional link.

Course Web Page

Off of buzzard.ups.edu/courses.html you can find the link to the course web page.

Office Hours

My office is in Thompson 303. Making appointments or simple, non-mathematical questions can be handled via email — my address is beezer@ups.edu. I rarely do not receive your email, and I read all of my email all of the time, usually very shortly after receiving it. Urgency of replying varies by the hour, day and nature of the message. Office Hours are (tentatively) 2:00–2:50 on Monday and Friday, 10:30–11:30 on Tuesday and Thursday. Office Hours are first-come, first-served, so I do not make appointments for these times, nor do you need to ask me if I will be present at these times. You may assume I will be there, unless I have announced otherwise in class or by email. You may make an appointment for other times, or just drop by my office to see if I am in. Office Hours are your opportunity to receive extra help or clarification on material from class, or to discuss any other aspect of the course.

Calendar

The course is organized into four units:

Start and stop dates are indicated on the attached tentative calendar.

Computation

Combinatorics (and graph theory), as part of discrete mathematics, is a natural area to explore with the aid of computational tools. I will keep you informed of ways that you can use Sage (an open source program for advanced mathematics) to aid your study. The book by Bard is a very helpful general resource, while the other two may be helpful but are not directly aligned with our course.

Practice

Exercises will be suggested regularly as part of each unit. Of course, you are not limited to working just these assigned problems and you can find many more in textbooks in the library (ask me for suggestions). We have seven class days reserved for discussions when we can talk about these problems. It is your responsibility to be certain that you are learning from the homework exercises. The best ways to do this are to work the problems diligently, start studying them early, and participate in the classroom discussion. If at this point you are still unsure about a problem, then a visit to my office is in order, since you are obviously not prepared for the examination questions. Making a consistent effort outside of the classroom is the easiest way (only way?) to do well in this course.

Mathematics not only demands straight thinking, it grants the student the satisfaction of knowing when he [or she] is thinking straight.

―D. Jackson

Mathematics is not a spectator sport.

―Anonymous

I hear, I forget. I see, I remember. I do, I understand.

―Chinese Proverb

An education is not received. It is achieved.

―Anonymous
Examinations

There will be four 50-minute timed examinations. Planned dates are all listed on the tentative schedule. The comprehensive final examination will be given at Noon on Wednesday, December 14. The final exam cannot be given at any other time, so be certain that you do not make any travel plans that conflict, and also be aware that I will allow you to work longer on the final exam than just the two-hour scheduled block of time.

Grades

Grades will be based on the following breakdown:

Attendance and improvement will be considered for borderline grades, while excessive attendance and late-arrival problems will result in grade penalties. Scores will be posted anonymously on the web at a link off the course page.

Academic Policy Reminders

Here are three reminders about important academic policies contained in the Academic Handbook. These are described thoroughly online at http://www.pugetsound.edu/student-life/student-handbook/academic-handbook/, or a printed copy may be requested from the Registrar's Office (basement of Jones Hall).

Registration for Courses of Instruction, Non-Attendance

“Regular class attendance is expected of all students. Absence from class for any reason does not excuse the student from completing all course assignments and requirements.”

Grade Information and Policy, Withdrawal Grades

Withdrawal grades are often misunderstood. A Withdrawal grade (W) can only be given prior to the university deadline listed on our course schedule, and after that time (barring unusual circumstances), the appropriate grade is a Withdrawal Failing (WF), even if your work has been of passing quality. See the attached schedule for the last day to drop with an automatic `W'.

Academic Integrity

All of your graded work is expected to be entirely your own work, this includes Reading Questions and Sage Exercises. Anything to the contrary is a violation of the university's comprehensive policy on Academic Integrity (cheating and plagiarism). Discovered incidents will be handled strictly, in accordance with this policy. Penalties can include failing the course and range up to being expelled from the university.

Purpose

At this point in your college career, you should be well on your way to being an independent scholar, who appreciates the beauty of mathematics and understands the effort needed to master new and difficult ideas. Consistent with that, I will be giving you more freedom than usual to learn this material in a manner that suits you. Of course, with freedom comes responsibility.

Study the material before the lectures, work the exercises early and diligently, tidy up your class notes each evening, and ask questions. Arriving late to class, or having conversations with others during class, not only disrupts your peers, but tells me you are not serious about your education.

Combinatorics is important for many problems in computer science and allied fields (like cryptology), is fundamentally the main part of simple probability questions, and is useful in other fields of mathematics, such as abstract algebra. Many optimization questions (scheduling, vehicle routing, etc.) rely heavily on ideas from combinatorics. Its also a major component of problems classified as recreational mathematics (puzzles and games).

Conduct

Daily attendance is required, expected, and overall a pretty good idea. Class will begin on-time, so be here, settled-in and ready to go. In other words, walking in the door at the exact time class is to begin is not considered arriving on-time. Repeated tardieness and absences will result in grade penalties, in accordance with university policies. Do not leave class during the lecture unless your continued presence would be a greater interuption — fill your water bottles, use the toilet, and so on, in advance. I do not care how much food or drink you bring to class, so long as it does not distract others or make me hungry. Please do not offer me sweets. Please keep phones in your pocket or bag, unless you are using them to read course material. In short, we are here to learn and discuss mathematics together. It is your responsibility to not distract your peers who are serious about their education or distract me as I endeavor to make the best use of the class time for you and your colleagues.

University Notices

These are two notices the university administration requests we relay to you.

Student Accessibility and Accommodation

“If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Peggy Perno, Director of the Office of Accessibility and Accommodation, 105 Howarth, 253.879.3395. She will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.”

I request that you give me at least two full working days to respond to any requests from this office.

Classroom Emergency Response Guidance

Please review university emergency preparedness and response procedures posted at http://www.pugetsound.edu/emergency/. There is a link on the university home page. Familiarize yourself with hall exit doors and the designated gathering area for your class and laboratory buildings.

If building evacuation becomes necessary (e.g. earthquake), meet your instructor at the designated gathering area so she/he can account for your presence. Then wait for further instructions. Do not return to the building or classroom until advised by a university emergency response representative.

If confronted by an act of violence, be prepared to make quick decisions to protect your safety. Flee the area by running away from the source of danger if you can safely do so. If this is not possible, shelter in place by securing classroom or lab doors and windows, closing blinds, and turning off room lights. Lie on the floor out of sight and away from windows and doors. Place cell phones or pagers on vibrate so that you can receive messages quietly. Wait for further instructions.

Tentative Daily Schedule
Monday Tuesday Thursday Friday
Aug 29
Syllabus
Start Unit:
Basic Counting
Aug 30
Sep 1
Sep 2
Sep 5
Labor Day
Sep 6
Sep 8
Sep 9
Sep 12
Discussion
Drop w/out Record
Sep 13
Sep 15
Sep 16
Sep 19
Sep 20
Sep 22
Discussion
Sep 23
Exam 1
Basic Counting
Sep 26
Start Unit:
Advanced Counting
Sep 27
Sep 29
Sep 30
Oct 3
Oct 4
Oct 6
Oct 7
Oct 10
Discussion
Oct 11
Oct 13
Oct 14
Mid-Term
Oct 17
Fall Break
Oct 18
Fall Break
Oct 20
Oct 21
Discussion
Oct 24
Exam 2
Advanced Counting
Oct 25
Start Unit:
Graph Theory
Oct 27
Oct 28
Oct 31
Nov 1
Nov 3
Nov 4
Drop w/ Auto W
Nov 7
Discussion
Nov 8
Nov 10
Nov 11
Nov 14
Nov 15
Discussion
Nov 17
Exam 3
Graph Theory
Nov 18
Start Unit:
Block Designs
Nov 21
Nov 22
Nov 24
Thanksgiving
Nov 25
Thanksgiving
Nov 28
Nov 29
Dec 1
Dec 2
Dec 5
Discussion
Dec 6
Exam 4
Block Designs
Dec 8
Reading Period
Dec 9
Reading Period
Final Examination: Wednesday, December 14, Noon
Topics and Texts
Topic KT L G DL B
Introduction 1 0.1 1.1
(Binary) Strings 2.1 1.2 1.4
Addition Principle 1.1 1.2 2.3
Multiplication Principle 1.1 1.2 2.1
Permutations 2.2 1.3 1.2 2.2
Combinations 2.3 1.2 1.2 2.4.1
Ordered Set Partitions 2.7 1.5
Ordered Integer Partitions 1.5 1.5
Binomial Coefficients 2.5, 2.6 1.2 1.3 2.4.2
Multinomial Coefficients 2.7
Inclusion-Exclusion 7 1.6 2
Set Partitions 1.8
Recurrence Relations 9 2 3.4 8
Generating Functions 8 5.1 3 8.5
Graph Theory Basics 5.1 4.1 4.4, 5.1 9.1
Eulerian, Hamiltonian 5.3 4.4 5.2, 5.3 9.4
Trees 5.5 10
Planarity 5.5 4.2 5.10 9.6
Coloring 5.4 4.3 5.4, 5.8, 5.10 9.6

Suggested Exercises
Topic Exercises
Introduction Discern Floor 4 tile patterns
Addition, Multiplication Principles L.1.1.1, L.1.1.2, L.1.1.3, L.1.1.4, L.1.1.11, L.1.1.13
G.1.2.3, G.1.2.5
DL.2.3.10, DL.2.1.2, DL.2.1.3, DL.2.1.5
Permutations and Combinations KT.2.9, 1–14
L.1.3, 1–14
G.1.2, 1–7
DL.2.4.5, 1–4, 7–11, 13, 14, 16, 18
Ordered Set Partitions KT.2.9, 31, 32
Ordered Integer Partitions L1.5, 1-4, 7-9, 11
Binomial, Multinomial Coefficients KT.2.9, 20, 21, 29, 30
L.1.2, 8, 9, 13
G.1.3, 2, 3, 5, 7, 8, 9, 11, 12, 13, 15–18
Inclusion-Exclusion KT.7.7, 1–21
L.1.6, 1–11
G.2.1, 2
Recurrence Relations KT.9.8, 2, 3, 4, 11, 13
L.2.4, 1–12
G.3.4, 1–9
DL.8.3.5, 1–9, 16
Generating Functions KT.8.8, 2, 3, 4–19
KT.9.9, 15, 16, 17
L.5.1, 1, 2, 5, 8, 9, 10, 13, 14, 15
G.3.1, 4, 5, 6, 7, 9
DL.8.5.7, 1–6, 9, 10
Graph Theory Basics KT.5, 1–5, 7
L.4.1, 1–6, 8
G.5.1, 1–12
Eulerian, Hamiltonian KT.5, 8–12
L.4.4, 1–11
G.5.2, 1–4
G.5.3, 1–3
DL.9.4, 1–6
Trees KT.5, 6, 36, 37–42
G.5.5, 1–6
DL.10.1, 1–5
Planarity KT.5, 29–32
L.4.2, 1–10
DL TBA
Coloring KT.5, 13–17
L.4.1, 6, 7
L.4., 1–11
G.5.4, 2, 3
G.5.8, 1–4
G.5.10, 1
DL TBA