\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Course Information}
\centerline{Spring 2005}
\bigskip
\leftline{{\it Professor:}  John Little}
\leftline{{\it Office:} Swords 335}
\leftline{{\it Office Phone:}  793-2274}
\leftline{{\it Office Hours:}  M-F 10-11, TR 1-3, and by appointment}
\leftline{{\it Course Homepage:} 
{\tt http://mathcs.holycross.edu/\~{}little/Combo05/ComboHome.html}}

\bigskip
\noindent
{\it Course Description}
\bigskip
\noindent
Combinatorics is a wide-ranging applied and pure mathematical discipline
that deals with questions concerning {\it combinations\/} or 
{\it arrangements\/} of objects, usually from a finite set.  For instance,
the arrangement might be an {\it ordering} of the objects in the finite
set, and we might ask whether an ordering with a certain property
(for instance, where some specified elements are not adjacent)
exists, and if so, how many of them are there?  Generalizing this, 
the basic questions addressed in combinatorics can be broken down into two groups:
\bigskip
\item{1)} {\it Existence\/} questions:  Do arrangements of a particular
type, or with specified properties exist?
\item{2)} {\it Enumeration\/} or counting questions:  If arrangements
of a particular type do exist, how many distinct ones are there? 
\bigskip
\noindent
This course will offer a breadth-first introduction to the subject
as a whole.  We will investigate a representative sampling of combinatorial
problems, and introduce a number of general techniques for solving them.
When we make connections with other classes you have taken,
we will be drawing primarily on ideas from Algebraic Structures and Linear Algebra,
so this course satisfies the Algebra distribution area requirement for 
the Mathematics major.

\bigskip
\noindent
The topics we will study this semester are:
\bigskip
\item{1)}  Counting techniques: permutations and combinations, binomial
and multinomial coefficients, recurrence relations, generating functions,
counting with symmetry (Polya's Theorem).
\item{2)}  Techniques for existence questions: Pigeonhole principle, 
parity arguments, Hall's ``marriage'' theorem.
\item{3)}  Numerous examples of various types.
\bigskip
\noindent
Because of the many interconnections between these subjects, we will
not be studying them in sequence; rather we will develop the techniques
and the  examples in tandem, following more or less the ordering of 
the chapters in our text.  A more detailed day-by-day schedule is
maintained on the course homepage if you want to see how the semester
breaks down that way.

\bigskip
\noindent
{\it Text}
\bigskip
The text for the course is {\it Introductory Combinatorics, 4th ed.\/} by 
Richard Brualdi, published by Pearson Prentice Hall in 2004.  
We will study the material from Chapters 1, 2, 3, 4, 5, 6, 7, 9, 11, 14 this term. 
The remaining chapters can serve as excellent bases for final projects
(see below).

\bigskip\noindent
{\it Course Format}
\bigskip
In order for a student to get as much as possible out of this or any
course, regular active participation and engagement with the ideas
we discuss are necessary.  This is especially true in a subject like
combinatorics where {\it the best way to learn the material is to 
solve lots of problems using the key ideas.  Indeed, a major portion
of what you should get out of this course is greater confidence and 
skill in solving problems.}
To get you more directly involved in the subject matter of this course,
regularly throughout the semester, the class will break down into groups
of roughly 4 students for one or more days, and each group will work 
individually on a group discussion exercise.
I will be responsible for designing and preparing these exercises, and 
 I will be available for questions
and other help during these periods.  At the conclusion of each 
discussion, the class as a whole will reconvene to talk about what has
been done, to sum up the results, to hear short oral reports from each group,
etc.  Each group will keep a written record of the group's
observations, results, questions, etc. which will be handed in.  I will
make copies of these, and return them with comments.  Other meetings 
of the class will also be structured as 
lectures when that seems appropriate.
\bigskip\noindent
{\it Grading}
\bigskip
\noindent
The assignments for the course will consist of:
\medskip
\item{1.} Two midterm exams  
together worth $30\%$ of the course grade.  Tentative dates:
\itemitem{a.}  Friday, February 25.
\itemitem{b.}  Friday, April 15.
\item{2.} Final exam worth $25\%$ of the course grade.  The final exam for 
this course is scheduled for 8:30 a.m. on Thursday, May 12.  
\item{3.} Individual Problem sets worth $20\%$ of the course grade.
\item{4.} Group discussion writeups, worth $10\%$ of the course grade.
\item{5.} Group final project, worth $15\%$ of the course grade.  More
information about the projects will be distributed later in the semester.  
\bigskip
If you ever have a question about the grading policy, or about your 
standing in the course, please feel free to consult with me.
\bye
   
