Syllabus for 22C:196, Computational Combinatorics
Professor Sriram Pemmaraju
Class Room and Timing 105 MLH, 2:30-3:45 pm, TTh
Office and Office Hours 101G MLH, 3:45-4:45 pm, MT
E-mail and phone sriram@cs.uiowa.edu, 319-353-2596
Course page http://www.cs.uiowa.edu/~sriram/196/fall01/index.html
Grading 6 homeworks at 10% each, 1 exam at 20%, and 1 project at 20%
Prerequisites Grades C- or above in 22C:34 and 22C:44

Introduction

Combinatorics is the study of counting. Traditional Combinatorics involves deriving formulae for counting arrangements of one sort or another. Since the 70's, Combinatorics has expanded to include the notion of enumeration as well. We not only want to count, but we want to be able to list the objects being counted, as well. Combinatorial numbers are typically huge and so it is crucial that our procedures for enumeration be efficient. This is where algorithmic techniques from computer science become relevant.

Two questions are central to this course (a) how do we efficiently generate all members of some class of combinatorial objects? (b) how do we efficiently select an object uniformly at random from a class of combinatorial objects? For example, how do we efficiently generate all unlabeled binary trees or select an unlabeled binary tree uniformly at random? There are many applications of combinatorial generation, for example, to circuit testing, to theorem proving, to solving popular puzzles, and to statistical computation. There is a great beauty to the subject and many interesting and accessible problems remain open - these will be presented throughout the course.

Tools from discrete mathematics such as generating functions, elementary theory of finite groups, and Polya theory will be developed along with tools from algorithms such as backtracking, branch-and-bound, and dynamic programming. Using these tools we will study the enumeration and selection of combinatorial objects such as permutations, combinations, set partitions, integer partitions, free trees, binary trees, spanning trees, graph colorings etc.

Combinatorica

To understand concepts, test conjectures, and generally play around with, we will use the Mathematica based software package called Combinatorica. This package contains over 400 built-in functions to count, enumerate, and select combinatorial objects. Since the package is Mathematica based, we get the considerable power of Mathematica for free. Students will also be expected to develop some amount of competence in Mathematica programming and will use this to code algorithms not already in Combinatorica. To learn more about Combinatorica go here and to learn more about Mathematica go here.

List of Topics

```Permutations
Lexicographic Permutations
Generation
Ranking and Unranking
Random Permutation
Mininum Change Permutations
Johnson-Trotter Algorithm
Ranking and Unranking

Cycle Structure of Permutations
To and From Cycles
Stirling Numbers of the First Kind
Generating Permutations with k-cycles
Hiding and Revealing Cycles
Random Permutation with k-cycles

Subsets
Lexicographic Subsets
Generation
Ranking and Unranking
Gray Codes
Hamiltonian Cycles in Graphs
k-subsets
Lexicographic k-subsets
Generation
Ranking and Unranking
Gray Code k-subsets

Integer Partitions
Reverse Lexicographic Ordered
Generation
Ranking and Unranking
Random Partitions
Counting Integer Partitions
Gray Code Integer Partitions
Introduction to Generating Functions
Examples: Fibonacci Numbers, Coin Changing
Applications of Generating Functions to Integer Partitions

Set Partitions
Generating Set Partitions
Stirling Numbers of the Second Kind and Bell Numbers
Ranking, Unranking, and Random Set Partitions
Restricted Growth Functions
Bijection between Set Partitions and Restricted Growth Functions
Generating, Ranking, and Unranking Restricted Growth Functions

Young Tableaux
Young Tableaux and Involutions
Insertion into and Deletion from a Tableaux
Robinson-Schensted-Knuth Correspondence
The Hook Formula
Generating Young Tableaux
Counting Tableaux by Shape
Generating Random Tableaux

Trees
Cayley's Theorem
Prufer's Correspondence and Labeled Trees
Generating Unlabeled Rooted Trees
Generating Unlabeled Free Trees
Random Unlabeled Trees
Counting Spanning Trees of Graphs: Matrix Tree Theorem

Groups and Symmetry
Elementary Theory of Permutation Groups
Automorphism Groups of Graphs
Vertex Transitive Graphs: Lovasz's Hamiltonian Cycle Conjecture
Symmetries of other combinatorial objects: necklaces, polyhedra
Simple Approaches to the Graph Isomorphism Problem
Computing Certificates
Tree Isomorphism
Graph Isomorphism

Polya Theory
Cycle Index of Permutation Groups
Burnside's Lemma
Polya's Theorem: Proof
Polya's Theorem: Applications
Generating Random Graphs using Polya Theory
```

Books

Here is a list of books I have often referred to in learning this material. Most of the books are in the library and I own a copy of all of these books, except for the one by Nijenhuis and Wilf. I'll provide typed notes for the course as we go along. My hope is that these will be sufficient and you will not to read far beyond what I provide. If you do want additional reading material get a copy of East Side, West Side,..., the lecture notes provided by Herbert Wilf. If you do want to spend money on a book and want my recommendation from among the list below, Combinatorial Algorithms : An Update by Herbert Wilf would be my choice.

```East Side, West Side...
Herbert S. Wilf, 1999

Introduction to Graph Theory
Douglas B. West
Prentice-Hall, 1996

Combinatorial Algorithms: Generation, Enumeration, and Search
Donald L. Kreher and Douglas R. Stinson
CRC Press, 1999

Concrete Mathematics : A Foundation for Computer Science
Ronald Graham, Oren Patashnik, Donald E. Knuth

The Art of Computer Programming : Fundamental Algorithms
(Art of Computer Programming, Vol 1, 2nd Ed)
Donald E. Knuth

The Art of Computer Programming : Sorting and Searching
(Art of Computer Programming, Vol 3, 2nd Ed)
Donald E. Knuth

Constructive Combinatorics
Dennis Stanton and Dennis White
Springer-Verlag, 1986

Combinatorial Algorithms,
Albert Nijenhuis and Herbert S. Wilf