Math 413
INTRODUCTION TO
COMBINATORICS
Sections B13 and B14
Instructor: Alexandr V. Kostochka
Office: 234 Illini Hall
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
E-mail:
kostochk@math.uiuc.edu
Time and place: 9am-9:50am MWF, 441 Altgeld Hall
Final exam: Monday, May 9 at 8 am
Office hours: 3-4pm MWF, and by
appointment
- Current homework
HW13: P. 317-318, # 12(c,d), 16, 22(a), 26(b,c,d). P. 416, # 7.
- Past homework
HW1: P. 23-24, # 26, 27, 31, 32, and 36.
HW2: P. 21-22, # 8, 12, 15, 18; P. 40, # 5.
HW3: P. 40-43, # 10, 12, 23, 26; P. 76, # 7(a,e,f).
HW4: P. 77-80, # 14, 19, 21, 38, 40(a,b).
HW5: P. 81, # 45, 47; P. 154, # 16; P. 120-122, # 36, 49.
HW6: P.155-158, # 18, 30, 31, 41, 45.
HW7: P. 200-202, # 2, 6, 8, 13, 24(a).
HW8: P. 259-262, # 1(b,c), 3, 18, 19(b,d,e); P. 203, # 27.
HW9: P. 261-262, # 12, 14, 15, 24, 26.
HW10: P. 262-264, # 27, 28(b,c,e), 29(b,d,e), 31, 34.
HW11: P. 262-265, # 27 (using generating functions), 40, 42(b,c), 44.
(Problem 27 is counted as two problems.)
HW12: P. 264-265, # 41, 46. P. 317-318, # 2,3,4.
- Class info and handouts:
[pdf], [pdf],
[pdf],
- Class log
Class Announcements
We have help sessions on Mondays
from 5pm to 6:30pm at 147 Altgeld Hall
Topics covered by the Final are
1. Covers of chessboards (Section 1.1).
2. Cutting a cube (Section 1.2).
3. Magic squares (Section 1.3).
4. Orthogonal Latin squares (Section 1.5).
5. The game of Nim (Section 1.7).
6. Pigeonhole principle (Sections 2.1 and 2.2).
7. A theorem of Ramsey (Section 2.3).
8. Basic counting principles (Section 3.1).
9. Counting mappings (Supplement).
10. Counting permutations of sets and multisets (Sections 3.2 and 3.4).
11. Counting combinations of sets and multisets (Sections 3.3 and 3.5).
12. Pascal's formula (Section 5.1).
13. The binomial theorem and binomial identities (Sections 5.2 and 5.3).
14. The multinomial theorem (Section 5.5).
15. Relations and their properties (Section 4.5+ Solution to hw 5).
16. Partial orders and equivalence relations (Section 4.5)
17. Covering partial orders by antichains and chains (Section 5.7).
18. Newton's binomial theorem (Section 5.6).
19. The inclusion-exclusion principle (Section 6.1).
20. Derangements (Section 6.3) and the number of onto functions (Supplement).
21. Permutations with forbidden positions (Section 6.4).
22. Permutations with forbidden relative positions (Section 6.5).
23. Some number sequences (including arithmetic, geometric and Fibonacci
sequences) (Section 7.1).
24. Linear homogeneous recurrence relations (Section 7.2).
25. Wandermonde's determinants (Section 7.2).
26. Linear nonhomogeneous
recurrence relations with constant coefficients (Section 7.3).
27. Generating functions and their use to solve recurrences
(Sections 7.4 and 7.5).
28. Exponential generating functions (Section 7.7).
29. Catalan numbers (Section 8.1).
30. Stirling numbers of the second kind (Supplement and Section 8.2).
31. Partition numbers (Supplement and Section 8.3).
32. Modular arithmetic (Section 10.1).
33. Block designs (Section 10.2).
Last changed on April 30, 2005.