Skip to main content
main-content

Über dieses Buch

The notes that eventually became this book were written between 1977 and 1985 for the course called Constructive Combinatorics at the University of Minnesota. This is a one-quarter (10 week) course for upper level undergraduate students. The class usually consists of mathematics and computer science majors, with an occasional engineering student. Several graduate students in computer science also attend. At Minnesota, Constructive Combinatorics is the third quarter of a three quarter sequence. The fIrst quarter, Enumerative Combinatorics, is at the level of the texts by Bogart [Bo], Brualdi [Br], Liu [Li] or Tucker [Tu] and is a prerequisite for this course. The second quarter, Graph Theory and Optimization, is not a prerequisite. We assume that the students are familiar with the techniques of enumeration: basic counting principles, generating functions and inclusion/exclusion. This course evolved from a course on combinatorial algorithms. That course contained a mixture of graph algorithms, optimization and listing algorithms. The computer assignments generally consisted of testing algorithms on examples. While we felt that such material was useful and not without mathematical content, we did not think that the course had a coherent mathematical focus. Furthermore, much of it was being taught, or could have been taught, elsewhere. Graph algorithms and optimization, for instance, were inserted into the graph theory course where they naturally belonged. The computer science department already taught some of the material: the simpler algorithms in a discrete mathematics course; effIciency of algorithms in a more advanced course.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Listing Basic Combinatorial Objects

Abstract
At a basic level, one would expect that constructive combinatorics would address the question of how one constructs the fundamental objects in combinatorics. In fact, “constructing” these objects could mean providing an algorithm for listing all of them, or it could mean generating one of them at random. While both questions are of interest, we shall concentrate on the first.
Dennis Stanton, Dennis White

Chapter 2. Partially Ordered Sets

Abstract
Partially ordered sets, or posets, appear in many branches of mathematics, but they are fundamental in combinatorics. For example, many of the important enumeration techniques (generating functions, inclusion-exclusion) have their theoretical foundation in some underlying poset.
Dennis Stanton, Dennis White

Chapter 3. Bijections

Abstract
We have already encountered several examples of explicit bijections (φ: A → B, for two finite sets A and B. In Chapter 1 we let A be the set of all permutations π of [n] and B be the set {0, 1,…, n! − 1}. The rank function was an explicit bijection from A to B. It was closely related to the listing algorithm for permutations.
Dennis Stanton, Dennis White

Chapter 4. Involutions

Abstract
Many combinatorial formulas include positive and negative values. It might first seem that a bijection is not the proper tool for dealing with these formulas. This is not the case, however. Such formulas can sometimes be proved by using an involution on a signed set. In fact, involutions may be used to prove theorems seemingly unrelated to combinatorics. This will be done in Section 3 for the Cayley-Hamilton Theorem.
Dennis Stanton, Dennis White

Backmatter

Weitere Informationen