Combinatorica
Combinatorica extends the Wolfram Language 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.
You are encouraged to visit the 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. Combinatorica provides functions for constructing objects both randomly and deterministically, to rank and unrank them, and to compute invariants on them. Here are examples of some of these functions in action.
distinct permutations of three elements, within 20 random permutations you are likely to see all of them. Observe that it is unlikely for the first six permutations to all be distinct. 
is an element in the same position in 
as in the inverse of 
. Thus, the only fixed point in this permutation is 7. 
beads, when there are 
different types or colors of beads to choose from. When two necklaces are considered the same if they can be obtained only by shifting the beads (as opposed to turning the necklace over), the symmetries are defined by 
permutations, each of which is a cyclic shift of the identity permutation. When a variable is specified for the number of colors, a polynomial results. 
‐subset is a subset with exactly 
elements in it. Since the lead element is placed in first, the 
‐subsets are given in lexicographic order. 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 non-negative 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.
. 
illustrates the amount of freedom available to tableau structures. The smallest element is always in the upper left‐hand corner, but the largest element is free to be the rightmost position of the last row defined by the distinct parts of the partition. 
computes the number of tableaux on 
elements. 
distinct integers must contain either an increasing or a decreasing scattered subsequence of length 
. | Compositions | DominatingIntegerPartitionQ |
| DominationLattice | DurfeeSquare |
| FerrersDiagram | NextComposition |
| NextPartition | PartitionQ |
| RandomComposition | RandomPartition |
| TransposePartition |
Combinatorica functions for integer partitions.
Combinatorica functions for set partitions.
Combinatorica functions for Young tableaux.
Combinatorica functions for counting.
Representing Graphs
A graph is defined as 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.
, each vertex is adjacent to all other vertices. CompleteGraph[n] constructs the complete graph on 
vertices. 
shows that each vertex is adjacent to all other vertices. The main diagonal consists of zeros, since there are no self‐loops in the complete graph, meaning edges from a vertex to itself. 
. Adding any new edge to a star produces a cycle of length 3. 
lists: one list for each vertex 
, 
, which records the vertices to which 
is adjacent. Each vertex in the complete graph is adjacent to all other vertices. 
is a subset of the vertices of 
together with any edges whose endpoints are both in this subset. An induced subgraph that is complete is called a clique. Any subset of the vertices in a complete graph defines a clique. 
is connected to each of two disconnected vertices. In achieving the minimum energy configuration, these two vertices end up on different sides of 
. Combinatorica functions for modifying graphs.
| Edges | FromAdjacencyLists |
| FromAdjacencyMatrix | FromOrderedPairs |
| FromUnorderedPairs | IncidenceMatrix |
| ToAdjacencyLists | ToAdjacencyMatrix |
| ToOrderedPairs | ToUnorderedPairs |
Combinatorica functions for graph format translation.
Combinatorica options for graph functions.
| GetEdgeLabels | GetEdgeWeights |
| GetVertexLabels | GetVertexWeights |
| SetEdgeLabels | SetEdgeWeights |
| SetGraphOptions | SetVertexLabels |
| SetVertexWeights |
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.
of a graph 
has a vertex of 
associated with each edge of 
, and an edge of 
if and only if the two edges of 
share a common vertex. 
times, and include complete graphs and cycles as special cases. Even random circulant graphs have an interesting, regular structure. 
are the graph product of cubes of dimension 
and the complete graph 
. Here, a Hamiltonian cycle of the hypercube is highlighted. Colored highlighting and graph animations are also provided in the package. 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 is a demonstration of how to compute several different graph invariants.
is an assignment of exactly one direction to each of the edges of 
. Note that arrows denoting the direction of each edge are automatically drawn in displaying directed graphs. 
is a vertex whose deletion disconnects 
. Any graph with no articulation vertices is said to be biconnected. A graph with a vertex of degree 1 cannot be biconnected, since deleting the other vertex that defines its only edge disconnects the graph. 
connected components. Deleting a leaf leaves a connected tree. 
‐connected if there does not exist a set of 
vertices whose removal disconnects the graph. The wheel is the basic triconnected graph. 
‐edge‐connected if there does not exist a set of 
edges whose removal disconnects the graph. The edge connectivity of a graph is at most the minimum degree 
, since deleting those edges disconnects the graph. Complete bipartite graphs realize this bound. Combinatorica functions for graph predicates.
is a cycle that visits every vertex in 
exactly once, as opposed to an Eulerian cycle that visits each edge exactly once. 
for 
are the only Hamiltonian complete bipartite graphs. 
cannot divide 
if 
. Finally, it is transitive, as 
implies 
for some integer 
, so 
implies 
.
is transitive if any three vertices 
, 
, 
, such that edges 
, imply 
. The transitive reduction of a graph 
is the smallest graph 
such that 
. The transitive reduction eliminates all implied edges in the divisibility relation, such as 
, 
, 
, and 
. 
of the vertices of a graph such that an edge 
implies that 
appears before 
in 
. A complete directed acyclic graph defines a total order, so there is only one possible output from TopologicalSort. 
can be colored in a certain number of ways with exactly 
colors 
. This number is determined by the chromatic polynomial of the graph. 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.
and 
is 
. 
edges of minimum total weight that form a spanning tree of the graph. Any spanning tree is a minimum spanning tree when the graphs are unweighted. 
, is a set of edges of 
such that no two of them share a vertex in common. A perfect matching of an even cycle consists of alternating edges in the cycle. 
Combinatorica functions for graph algorithms.