CS 449-3
Introduction to Combinatorics
Catalog Description
((Same as Mathematics 449.) An introduction to combinatorial mathematics with computing applications. Topics include selections and arrangements, generating functions, recursion, inclusion and exclusion, coding theory, block designs.
Prerequisite:
Mathematics 349 or consent of instructor.
Objectives
To familiarize the students with the basic concepts and techniques of Combinatorics, such as counting functions, pigeonhole principle, inclusion-exclusion, partitions, generating functions, and combinatorial designs.
Course Outline
| Lectures | ||
| 1. | Basic Tools of Combinatorics
Product and Sum Rule, Selections and Arrangements, Basic Ideas of Graph Theory |
6 |
| 2. | Combinatorial Techniques
Inclusion and Exclusion, Binomial Theorem, Multinomial Coefficients, Pigeonhole Principle, Permutations-transpositions, parity, unique cycle decomposition. |
6 |
| 3. | Generating Functions and Recurrences
Power Series, Ordinary and Exponential Generating Functions, Probability Generating Functions. |
6 |
| 4. | Polya's Theorem | 6 |
| 5. | Coding Theory
Codes and Linear Codes, Shannon's Theorem, Error Correction and Detection, Application of the pigeonhole principle. |
8 |
| 6. | Block Designs
Balanced Incomplete Block Designs, Hadamard Matrices, Latin Squares. |
6 |
| Total | 40 | |