Math 17
An Introduction to Mathematics Beyond Calculus
Last updated June 27, 2016 13:25:43 EDT
Students are expected to give an in-class presentation on a topic of their choice. It is recommended that you work in small groups.
Each of you should speak for about 20 minutes. Below is a list of potential topics, but you are also welcome to suggest other topics and discuss them with me. You should let me know what topic you have chosen no later than February 4.
A few suggested topics for student presentations
- A combinatorial interpretation of the fibonomial coefficients.
Suggested references: [C. Savage, B. Sagan, Combinatorial interpretations of binomial coefficients analogues related to Lucas sequences, Integers 10 (2010), 697-703], see also these slides.
- (Taken by Patricia and Shawn) Derangements and the sum of the largest fixed points. For each permutation of [n] with fixed points, take the value of its largest fixed point. The goal of this project is to prove that the
sum of all these values equals D(n-1), the number of derangements of [n-1].
Suggested reference: [E. Deutsch, S. Elizalde, The largest and the smallest fixed points of permutations, European J. Combin. 31 (2010), 1404-1409].
- (Taken by Madi and Mike L.) The inversion number and the major index. Related to problems 70 and 71. The major index of a permutation is defined as the sum of all its descents (positions of entries that are smaller than the next entry).
The goal of this project is to show that for any k, the number of permutations of [n] with k inversions equals the number of permutations of [n] with major idex equal to k.
Suggested references: [R. Stanley, Enumerative Combinatorics Vol I, Prop. 1.4.6], [D. Foata, M.-P. Schutzenberger, Major index and inversion number of permutations, Math. Nach. 83 (1978), 143-159].
- De Bruijn sequences. Related to Problem 28.
Suggested references: [D. West, Introduction to Graph Theory, Prentice Hall; Section 1.4.25], [N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch. Proc. 49 (1946) 758-764].
- Problem 241: The Gessel-Viennot method. This is a remarkable formula to enumerate n-tuples of nonintersecting lattice paths. The answer is given by a determinant of binomial coecients, and the proof is based on the combinatorics of involutions.
Suggested references: [M. Aigner, A Course in Enumeration, Springer; Section 5.4], [R. Stanley, Enumerative Combinatorics Vol I; Section 2.7], [I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae,
Advances in Math. 58 (1985), 300-321].
- (Taken by Mike B., Henry and Nick) Problem 243: Domino tilings of Aztec diamonds. Counting the number of domino tilings of a given shape is a dicult problem in general. However, for the so-called Aztec diamond, the number of domino tilings has a very simple formula.
Suggested references: [M. Aigner, A Course in Enumeration, Springer; pages 44-50], [E. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoretical Computer Science 319 (2004), 29-57].
- The Robinson-Schensted-Knuth correspondence. This is one of the most important bijections in combinatorics.
- Bijections between 321-avoiding and 132-avoiding permutations. Related to problems 173 and 174.
- A problem of your choice from Stanley's list, rated [3] or [3-] (ask me first if it is suitable).
Last updated June 27, 2016 13:25:43 EDT