MAIN LECTURE:

• Instructor: Fedor A. Andrianov.
• E-mail: fedandr@math.ucla.edu.
• Class meets:
  • MTWR, 12:30pm - 1:20pm in MS 5117.
• Office hours:
  • MW, 1:30pm - 3:00pm, in MS 6172.
  • Virtual Office Hours.
  • And by appointment.

DISCUSSION SESSIONS:

• Section 1a meets TR at 2:30pm - 3:20pm in MS 5117.
  • TA: Aaron Reite.

TEXTBOOKS:

• [1] Fred S. Roberts "Applied Combinatorics" Prentice Hall 1984. ISBN 0-13-039313-4.

EXAM DATES:

• Midterm: Thursday, July 22, 2004, 12:30pm - 1:20pm, in class.
• Final exam: Tuesday, August 19, 2004, 12:30pm - 1:20pm, in class.

GRADING POLICY:

• Homework is worth 35% of the grade. Midterm will count 25%. Final examination will count 40%.

MISCELLANEOUS:

1. Please consult the class web page "http://www.math.ucla.edu/~fedandr/113.1.041/" for a detailed information on class policies and procedures as well as for the latest
   • announcements,
   • homework assignments,
   • examples.
2. No make-up exams will be given.
3. Please bring you UCLA identification card to the exams.
4. You are not allowed to consult books or notes during the exams.
5. I do not give incompletes, except in cases of extreme human tragedy.
6. Please note that I neither read anonymous posts and/or anonymous e-mails, nor (moreover) reply to such posts and/or e-mails. I am sorry for any inconvenience.

AN OVERVIEW:

1. Product and Sum rules, permutations (Sections 2.1 - 2.5);
2. Subsets, combinations, binomial coefficients (Sections 2.6 - 2.8, 2.15);
3. Probability, sampling with replacement (Sections 2.9 - 2.10);
4. Occupancy problems (Section 2.11);
5. Generating functions (Section 4.1);
6. Operating on generating functions, sampling (Sections 4.2, 4.3.1);
7. Occupancy problems, binomial theorem (Sections 4.3.2, 4.4);
8. Exponential generating functions (Section 4.5);
9. Recurrence relations (Section 5.1);
10. Recurrence relations (Section 5.1);
11. The method of characteristic roots (Section 5.2);
12. Solving recurrence using generating functions (Section 5.3);
13. Principle of inclusion and exclusion (Section 6.1);
14. Principle of inclusion and exclusion (Section 6.1);
15. Number of objects having exactly n properties (Section 6.2);
16. Fundamental concepts of graph theory (Section 3.1);
17. Connectedness (Section 3.2);
18. Graph coloring (Section 3.3);
19. Chromatic polynomials (Section 3.4);
20. Max-flow, Min-cut theorem (Sections 13.1 - 13.3);
21. Max-flow, Min-cut theorem (Sections 13.1 - 13.3);
22. Depth first search, a test for connectedness (Section 11.1);
23. One-way street problem (Section 11.2);
24. Hamiltonian chains and paths, Redei's theorem (Sections 11.5, 11.6).