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 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.