The Combinatorica Project

Sriram V. Pemmaraju
Department of Computer Science, The University of Iowa

Steven Skiena
Department of Computer Science, State University of New York at Stony Brook

Combinatorica is a package written in 1989 by Steve Skiena for doing computational discrete mathematics in Mathematica. It included over 230 functions and has been a Standard AddOn Mathematica package. Steve Skiena described this package in his book Implementing Discrete Mathematics: Combinatorics and Graph Theory in Mathematica, Advanced Book Division, Addison-Wesley, Redwood City CA, June 1990. Along with Steve Skiena I am developing a "new" Combinatorica package that is expected to be released in the first half of 2001. How computational discrete mathematics is done using the new package will be described in a forthcoming book:

Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica
Cambridge University Press, September 2002

Want the latest Combinatorica package? Download Version 2.0.0 from here and the list of known bugs in this version. (last update: March 5, 2003, size: 341KB)

I am using Combinatorica in the course "Computational Combinatorics" For lecture notes and other resources, visit its homepage here.

How is the new Combinatorica different?

The "new" Combinatorica is an almost complete rewrite of the old package. The rewrite was done primarily to:

Significantly speed up most of the functions: This has been achieved by changing underlying data structures and algorithms, using code compilation judiciously, taking advantage of packed arrays in Mathematica 4.0, and in general paying closer attention to the Mathematica model of computation. Here is an example of the kind of speedup obtained.
Treat several new topics: These include set partitions, Polya theory, tree enumeration, Catalan families, planar graphs and embeddings, and approximation algorithms for NP-hard problems. Here is an example of a few Polya theory related functions.
Significantly improve on the graphics: A user can now color vertices and edges, draw them in different styles, display edge and vertex weights and labels and in general produce high quality graph drawings. Here is an example of the kinds of graph drawings the "new" Combinatorica is capable of producing.
Provide a large database of combinatorial objects and interface Combinatorica with other discrete math packages:

Combinatorica resources

The files provided here are rather large, especially the postscript files. Ideally, you should download Mathematica notebooks, ignoring the postscript and pdf versions. Even those who don't have access to Mathematica can read these notebooks by downloading MathReader from Wolfram Research.

Here is a demo I presented to Wolfram Research providing an overview of the ways in which the New Combinatorica is an improvement over the old: Mathematica notebook, postscript, pdf. (Last updated: June 14, 2001.)
Here is the beginning of a Mathematica tutorial for Combinatorica users that I am constructing: Mathematica notebook, postscript, and pdf). (Last updated: June 14, 2001.)
Examples, examples, and more examples.
- How to draw graphs: Mathematica notebook, postscript, and pdf.
- Basic graph manipulation functions: Mathematica notebook, postscript, and pdf.
- Functions for generating classes of graphs: Mathematica notebook, postscript, and pdf.
- Graph Algorithms I: Mathematica notebook, postscript, and pdf.
- Graph Algorithms II: coming soon.
Note: These examples are slightly out of date and the few examples that don't work can be made to work by a slight modification in the syntax.