Delaware State University
DOVER, DE 19901

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]

Instructor: Tristan Hübsch, ETV 103, (302) 857-6603, thubsch@mac.com, thubsch@desu.edu
Office hours: M: 2:00–4:30 pm, T: 6:00–7:30 pm, R: 2:00–4:00 pm
Textbook (required): Fred Roberts and Barry Tesman, Applied Combinatorics (2nd ed.)

Grading recipe (no make-ups are given, except in cases of proven medical emergency):

Component

Time

Remark

% of Grade

Homework

See in daily schedule

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!


Topical schedule:

§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


Day-to-day schedule: Students are required to read ahead

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


Homework assignments

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


Return to my Welcome!, or check out my [Curriculum Vitae][Research][Other Interests]