This is documentation for Mathematica 5.2, which was
based on an earlier version of the Wolfram Language.

## DiscreteMath`Combinatorica`

DiscreteMath`Combinatorica` extends Mathematica by over 450 functions in combinatorics and graph theory. It includes functions for constructing graphs and other combinatorial objects, computing invariants of these objects, and finally displaying them. This documentation covers only a subset of these functions. The best guide to this package is the book Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, by Steven Skiena and Sriram Pemmaraju, published by Cambridge University Press, 2003. The new Combinatorica is a substantial rewrite of the original 1990 version. It is now much faster than before, and provides improved graphics and significant additional functionality.

We encourage you to visit our website, www.combinatorica.com, where you will find the latest release of the package, an editor for Combinatorica graphs, and additional files of interest.

### Permutations and Combinations

Permutations and subsets are the most basic combinatorial objects. DiscreteMath`Combinatorica` provides functions for constructing objects both randomly and deterministically, to rank and unrank them, and to compute invariants on them. Here we provide examples of some of these functions in action.

Combinatorica functions for permutations.

Combinatorica functions for subsets.

Combinatorica functions for group theory.

### Partitions, Compositions, and Young Tableaux

A partition of a positive integer is a set of strictly positive integers whose sum is . A composition of is a particular arrangement of nonnegative integers whose sum is . A set partition of elements is a grouping of all the elements into nonempty, nonintersecting subsets. A Young tableau is a structure of integers where the number of elements in each row is defined by an integer partition of . Further, the elements of each row and column are in increasing order, and the rows are left justified. These four related combinatorial objects have a host of interesting applications and properties.

 Out[20]//TableForm=

Combinatorica functions for integer partitions.

Combinatorica functions for set partitions.

Combinatorica functions for Young tableaux.

Combinatorica functions for counting.

### Representing Graphs

We define a graph to be a set of vertices with a set of edges, where an edge is defined as a pair of vertices. The representation of graphs takes on different requirements depending upon whether the intended consumer is a person or a machine. Computers digest graphs best as data structures such as adjacency matrices or lists. People prefer a visualization of the structure as a collection of points connected by lines, which implies adding geometric information to the graph.

 Out[24]//TableForm=

 Out[32]//TableForm=

Combinatorica functions for modifying graphs.

Combinatorica functions for graph format translation.

Combinatorica options for graph functions.

Combinatorica functions for graph labels and weights.

Combinatorica functions for drawing graphs.

### Generating Graphs

Many graphs consistently prove interesting, in the sense that they are models of important binary relations or have unique graph theoretic properties. Often, these graphs can be parameterized, such as the complete graph on vertices , giving a concise notation for expressing an infinite class of graphs. Start off with several operations that act on graphs to give different graphs and which, together with parameterized graphs, give the means to construct essentially any interesting graph.

Combinatorica functions for graph constructors.

### Properties of Graphs

Graph theory is the study of properties or invariants of graphs. Among the properties of interest are such things as connectivity, cycle structure, and chromatic number. Here we demonstrate how to compute several different graph invariants.

Combinatorica functions for graph predicates.

Combinatorica functions for graph invariants.

### Algorithmic Graph Theory

Finally, there are several invariants of graphs that are of particular interest because of the algorithms that compute them.

Combinatorica functions for graph algorithms.