Version as of April 25, 2011. Syllabus is updated (for FINAL) According to the FIFTH EDITION.
Still more than 40% of credit is ahead of us. Keep working!
(Previous versions: Feb 25: HWs instead of quizes, Feb 21: office hours changed, Feb 4: updated after the snow emergency, Jan 28: 5th edition added, Jan 25: first version)
This site is updated according to the new textbook, the 5th Edition
This is our official textbook now. (I will indicate by a '(4th)' the old numbering wherever I could.)

MATH 413 (Spring 2011) Intro to Combinatorics MWF10 at 445 Altgeld Zoltan Furedi

The aim of this course is to give an introduction to finite mathematics, like enumerations, sieve method, designs and other symmetric configurations, (no or very little about graphs). We emphasize techniques, but also present proofs of theorems.

LECTURES, DISCUSSION: Monday, Wed. and Friday 10:00-10:50 in 445 Altgeld.

INSTRUCTOR: Prof. Zoltan Furedi, 233B Illini Hall
Telephone 333-3355.
E-mail address: z-furedi@illinois.edu

OFFICE HOURS: Monday and Wednesday 2:00-2:50
I can often see you if you come by without an appointment (whether or not during office hours).

TEXT: Introductory Combinatorics, by Richard A. Brualdi, Prentice-Hall, 2010, Fifth Edition
(Below I am using 2004, Fourth Edition numbers, I will update Exercise numbers later)
We leave out (among others) entirely Chapters 4, 9, 11-14.

SYLLABUS:

What is Combinatorics: Sections 1.1, 1.3 only. Class hours: 3

Pigeonhole: Chapter 3 entirely except 3.3 (4th: Ch. 2.1, 2.2) 2 hours

Permutations and Combinations: Chapter 2 entirely except 2.6 (4th: Ch. 3) 4 hours

Binomial coefficients: Chapter 5 except 5.6 (antichains: pp. 141-143 in 5.3 only for honor studets and for 4 credit) (4th: 5.2+5.3 is now one chapter) 6 hours

Inclusion-Exclusion: Chapters 6.1, 6.2, 6.3, 6.4, and formula for phi(n) on the bottom of page 195/ top 196. 4 hours

Recurrence and generating functions: Chapter 7. including 7.6 but leaving out diff equations. (4th: minus 7.7) 7 hours

Special sequences (Catalan, Stirling): Chapters 8.1 multip. schemes are replaced by planar binary trees, 8.2 till the Bell numbers (no neeed for Stirling number of the 1st kind), 8.4 and Thm 8.5.2 on page 303. 3 hours

Combinatorial Designs: Chapter 10.1, 10.2, 10.3 minus resolvability pp 367-368, 10.4 only pp. 369-371. 4 hours

Exams + leeway + tutoring session 6+3+3

Total 42+3


HOMEWORK: originally, only recommended homeworks were assigned. and were QUIZES once a week (on Wednesdays) whose questions came directly from the homework.
From now on, (Feb 25), to save class time THERE ARE HOMEWORKS, due Fridays, but no more quizes.

HOURLY EXAMS: Three evening exams are planned tentatively Feb 16, March 16, and April 13 at 6:00-7:50 pm (all Wednesdays) in our usual classroom 445 Altgeld.
If you can not make it, then please send me an e-mail (in time!) to discuss a makeup exam.
If it does not fit into your university schedule, send an e-mail NOW.

FINAL EXAM: The final exam will be on May 6, Friday, 8:00-11:00am, here in our usual classroom.

GRADING: Quizes (Homework) -- 18% ; Hour Exams -- 3x14% ; Final Exam -- 40%

NO CLASS: on Jan 19, 21, March 18, April 15, May 2, 4.
However we have three two-hour evening exams, (Feb 14, March 14, April 13, all Wednesdays, 6:00-7:50) and
three evening tutoring session (March 9, April 6, April 20, all Wednesdays, 6:00-6:50).
No classes on March 21--25 (Spring break!).

HW (in the 5th Edition)

HW 4 due at 10:05 am, March 4, Friday

Ch.5 page 154-160: Exercise 21, 22, 25, 39, 40, 46, Ch.6 page 198-200: Exercise 3, 7

HW 5 due at 10:05 am, March 11, Friday

Ch.6 page 198-200: Exercise 1, 4, 5, 8, 12, 17, 24, 25

HW 6 due at 10:05 am, April 1, Friday

Ch.7 page 257-264: Exercise 1, 2, 3, 5, 18, 19, 31, 32

HW 7 due at 10:05 am, April 8, Friday

Ch.7 page 257-264: Exercise 33, 34, 35, 38, 43, 44, 46, 47

HW 8 due at 10:05 am, April 22, Friday

Ch.8 page 315-317 : Exercise 1, 6, 8, 9, 10, 12, 15, 19

HW 9 due at 10:05 am, April 29, Friday

Ch.10 page 388-394: Exercise 1, 3, 10, 12, 13, 16, 18, 19

Recommended HW (in the 5th Edition)

Ch.1 page 20-22: Exercise 1, 2, 3, 4, 5, 7, 8, 9, 20

Ch.3 page 83-84: Exercise 3, 4, 5, 8, 12, 14, 15, 16, 17, 18

