|
| Professional |
| Classes |
| Hobbies |
| Useful Links |
Enumerative Combinatorics
Questions or Comments?
- Send me email (click here and delete my initials at end).
- Homepage: http://www.math.uconn.edu/~troby
- Office: MONT 239; Phone: 860-486-8385
- Office hours: Tues/Thurs 3:20–3:45, right after class, and by appointment in MONT 239. You can often find me in my office on TuTh mornings. I'm happy to answer questions or schedule appointments by email, which I check frequently.
Class Information
COORDINATES: Classes meet Tuesdays and Thursdays 2:00-3:15 in MONT 245. The registrar calls this Section 001.
PREREQUISITES: MATH 5120 (Graduate Abstract Algebra) or consent of instructor.
TEXT: Richard P. Stanley: Enumerative Combinatorics 1 (2nd edition) & 2. A near-final version of EC1Ed2 (useful for searching) and many other resources can be downloaded therefrom. It's a good idea to start reading the text as early as possible.
OTHER REFERENCES: The following texts and treatises are at the graduate or advanced undergraduate level. They may provide useful alternative points of view or more leisurely presentations of some of the material we will cover. (I'm not including here the much longer list of books concerned with more specialized topics related to representation theory, polytopes, etc.)
- M. Aigner: Combinatorial Theory (Classics in Mathematics), Springer, 1979 (reprint 2013).
- M. Aigner: A Course in Enumeration (GTM), Springer, 2007.
- M. Bona: Combinatorics of Permutations, Chapman and Hall/CRC, 2004.
- M. Bona: Introduction to Enumerative Combinatorics, McGraw-Hill, 2005.
- M. Bona: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, 2002, 2006, 2011.
- L. Comtet: Advanced Combinatorics, Reidel/Kluwer, 1974.
- I. Goulden & D. Jackson: Combinatorial Enumeration, Wiley, 1983; Dover reprint, 2004.
- J. van Lint & R. Wilson: A Course in Combinatorics, Cambridge, 2001.
- R. Merris: Combinatorics, Wiley, 2003.
- R. Stanley: Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Springer UTM, 2013.
- H. Wilf: Generatingfunctionology,
Academic Press 1990, 1994: A. K. Peters, 2006. (2nd edition is
WEB RESOURCES: The homepage for this course is http://www.math.uconn.edu/~troby/math5020s17.
SOFTWARE: While doing some computations by hand is generally essential for learning, having software that can do bigger computations or check one's work is very useful. The free open-source computer algebra system Sage has an extensively-developed collection of objects and algorithms for algebraic combinatorics with various documentation including thematic tutorials. More generally, Christian Krattenthaler has kindly compiled a comprehensive list of Combinatorial software and databases.
GRADING: Your grade will be based on several HW assignments, and possibly a short oral exam given near the end of the term. Assignments will consists of problems at a variety of difficulty levels, of which you are to hand in at most 3–4. You should only write up carefully and hand in your best work, i.e., the hardest problems you were able to solve well. It's fine to do the easier problems if you're new to combinatorics or too busy with more important things (like giving job talks). This won't count against your grade.
The text is loaded with exercises, most of them with solutions, though the latter often are brief outlines, sometimes with pointers to the research literature. Stanley's knowledge of the subject is encylopedic, and he was able include a large amount of interesting material this way. If I assign an exercise whose solution is already included, I'll expect much more detail in what you hand in. I recommend you browse through many of the unassigned exercises to get a sense for what's there.
You may find some homework problems to be challenging, leading you to spend lots of time working on them and sometimes get frustrated. This is natural. I encourage you to work with others, or to ask me for hints. It's OK to get significant help from any resource, but in the end, please write your own solution in your own words. Do not simply copy another student's work or obtain a solution from an outside source. Copying someone else's work without credit is plagiarism and will be dealt with according to university policy. More importantly, it is a poor learning strategy.
HOMEWORK PROBLEMS: Problem assignments and details on how problems are weighted is available here.
ACADEMIC INTEGRITY: Please make sure you are familiar with and abide by Policy on Scholarly Integrity in Graduate and Post-Doctoral Education and Research.
ACKNOWLEDGEMENTS: Many people have influenced my approach to this material, particularly Richard Stanley, but also Ira Gessel, Jim Propp, and Gian-Carlo Rota. This term my initial plan is to follow the lectures Stanley gave at MIT in Fall 2016 when he taught a version of this course, but with whatever modifications make sense.
CONTENT: Enumerative Combinatorics is a beautiful and deep subject which has lately forged strong connections with many other parts of mathematics. This course will focus on the basic techniques of enumeration, with a strong emphasis on generating functions and bijective proofs. In particular, the initial plan is to cover much of Chapters 1,2,4,5, and 6 of EC1 and EC2, leaving out the large chapters on partially-ordered sets and symmetric functions, each of which could be a course on its own.
ACCESSIBILITY & DISABILITY ISSUES: Please contact me and UConn's Center for Students with Disabilities as soon as possible if you have any accessibility issues, have a (documented) disability and wish to discuss academic accommodations, or if you would need assistance in the event of an emergency.
LEARNING: The only way to learn mathematics is by doing it! Complete each assignment to the best of your ability, and get help when you are confused. Come to class prepared with questions. Don't hesitate to seek help from other students. Sometimes the point of view of someone who has just figured something out can be the most helpful.
| 5020 LECTURE SCHEDULE | |||
|---|---|---|---|
| |
Section | |
|
| 1/17 T | §1.1 | How to count, generating functions | |
| 1/19 R | §1.2 | Generating functions, binomial coefficients | |
| 1/24 T | §1.2 | Compositions, multisets, multinomial coefficients | |
| 1/26 R | §1.3 | Permutations: cycles, cycle indicators, Renyi-Foata map | |
| 1/31 T | SNOW DAY (Class cancelled) | ||
| 2/2 R | §1.3 | Stirling numbers (1st kind), q-counting inversions | |
| 2/7 T | §1.7 | q-counting inversions for multiset permutations, q-multinomial coefficients, integer partitions | |
| 2/9 R | SNOW DAY (Class cancelled) | ||
| 2/14 T | §1.4, 1.7 | q-binomial coeff. count partitions in rectangle, permutation descents | |
| 2/16 R | SICK DAY (Class cancelled) | ||
| 2/21 T | § 1.4 | Eulerian polynomials & Eulerian numbers, summing dth powers. | |
| 2/23 R | §1.4–5 | Alternating permutations, Tree representations of permutations | |
| 2/28 T | §1.8 | Integer partition identities | |
| 3/2 R | §1.8 | Euler's pentagonal number theorem | |
| 3/7 T | §1.8+ | Jacobi's triple product formula, Jacobi's identity, Ramanujuan's p(5k+4) congruence. | |
| 3/9 R | §1.9 | Sti2ling numbers (2nd kind) | |
| 11–19 MARCH SPRING BREAK (NO CLASS MEETINGS) | |||
| 3/21 T | §2.1 | Sieve methods Principle of Inclusion-Exclusion (PIE) | |
| 3/23 R | §2.2 | Generalized PIE, derangements, Sti2ling Numbers. | |
| 3/28 | §2.2 | Counting and q-counting permutations by descent set | |
| 3/30 R | §5.1 | Products and compositions of generating functions (20min before Number Theory Day) | |
| 4/4 T | §5.1 | The Compositional and exponential formulae | |
| 4/6 R | §5.1–2 | Examples of compositional and exponential formulae | |
| 4/11 T | §5.1–2 | Permutation version of exponential formula, more examples | |
| 4/13 R | §5.3 | Enumerating trees and symmetric matrices with all line sums 2 | |
| 4/18 T | §5.4 | Lagrange inversion, enumerating k-ary trees | |
| 4/20 R | §5.5 | Enumeration of matrices with all line sums 2 | |
| 4/25 T | §5.6 | Directed graph version of Matrix-Tree theorem | |
| 4/27 R | §5.6 | Matrix-Tree theorem and applications | |
Web Resources
- The Electronic Journal of Combinatorics has high quality survey articles as well as cutting-edge research;
- A longstanding series of conferences in Europe with concommitant journal, the Séminaire Lotharingien de Combinatoire;
- Sage-Combinat is the open source extensible toolbox which has made Sage extremely useful for students and researchers in algebraic combinatorics. A thematic tutorial linked to Stanley's undergraduate algebraic text has been started here by Anne Schilling;
- Federico Ardila has bravely videotaped his graduate-level courses in a variety of topics in combinatorics (Enumeration, Combinatorial commutative lagebra, Coxeter groups, Hopf algebras, Matroids, Polytopes) and made them available.
NEWS, NOTES, AND HANDOUTS
Handouts
Back to my home page.