MATH 3610 Combinatorics II
Course Description
This course deals with concrete problems by considering finite collections of discrete objects as opposed to continuous mathematics. Students taking this course will be expected to have a solid foundation in algebra (either abstract or linear), and for this reason either MATH 2272 or MATH 2273 are listed as a course prerequisite.
The main focus is neither on the use of standard algebraic manipulations nor on any given systematic problem solving framework. We begin with a study of combinations and permutations of objects which are incorporated in the binomial and associated multinomial theorem. The cases of redundant permutations and combinations are examined. Bell numbers and Catalan numbers are analyzed by recurrence relations. We illustrate how calculus techniques are applied to the binomial theorem leading to the formation of combinatorial identities. Generating functions are introduced to count number of permutations and combinations which involves different types of indicator functions. In so doing, we define Stirling numbers of the first and second kind, and provide connections with number of permutations of distinct objects. Ordinary generating functions are developed, leading to various problems on partitions of integers. The concept of a Ferrers graph is used to illustrate partitions, and results are deduced on numbers of partitions by looking at conjugacy. The study of ordered partitions or compositions is closely compared to that of partitions. Particular emphasis is given to recurrence relations and an entire section is devoted to the solving of both one index and two indices recurrence relations, which are subsequently solved by means of generating functions or by repeated iteration techniques. The principle of inclusion and exclusion is a very potent tool in mathematics and we apply this principle to a variety of problems on arrangements with restrictions. In so doing the rook polynomial of an associated chessboard is introduced as a generating function.
