Prerequisites & Bulletin Description
Course Objectives
In the course, students will become familiar with fundamental combinatorial structures that naturally appear in various other fields of mathematics and computer science. They will learn how to use these structures to represent mathematical and applied questions, and they will become comfortable with the combinatorial tools commonly used to analyze such structures. Given a hypothetical combinatorial object that must satisfy certain properties, students will learn how to prove the existence or non-existence of the object, compute the number of such objects and understand their underlying structure. Three of the four learning outcomes of the BA in Mathematics will be addressed:
- Students will be able to utilize mathematics and computer applications to solve practical problems in mathematics. This course will give students the combinatorial tools to model and analyze practical problems in various areas.
- Students will be able to identify, formulate and solve problems in mathematics, including proof writing. The course will teach students how to understand and deal with enumerative problems. They will put to practice problem solving techniques that they know and learn new ones, such as non-constructive existence proofs and the probabilistic method.
- Students will be able to present technical information clearly in both oral and written formats. The evaluation will be based on students writing proofs in correct mathematical english. Oral communication will not be addressed.
Evaluation of Students
Students will be evaluated on their ability to create, organize and clearly present rigorous solutions to combinatorial problems. Instructors may design their own methods of evaluating student performance, but these will include in-class examinations, graded homework and a final exam. A possible distribution is the following: 2 midterms (40%), weekly homework (30%), final (30%).
Course Outline
The pigeonhole principle. Counting techniques. Fundamental combinatorial objects (sets, permutations, combinations, partitions). The sieve. Generating functions. Graphs. Partially ordered sets. Möbius inversion formula. Ramsey theory. The probabilistic method.
Textbooks & Software
M. Bona, A walk through combinatorics, World Scientific Publishing Company, 2002. R. Brualdi, Introductory Combinatorics, Prentice Hall, 2004.