Ch.2 page 60-66: Exercise 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 19, 20, 28, 29, 30, 31, 34, 37, 38, 41, 45

Ch.5 page 154-160: Exercise 2, 3, 4, 5, 6, 7, 8, 11, 13, 14, 16, 20, 21, 22, 25, 46

Ch.6 page 198-200: Exercise 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 17, 24, 25

Ch.7 page 257-264: Exercise 1, 2, 3, 4, 5, 17, 18, 19, 31, 32, 33, 34, 35, 36, 38, 39, 43, 44, 46, 47

Ch.8 page 315-317 : Exercise 1, 2, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19

Ch.10 page 388-394: Exercise 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 37, 58, 59, 60, 61

Same recommended HW according to the 4th Edition
(One more problem here!)

Ch.1 page 20-22: Exercise 1, 2, 3, 4, 5, 6, 8, 9, 10, 21

Ch.2 page 40-41: Exercise 3, 4, 5, 8, 12, 14, 15, 16, 17, 18

Ch.3 page 75-81: Exercise 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 19, 20, 28, 29, 30, 31, 34, 37, 38, 41, 45

Ch.5 page 153-158: Exercise 2, 3, 4, 5, 6, 7, 8, 11, 13, 14, 16, 20, 21, 22, 25, 45

Ch.6 page 200-202: Exercise 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 17, 24, 25

Ch.7 page 259-264: Exercise 1, 2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 19, 20, 23, 24, 26, 27, 35, 36, 37

Ch.8 page 317-319 : Exercise 1, 2, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19

Ch.10 page 415-421: Exercise 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 37, 58, 59, 60, 61

TENTATIVE SCHEDULE
Jan 19, 21: --- classes are cancelled. We have a slow start, but please keep doing HWs.

Jan 24, Monday: The combinatorial explosion, pigeon hole, infinite descent (root 2 is irrational)
Jan 26, Wednesday: Covering the board, Chapter 1.1
Jan 30, Friday: Cutting the cube + Chapter 1.3 (4th: 1.2, 1.4)

Jan 31, Monday: Pigeon hole, Chapter 3.1 (4th: 2.1)
Feb 2, Wednesday: No class. Snow emergency
Feb 4, Friday: Chapter 3.2 (4th: 2.2)

Quiz 1

Feb 7, Monday: Permutations and Combinations: Chapter 2.1 and 2.2 (4th: 3.1 and 3.2)
Feb 9, Wednesday: Chapter 2.3 (4th: 3.3)

Quiz 2
Feb 11, Friday; Chapter 2.4 (4th: 3.4)

Feb 14, Monday: Chapter 2.5 (4th: 3.5)
Feb 16, Wednesday: review class in the morning

Evening EXAM 1, 6-7:50 pm in our usual classroom, 445 Altgeld.
Feb 18, Friday; The binomial theorem: Chapter 5.1

Feb 21, Monday: Chapter 5.2 (4th: 5.2+5.3)
Feb 23, Wednesday: Chapter 5.3 (4th: 5.4)

Quiz 3
Feb 25, Friday: Chapter 5.4 (4th: 5.5)

Feb 28, Monday: Chapter 5.5 (4th: 5.6)
March 2, Wednesday: review of Chapter 5
March 4, Friday: Inclusion--Exclusion: Chapter 6.1

HW 4 due at 10:05 am

March 7, Monday: Chapter 6.2
March 9, Wednesday: Chapter 6.3

Evening tutoring session, 6-6:50 pm in our usual classroom, 445 Altgeld.
March 11, Friday: Chapter 6.4

HW 5 due at 10:05 am

March 14, Monday: Recurrences: Chapter 7.1
March 16, Wednesday: review class in the morning

Evening EXAM 2, 6-7:50 pm in our usual classroom, 445 Altgeld.
March 18, Friday: No class

March 21-25, --- No class, Spring break

March 28, Monday: Chapter 7.2
March 30, Wednesday: Chapter 7.3
April 1, Friday: Chapter 7.4

HW 6 due at 10:05 am

April 4, Monday: Chapter 7.5
April 6, Wednesday: review of Chapter 7

Evening tutoring session, 6-6:50 pm in our usual classroom, 445 Altgeld.
April 8, Friday: Chapter 7.6

HW 7 due at 10:05 am

April 11, Monday: Special sequences: Chapter 8.1
April 13, Wednesday: review class in the morning

Evening EXAM 3, 6-7:50 pm in our usual classroom, 445 Altgeld.
April 15, Friday: no class

April 18, Monday: Chapter 8.2
April 20, Wednesday: Chapter 8.3

Evening tutoring session, 6-6:50 pm in our usual classroom, 445 Altgeld.
April 22, Friday: Designs: Chapter 10.1

HW 8 due at 10:05 am

April 25, Monday: Chapter 10.2
April 27, Wednesday: Chapter 10.3
April 29, Friday: Chapter 10.4 last lecture.

HW 9 due at 10:05 am

May 2, Monday: No class
May 4, Monday: No class
--------
May 6, Friday: 8:00-11:00 am, FINAL EXAM in our usual classroom (445 Altgeld).

WEB: https://math.uiuc.edu/~z-furedi/TAN/413math_2011.html