Contents
Catalog Links
Share

MA4026 Combinatorial Mathematics

Advanced techniques in enumerative combinatorics and an introduction to combinatorial structures. Topics include generating functions, recurrence relations, elements of Ramsey theory, theorems of Burnside and Polya, and balanced incomplete block designs. Application areas with DoD/DoN relevance range from mathematics to computer science and operations research, including applications in probability, game theory, network design, coding theory, and experimental design.

Prerequisite

MA3025

Lecture Hours

4

Lab Hours

0

Course Learning Outcomes

After successfully completing this course, the student will be able to:

  • Describe the four basic counting principles. Analyze problems and correctly apply these principles when solving counting problems.
  • Understand the pigeonhole principle, both in simple and strong form.Recognize when it can be applied, and correctly set up and solve counting problems using the principle.
  • Define permutations and combinations of sets and multisets, and demonstrate mastery of their use when solving combinatorial problems.
  • Explain Pascal’s formula, as well as the binomial and multinomial theorems, and be able to manipulate expressions and derive mathematical identities.
  • State the inclusion-exclusion principle.Recognize when its use is necessary, and correctly apply the principle to counting problems.
  • Show proficiency in solving problems involving combinations with repetitions, derangements, and permutations with forbidden positions.
  • Be able to solve linear homogeneous and non-homogeneous recurrence relations.
  • Describe the method of generating functions. Demonstrate proficiency in the manipulation and use of ordinary and exponential generating functions in solving combinatorial problems.
  • Be familiar with Catalan numbers, difference sequences, Stirling numbers, and partition numbers.
  • Describe and demonstrate proficiency with solving Matching, Systems of Distinct Representatives, and Stable Marriage problems.
  • Explain and be able to solve basic block-design and Steiner tripe Systems.