From laci@cs.uchicago.edu Fri Apr  8 13:08:07 2005
Date: Fri,  8 Apr 2005 12:37:26 -0500 (CDT)
From: Laszlo Babai <laci@cs.uchicago.edu>
To: hari@cs.uchicago.edu
Subject: info.tex, revised


\documentclass[12pt]{article}

\setlength{\textheight}{8.5in}
\setlength{\topmargin}{-0.4in}

\begin{document}
%\pagestyle{empty}

\begin{center}
{\large{Combinatorics and Probability, Spring 2005}}
\end{center}

This is a combination of two co-located courses,
``Honors Combinatorics and Probability''
(Math-28400 = CS-27400) and ``Combinatorics''
(Math-37200 = CS-37200).

While the class material is the same, the requirements
for the graduate credit are considerably higher than
those for the undergraduate credit.  Those seeking
graduate (37200) credit will have extra assignments
and are expected to show a deeper understanding of the
course material.

\medskip
\noindent
Instructor: L\'aszl\'o Babai \quad Ryerson 164 \quad e-mail: 
     {\tt laci@cs.uchicago.edu}. 
      Office hours: by appointment (please send e-mail)

\medskip
\noindent
TA1: Hari Narayanan \quad {\tt hari@cs.uchicago.edu}.

\noindent
TA2: Raghav Kulkarni \quad {\tt raghav@cs.uchicago.edu}.

\noindent
Hari holds office hours Monday, Tuesday, Thursday 5:30--6:30pm in Ry 255.

\vspace{.1in}
\hrule

\bigskip
\noindent
Text.  Your primary text will be your course notes, so please
    make sure you don't miss classes.  If you do, you should copy
    somebody's class notes and discuss the class with them.

Printed texts:

J. Matou\v{s}ek, J. Ne\v{s}et\v{r}{\'\i}l: 
``Invitation to Discrete Mathematics,''

available at the Seminary Coop Bookstore (University Ave. at 58th St.).

\bigskip

   L.\,Babai and P. Frankl: ``Linear Algebra Methods in
         Combinatorics,'' book manuscript, 1992.

         Available from the Dept.~C.S. office
         (Ry-152, ask Andrea, \$ 20)

\bigskip

Numerous handouts will accompany the course, including class notes,
and chapters of the Discrete Math course handouts for the
benefit of those who did not attend Discrete Math or need a
refresher.

    Recommended advanced texts:

\bigskip
    L. Lov\'asz: ``Combinatorial Problems and Exercises,''
    North-Holland 1979;\ 2nd ed. Elsevier 1992.

\bigskip

    N. Alon, J.\,H. Spencer: ``The Probabilistic Method''
      J.\,Wiley, Publ., 1992

\bigskip

  J.\,H.\,Van\,Lint and R.\,M.\,Wilson: 
    ``A Course in Combinatorics,''
      Cambridge University Press, 1992.

\bigskip
  Reinhard Diestel: ``Graph Theory''
      Springer; available online (can be downloaded but cannot be printed)

\bigskip
If you have not taken ``Discrete Mathematics'' (CS-17400) or
a similar introduction to combinatorics, number theory,
graph theory, finite probability, and asymptotic notation,
you may want to consult an introductory text, such as

\medskip
\noindent
   Richard A. Brualdi: ``Introductory Combinatorics''

\medskip
\noindent
    Alan Tucker: ``Applied Combinatorics''

\medskip
\noindent
    Kenneth Rosen: ``Discrete Mathematics and Its Applications.''

\vspace{.1in}
\hrule

\bigskip

Grading will be based on three midterm exams, the two best of which
will count (40\% each) and a take-home test (20\%).  Midterm dates: 
Wednesday, April 13; Wednesday, May 25; Wednesday, June 1.
Take-home test: Friday, April 29 (due Monday, May 2). 

Most of the test problems will previously have been assigned in 
class.  Class notes are posted on the course website; please
check for the ``revised/proofread version.''  (For the sake of
fast communication, often an unproofread copy is first distributed
in class.  These copies are clearly marked ``not proofread''
and tend to contain numerous errors.  Be sure to discard them
once the proofread copies are available.   Check the website;
the proofread copies are posted there as soon as they are
available.)

\vspace{.1in}

\hrule

\bigskip\noindent
{\sf A REQUEST.}\ Please send e-mail to the instructor
with Subject: ``comb class''

Please include the following information.  Your answers will
help me in designing the course.

\begin{itemize}
  \item Your name and the letter U or G depending on whether you seek
undergraduate of graduate credit

  \item The type of credit you seek (letter grade, P/F, audit, etc.)
     and whether or not the grade is needed to fulfill a requirement.
     (Your choice of type of credit is not binding on you, you can change
      your mind later.)

  \item Your major and grade (e.g. 3rd yr math-econ); if grad student,
the program in which you are enrolled (Math PhD, CSPP, PSD grad student
at large, etc.).

  \item Your prior experience with combinatorics,
discrete mathematics, probability, linear algebra,
elements of number theory (Fermat's little theorem,
quadratic residues, etc.)

  \item Undergraduates and non-math grad students: what proof-oriented
     math classes have you taken (please give title of each course)
\end{itemize}
\end{document}


\noindent
\begin{itemize}
\item[0.] Please PRINT your name.  On a separate sheet please answer the
  following questions:  your name, major, year, e-mail address,
  type of credit sought (letter, P/F, audit) (for my information only, 
  you may change your mind). Have you taken ``Discrete Mathematics''
  last fall?  Have you had linear algebra?  What other proof-oriented
  math courses have you taken?  (State if you are a graduate student, 
  your field of specialty, year.) 

  Please write each solution on a separate
  page because a different person may grade each.  
\item[1.] {\tt [4 points]}
   Ten people draw one card each from deck of 52 cards
   with replacement.  (The deck is well shuffled each time
   before someone draws a card.) Let $A$ denote the event that 
   all the cards drawn are distinct. Determine the probability
   of this event.
 \begin{itemize}
 \item[(a)] Describe this probability by an exact formula.
 \item[(b)] Calculate this probability to 5 significant digits of accuracy.
 \end{itemize}
%% 0.397133699
   Show all your work.

\item[2.] {\tt [5 points]} 
The {\em trinomial theorem}\ is the expansion of $(x+y+z)^n$
as a sum of {\em monomials} of the form $cx^iy^jz^k$ where
$c$ is a ``trinomial coefficient.'' Count the number of
monomials appearing in the trinomial theorem. Find a closed
form expression for the number of terms in this
expansion. (For comparison: the number of monomials in the {\em binomial
theorem} is $n+1$.) Prove your answer. (A closed form expression
may not contain the summation symbol or ``three dots'' representing
a variable number of terms.)

\end{itemize}

\end{document}

Unless expressly stated otherwise, all homework problems are due
{\em before}\/ next class.  There will be ``Grad only `` problems;
undergraduates are encouraged to hand them in for {\em bonus points}
equal to the graduate point value of the problem.  
