UTSA logo Applied Combinatorics
MAT 4331
Fall, 2005
Instructor: J. Iovino
 

Brief Description

Combinatorics is the backbone of finite mathematics and one of the most important tools for analytical problem-solving. Collegiate curriculum recommendations from the Mathematical Association of America have included combinatorial problem solving as an important component of training in the mathematical sciences since 1980.

The course is strongly recommended for computer science, electrical engineering, mathematics, and statistics majors. Combinatorics underlies the analysis of all computer systems, and it plays a fundamental role in probability, game theory, and discrete optimization.

We will follow Alan Tucker's book Applied Combinatorics (see detailed bibliographic information below). This is a very established textbook. It has a wealth of examples and applications, and for about two decades, it has been used by many mathematics, engineering, computer science, and statistics departments around the world. The author emphasizes general reasoning skills over formalism.

Prerequisites

Essential prerequisite: love for mathematics and analytic problem solving.

Formal prerequisite: at least one the following courses,

Foundations of Mathematics (MAT 2243)
Discrete Mathematical Structures (CS 3233)
Calculus II (MAT 1223),
or instructor consent.

Textbook

Alan Tucker, Applied Combinatorics, Fourth Edition, John Wiley & Sons, 2002.

(Check the Amazon.com customer reviews for this book; the average customer rating is 5/5).

Content

  • Part 1. General counting methods. Arrangements and selections, distributions, binomial identities.
  • Part 2. Genarating functions. Generating function models, coeffitients of generating functions, partitions, eponential generating functions.
  • Part 3. Recurrence relations. Recurrence relation models, divide-and-conquer relations, solutions of linear recurrence relations, solution with generating functions.

    • Evaluation

    There will be four problem sets. The students will have two weeks to work on each set. Each problem set will be worth 25% of the grade.

    Material Covered

    8/25: Section 5.1.
    8/30: Section 5.2.
    9/1: Section 5.3.
    9/6: Section 5.4.
    9/8: Section 5.5.
    9/13: Section 6.1.
    9/15: Finished Section 6.1 ans started Section 6.2.
    9/20: Finished Section 6.2.
    9/22: Discussion of Homework 1.
    9/27: Section 6.4.
    9/29: Finished Section 6.4. Started Section 6.5.
    10/4: Section 6.5.
    10/6: Started Section 7.1.
    10/11: Finished Section 7.1.
    10/13: Started Section 7.3.
    10/18: Finished Section 7.3.
    10/25: Section 7.4.
    10/27: Started Section 7.5.
    11/1: Section 7.5.
    11/3: Section 7.5.
    11/8: Section 7.5.
    11/10: Section 8.1.
    11/17: Started Section 8.2.
    11/22: Section 8.2.
    11/29: Finished Section 8.2.
    12/1: Conclusion.

    Homework Assignments

    Homework 1 (Due 9/15)
    Section 5.2: 3,5; Section 5.4: 16, 36, 52; Section 5.5: 22, 32.
    Homework 2 (Due 10/18)
    Section 6.2: 20, 30; Section 6.4: 4, 10, 14; Section 6.5: 2(c), 2(e).
    Homework 3 (Due 12/1)
    Section 7.3: 2; Section 7.4: 2, 4, 8, 12; Section 7.5: 4(a), 8, 14.
    Homework 4 (Due 12/13)
    Section 8.2: 8, 10(a), 10(b), 16, 18.

    How to contact the instructor

    Office: SB 4.01.34

    Telephone: (210) 458-5531

    Email: iovino at math.utsa.edu

    Office hours: Tu, Th, 3-4 pm, or by appointment.

    Valid HTML 4.0!