Department of Applied Mathematics & Theoretical Physics -- (302) 857-7516 (main), -7517 (fax)
Combinatorics
Math-641 (17595) : TR,
4:30–5:45 pm, place TBA
[Topics][Daily
Schedule][Assignments][Welcome]
Grading recipe (no make-ups are given, except in cases of proven medical emergency):
Component |
Time |
Remark |
% of Grade |
---|---|---|---|
Late HW = 0 credit !!! |
60% |
||
Term-paper |
Last week of semester |
Chosen topic |
40% |
Combinatorics (Math 641) is a course that introduces some essential topics in discrete, combinatorial mathematics and samples their applications in sciences and otherwise. paraphrasing from the text: The applications that motivate both the development and also the use of combinatorics are expanding, and occur throughout the sciences, both natural and social, but also in practical daily life and business, such as scheduling complex inter-related tasks and activities. It is important to identify the common underlying principles, methods and techniques, as they can then freely be used in a vast variety of applications.
“Success
= 1% inspiration + 99% perspiration”--T.A. Edison
But, learning is still 100% learning!
§1: What is combinatorics
§2: Basic counting rules
§3: Introduction to graph theory
§4: Relations
§5: Generating functions and their applications
§6: Recurrence relations
§7. The principle of inclusion and exclusion
§8: The Pólya theory of counting
01/15: Introductory
Matters §1.1–2
Basic Counting Rules
01/17: Counting rules, strategies and caveats:
§2.1–4
01/22: More on counting rules, strategies and caveats:
§2.5–10
01/24: Multinomials, permutations and simple
games—incl. legislatures: §2.11–16
01/29: Generating subsets, good algorithms, and the
pidgeonhole principle: §2.17–19
Introduction to Graph Theory
01/31: Fundamentals of graph theory: §3.1–2
02/05: Graph colorings: §3.3
02/07: Chromatic polynomials and trees:
§3.4–5
02/12: Applications of rooted trees: §3.6
02/14: Graph theory methods
in representation theory: extra
02/19: Adinkras: graphs for
supersymmetry representaions: extra
Relations
02/21: Binary
and order relations: §4.1–2
02/26: Linear extensions of partial orders: §4.3
02/28: Lattices and Boolean algebras, §4.4
Generating Functions
03/04: Generating functions: examples, operations and
applications, §5.1
03/06: Binomial theorem, and the exponential generating
function: §5.4–5
03/11: Relations to probability, and the Coleman and Banzhaf
indices: §5.6–7
03/13: Generating functions
in algebraic geometry: extra
03/17-21: Spring
Recess
03/25: Generating functions from
string theory and mirror symmetry: extra
Recurrence Relations
03/27: Recurrence relations: examples, and the method of characterisitc
roots: §6.1–2
04/01: Generating functions and convolutions:
§6.3–4
04/03: The principle of Inclusion and Exclusion: §7.1
The Principle of Inclusion and Exclusion
04/08: The
number of objects with exactly m properties: §7.2
The Pólya Theory of Counting
04/10: Equivalence relations: §8.1
04/15: Permutation groups: §8.2
04/17: Representations of
the permutation group and Young tableaux: extra
04/22: Applications of Young
tableaux: extra
04/24: Burnside’s Lemma: §8.3
04/29: Distinct colorings, the cycle index: §8.4–5
05/01: Pólya’s theorem: §8.6
To be announced by 01/29/07
All homework assignments are due by 5:00 pm of the day indicated and should be either given to the instructor in hand, left in the instructor's mailbox in ETV#116. Late homework will not be accepted, except in cases of proven emergency.
Collaboration policy
Collaboration -- but not blind copying -- on the homework assignments is strongly encouraged; students should use this to learn from each other. All exams and quizzes are open text and open class-notes (including notebooks and class handouts), but no collaboration is allowed; by signing the exams and quizzes, the student implicitly agrees to abide by this policy. Violation of this policy is covered under University regulations on academic dishonesty and cheating.
Presentation and organization
While a neat presentation of home,- quiz- and exam-work is not required for full credit, it certainly makes it easier to assess the quality of the work and give the proper credit due. In all cases, include a simple sketch if it might help conveying the approach or the calculations. Where necessary, include all units and symbols such as the measure of an integral, arrow on a vector, vertical bars for the absolute value of a quantity, for the magnitude of a vector or for the determinant of a matrix, etc.
© Tristan Hübsch, 2007