Combinatorica
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.
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.
These permutations are generated in minimum change order, where successive permutations differ by exactly one transposition. The built-in generator Permutations constructs permutations in lexicographic order.
| Out[2]= |  |
|
The ranking function illustrates that the built-in function Permutations uses lexicographic sequencing.
| Out[3]= |  |
|
With 3!=6 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.
| Out[4]= |  |
|
A fixed point of a permutation p is an element in the same position in p as in the inverse of p. Thus, the only fixed point in this permutation is 7.
| Out[5]= |  |
|
The identity permutation consists of n singleton cycles or fixed points.
| Out[6]= |  |
|
The classic problem in Polya theory is counting how many different ways necklaces can be made out of k beads, when there are m 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 k 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.
| Out[7]= |  |
|
The number of inversions in a permutation is equal to that of its inverse.
| Out[8]= |  |
|
Generating subsets incrementally is efficient when the goal is to find the first subset with a given property, since every subset need not be constructed.
| Out[9]= |  |
|
In a Gray code, each subset differs in exactly one element from its neighbors. Observe that the last eight subsets all contain 1, while none of the first eight do.
| Out[10]= |  |
|
A k-subset is a subset with exactly k elements in it. Since the lead element is placed in first, the k-subsets are given in lexicographic order.
| Out[11]= |  |
|
Combinatorica functions for permutations.
Combinatorica functions for subsets.
Combinatorica functions for group theory.
Partitions, Compositions, and Young Tableaux
A partition of a positive integer
n is a set of
k strictly positive integers whose sum is
n. A composition of
n is a particular arrangement of nonnegative integers whose sum is
n. A set partition of
n elements is a grouping of all the elements into nonempty, nonintersecting subsets. A Young tableau is a structure of integers
1, ..., n where the number of elements in each row is defined by an integer partition of
n. 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.
Here are the eleven partitions of 6. Observe that they are given in reverse lexicographic order.
| Out[12]= |  |
|
Although the number of partitions grows exponentially, it does so more slowly than permutations or subsets, so complete tables can be generated for larger values of n.
| Out[13]= |  |
|
Ferrers diagrams represent partitions as patterns of dots. They provide a useful tool for visualizing partitions, because moving the dots around provides a mechanism for proving bijections between classes of partitions. This constructs a random partition of 100.
| Out[14]= |  |
|
Here every composition of 5 into 3 parts is generated exactly once.
| Out[15]= |  |
|
Set partitions are different than integer partitions, representing the ways you can partition distinct elements into subsets. They are useful for representing colorings and clusterings.
| Out[16]= |  |
|
The list of tableaux of shape {2, 2, 1} illustrates the amount of freedom available to tableaux 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.
| Out[17]= |  |
|
By iterating through the different integer partitions as shapes, all tableaux of a particular size can be constructed.
| Out[18]= |  |
|
The hook length formula can be used to count the number of tableaux for any shape. Using the hook length formula over all partitions of n computes the number of tableaux on n elements.
| Out[19]= |  |
|
Each of the 117,123,756,750 tableaux of this shape will be selected with equal likelihood.
Out[20]//TableForm= |
| |  |
|
A pigeonhole result states that any sequence of n2+1 distinct integers must contain either an increasing or a decreasing scattered subsequence of length n+1.
| Out[21]= |  |
|
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.
In the complete graph on five vertices, denoted K5, each vertex is adjacent to all other vertices. CompleteGraph[n] constructs the complete graph on n vertices.
| Out[22]= |  |
|
The internals of the graph representation are not shown to the user—only a notation with the number of edges and vertices, followed by whether the graph is directed or undirected.
| Out[23]= |  |
|
The adjacency matrix of K5 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.
Out[24]//TableForm= |
| |  |
|
The standard embedding of K5 consists of five vertices equally spaced on a circle.
| Out[25]= |  |
|
The number of vertices in a graph is termed the order of the graph.
| Out[26]= |  |
|
M returns the number of edges in a graph.
| Out[27]= |  |
|
Edge/vertex colors/styles can be globally modified, giving complete flexibility to change the appearance of a graph.
| Out[28]= |  |
|
The colors, styles, labels, and weights of individual vertices and edges can also be changed individually, perhaps to highlight interesting features of the graph.
| Out[29]= |  |
|
A star is a tree with one vertex of degree n-1. Adding any new edge to a star produces a cycle of length 3.
| Out[30]= |  |
|
Graphs with multi-edges and self-loops are supported. Here there are two copies of each edge of a star.
| Out[31]= |  |
|
The adjacency list representation of a graph consists of n lists, one list for each vertex vi, 1≤i≤n, which records the vertices to which vi is adjacent. Each vertex in the complete graph is adjacent to all other vertices.
Out[32]//TableForm= |
| |  |
|
There are n (n-1) ordered pairs of edges defined by a complete graph of order n.
| Out[33]= |  |
|
An induced subgraph of a graph G is a subset of the vertices of G 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.
| Out[34]= |  |
|
The vertices of a bipartite graph have the property that they can be partitioned into two sets such that no edge connects two vertices of the same set. Contracting an edge in a bipartite graph can ruin its bipartiteness. Note the self-loop created by the contraction.
| Out[35]= |  |
|
A breadth-first search of a graph explores all the vertices adjacent to the current vertex before moving on. A breadth-first traversal of a simple cycle alternates sides as it wraps around the cycle.
| Out[36]= |  |
|
In a depth-first search, the children of the first son of a vertex are explored before visiting his brothers. The depth-first traversal differs from the breadth-first traversal above in that it proceeds directly around the cycle.
| Out[37]= |  |
|
Different drawings or embeddings of a graph can reveal different aspects of its structure. The default embedding for a grid graph is a ranked embedding from all the vertices on one side. Ranking from the center vertex yields a different but interesting drawing.
| Out[38]= |  |
|
The radial embedding of a tree is guaranteed to be planar, but radial embeddings can be used with any graph. Here is a radial embedding of a random labeled tree.
| Out[39]= |  |
|
By arbitrarily selecting a root, any tree can be represented as a rooted tree.
| Out[40]= |  |
|
An interesting general heuristic for drawing graphs models the graph as a system of springs and lets Hooke's law space the vertices. Here it does a good job illustrating the join operation, where each vertex of K7 is connected to each of two disconnected vertices. In achieving the minimum energy configuration, these two vertices end up on different sides of K7.
| Out[41]= |  |
|
Combinatorica functions for modifying graphs.
Combinatorica functions for graph format translation.
Combinatorica options for graph functions.
