Counting methods for arrangements and selections, generating functions, recurrence relations, inclusion-exclusion principle, elementary graph theory, trees and searching, network algorithms. Prerequisite: MATH 112.  (Offered even years, fall semester.)

Alan Tucker, Applied Combinatorics, 4^th edition, John Wiley & Sons Inc., 2001.

P. Christopher Staecker, Ph.D., Assistant Professor of Mathematics

Math and computer science majors.

1. To develop problem solving skills.
2. To emphasize the design of solution methods.
3. To learn elementary counting techniques in forms of combinations and permutations
4. To develop the ability to see the mathematics in the structure of the problem.
5. To write clear and concise descriptions of problems and their solutions.
6. To use when appropriate, the concept of generating functions and the corresponding identities.
7. To employ elementary graph theory in solving network and scheduling problems.
8. To analyze simple games and implement strategies for winning.
9. To use the inclusion-exclusion principle in analyzing counting problems.
10. To develop the ability to discern which problem solving technique is appropriate for the given problem.

Introductory graph theory, Euler circuits, Hamiltonian paths, graph coloring, planarity, graph isomorphism, shortest paths, networks, and applications of graphs. The combinatorics topics include generating polynomials, exponential generating functions, solving diophantine equations, the inclusion-exclusion principle, derangements, mathematical induction, recursion and elementary counting problems including partitions of integers, the analysis of elementary games and puzzles using graph analysis will also be a topic of discussion. Comparison of several sorting algorithms will be discussed.

1. Mathematics of Choice, "How to Count without Counting", by Ivan Niven.
2. Applied Combinatorics with Problem Solving by Jackson/Thoro.
3. An introduction to Discrete Mathematics by Roman.
4. Introduction to Finite Mathematics by Kemeny, Snell, Thompson.
5. Recent issues of College Mathematics Journal (MAA).
6. Recent issues of Math Teacher (N.C.T.M.).
7. Recent issues of the Math Monthly (MAA).