Combinatorica
As of Version 10, most of the functionality of the Combinatorica package is built into the Wolfram System. »
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.
In[1]:=1
✖
https://wolfram.com/xid/0im2i3q5y30-s5m
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.
In[2]:=2
✖
https://wolfram.com/xid/0im2i3q5y30-jbx
Out[2]=2
The ranking function illustrates that the built‐in function Permutations uses lexicographic sequencing.
In[3]:=3
✖
https://wolfram.com/xid/0im2i3q5y30-vgn
Out[3]=3
With 
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.
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. In[4]:=4
✖
https://wolfram.com/xid/0im2i3q5y30-b93
Out[4]=4
A fixed point of a permutation 
is an element in the same position in 
as in the inverse of 
. Thus, the only fixed point in this permutation is 7.
is an element in the same position in as in the inverse of . Thus, the only fixed point in this permutation is 7. In[5]:=5
✖
https://wolfram.com/xid/0im2i3q5y30-elh
Out[5]=5
In[6]:=6
✖
https://wolfram.com/xid/0im2i3q5y30-sok
Out[6]=6
The classic problem in Polya theory is counting how many different ways necklaces can be made out of 
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.
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. In[7]:=7
✖
https://wolfram.com/xid/0im2i3q5y30-mdw
Out[7]=7
In[8]:=8
✖
https://wolfram.com/xid/0im2i3q5y30-ngn
Out[8]=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.
In[9]:=9
✖
https://wolfram.com/xid/0im2i3q5y30-wpu
Out[9]=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.
In[10]:=10
✖
https://wolfram.com/xid/0im2i3q5y30-zg8
Out[10]=10
A 
‐subset is a subset with exactly 
elements in it. Since the lead element is placed in first, the 
‐subsets are given in lexicographic order.
‐subset is a subset with exactly elements in it. Since the lead element is placed in first, the ‐subsets are given in lexicographic order. In[11]:=11
✖
https://wolfram.com/xid/0im2i3q5y30-kp3
Out[11]=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 
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.
In[12]:=12
✖
https://wolfram.com/xid/0im2i3q5y30-vba
Out[12]=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 
.
. In[13]:=13
✖
https://wolfram.com/xid/0im2i3q5y30-ni2
Out[13]=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.
In[14]:=14
✖
https://wolfram.com/xid/0im2i3q5y30-vcx
Out[14]=14
In[15]:=15
✖
https://wolfram.com/xid/0im2i3q5y30-l0p
Out[15]=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.
In[16]:=16
✖
https://wolfram.com/xid/0im2i3q5y30-nim
Out[16]=16
The list of tableaux of shape 
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.
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. In[17]:=17
✖
https://wolfram.com/xid/0im2i3q5y30-w5v
Out[17]=17
By iterating through the different integer partitions as shapes, all tableaux of a particular size can be constructed.
In[18]:=18
✖
https://wolfram.com/xid/0im2i3q5y30-sol
Out[18]=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 
computes the number of tableaux on 
elements.
computes the number of tableaux on elements. In[19]:=19
✖
https://wolfram.com/xid/0im2i3q5y30-ful
Out[19]=19
In[20]:=20
✖
https://wolfram.com/xid/0im2i3q5y30-j4f
A pigeonhole result states that any sequence of 
distinct integers must contain either an increasing or a decreasing scattered subsequence of length 
.
distinct integers must contain either an increasing or a decreasing scattered subsequence of length . In[21]:=21
✖
https://wolfram.com/xid/0im2i3q5y30-vdl
Out[21]=21
| 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.
In the complete graph on five vertices, denoted 
, each vertex is adjacent to all other vertices. CompleteGraph[n] constructs the complete graph on 
vertices.
, each vertex is adjacent to all other vertices. CompleteGraph[n] constructs the complete graph on vertices. In[22]:=22
✖
https://wolfram.com/xid/0im2i3q5y30-xtk
Out[22]=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.
In[23]:=23
✖
https://wolfram.com/xid/0im2i3q5y30-wh7
Out[23]=23
The adjacency matrix of 
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.
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. In[24]:=24
✖
https://wolfram.com/xid/0im2i3q5y30-wkf
In[25]:=25
✖
https://wolfram.com/xid/0im2i3q5y30-s5q
Out[25]=25
In[26]:=26
✖
https://wolfram.com/xid/0im2i3q5y30-i07
Out[26]=26
In[27]:=27
✖
https://wolfram.com/xid/0im2i3q5y30-do7
Out[27]=27
Edge/vertex colors/styles can be globally modified, giving complete flexibility to change the appearance of a graph.
In[28]:=28
✖
https://wolfram.com/xid/0im2i3q5y30-o9y
Out[28]=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.
In[29]:=29
✖
https://wolfram.com/xid/0im2i3q5y30-ulz
Out[29]=29
A star is a tree with one vertex of degree 
. Adding any new edge to a star produces a cycle of length 3.
. Adding any new edge to a star produces a cycle of length 3. In[30]:=30
✖
https://wolfram.com/xid/0im2i3q5y30-b99
Out[30]=30
Graphs with multi‐edges and self‐loops are supported. Here there are two copies of each edge of a star.
In[31]:=31
✖
https://wolfram.com/xid/0im2i3q5y30-om3
Out[31]=31
The adjacency list representation of a graph consists of 
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.
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. In[32]:=32
✖
https://wolfram.com/xid/0im2i3q5y30-gab
In[33]:=33
✖
https://wolfram.com/xid/0im2i3q5y30-pz5
Out[33]=33
An induced subgraph of a graph 
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 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. In[34]:=34
✖
https://wolfram.com/xid/0im2i3q5y30-d90
Out[34]=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.
In[35]:=35
✖
https://wolfram.com/xid/0im2i3q5y30-n16
Out[35]=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.
In[36]:=36
✖
https://wolfram.com/xid/0im2i3q5y30-pz2
Out[36]=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.
In[37]:=37
✖
https://wolfram.com/xid/0im2i3q5y30-b4w
Out[37]=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.
In[38]:=38
✖
https://wolfram.com/xid/0im2i3q5y30-u8k
Out[38]=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.
In[39]:=39
✖
https://wolfram.com/xid/0im2i3q5y30-xlo
Out[39]=39
In[40]:=40
✖
https://wolfram.com/xid/0im2i3q5y30-qm0
Out[40]=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 
is connected to each of two disconnected vertices. In achieving the minimum energy configuration, these two vertices end up on different sides of 
.
is connected to each of two disconnected vertices. In achieving the minimum energy configuration, these two vertices end up on different sides of . In[41]:=41
✖
https://wolfram.com/xid/0im2i3q5y30-r5c
Out[41]=41
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.
In[42]:=42
✖
https://wolfram.com/xid/0im2i3q5y30-pcf
Out[42]=42
Graph products can be very interesting. The embedding of a product has been designed to show off its structure, and is formed by shrinking the first graph and translating it to the position of each vertex in the second graph.
In[43]:=43
✖
https://wolfram.com/xid/0im2i3q5y30-ji7
Out[43]=43
The line 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.
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. In[44]:=44
✖
https://wolfram.com/xid/0im2i3q5y30-ca6
Out[44]=44
Circulants are graphs whose adjacency matrix can be constructed by rotating a vector 
times, and include complete graphs and cycles as special cases. Even random circulant graphs have an interesting, regular structure.
times, and include complete graphs and cycles as special cases. Even random circulant graphs have an interesting, regular structure. In[45]:=45
✖
https://wolfram.com/xid/0im2i3q5y30-q7x
Out[45]=45
Some graph generators create directed graphs with self‐loops, such as this de Bruijn or shift register graph encoding all length‐5 substrings of a binary alphabet.
In[46]:=46
✖
https://wolfram.com/xid/0im2i3q5y30-r6y
Out[46]=46
Hypercubes of dimension 
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.
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. In[47]:=47
✖
https://wolfram.com/xid/0im2i3q5y30-u7g
Out[47]=47
Several of the built‐in graph construction functions do not have parameters and only construct a single interesting graph. FiniteGraphs collects them together in one list for convenient reference. ShowGraphArray permits the display of multiple graphs in one window.
In[48]:=48
✖
https://wolfram.com/xid/0im2i3q5y30-xn4
Out[48]=48
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.
An undirected graph is connected if a path exists between any pair of vertices. Deleting an edge from a connected graph can disconnect it. Such an edge is called a bridge.
In[49]:=49
✖
https://wolfram.com/xid/0im2i3q5y30-mzm
Out[49]=49
GraphUnion can be used to create disconnected graphs.
In[50]:=50
✖
https://wolfram.com/xid/0im2i3q5y30-ck9
Out[50]=50
An orientation of an undirected graph 
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 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. In[51]:=51
✖
https://wolfram.com/xid/0im2i3q5y30-ryc
Out[51]=51
An articulation vertex of a graph 
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.
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. In[52]:=52
✖
https://wolfram.com/xid/0im2i3q5y30-ld5
Out[52]=52
The only articulation vertex of a star is its center, even though its deletion leaves 
connected components. Deleting a leaf leaves a connected tree.
connected components. Deleting a leaf leaves a connected tree. In[53]:=53
✖
https://wolfram.com/xid/0im2i3q5y30-c6v
Out[53]=53
In[54]:=54
✖
https://wolfram.com/xid/0im2i3q5y30-rhl
Out[54]=54
A graph is said to be 
‐connected if there does not exist a set of 
vertices whose removal disconnects the graph. The wheel is the basic triconnected graph.
‐connected if there does not exist a set of vertices whose removal disconnects the graph. The wheel is the basic triconnected graph. In[55]:=55
✖
https://wolfram.com/xid/0im2i3q5y30-lzs
Out[55]=55
A graph is 
‐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.
‐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. In[56]:=56
✖
https://wolfram.com/xid/0im2i3q5y30-x8
Out[56]=56
These two complete bipartite graphs are isomorphic, since the order of the two stages is simply reversed. Here, all isomorphisms are returned.
In[57]:=57
✖
https://wolfram.com/xid/0im2i3q5y30-ne1
Out[57]=57
A graph is self‐complementary if it is isomorphic to its complement. The smallest nontrivial self‐complementary graphs are the path on four vertices and the cycle on five.
In[58]:=58
✖
https://wolfram.com/xid/0im2i3q5y30-tcm
Out[58]=58
A directed graph in which half the possible edges exist is almost certain to contain a cycle. Directed acyclic graphs are often called DAGs.
In[59]:=59
✖
https://wolfram.com/xid/0im2i3q5y30-rk0
Out[59]=59
The girth of a graph is the length of its shortest cycle. A cage is the smallest possible regular graph (here degree 3) that has a prescribed girth.
In[60]:=60
✖
https://wolfram.com/xid/0im2i3q5y30-tzd
Out[60]=60
An Eulerian cycle is a complete tour of all the edges of a graph. An Eulerian cycle of a bipartite graph bounces back and forth between the stages.
In[61]:=61
✖
https://wolfram.com/xid/0im2i3q5y30-vph
Out[61]=61
Combinatorica functions for graph predicates.
A Hamiltonian cycle of a graph 
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.
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. In[62]:=62
✖
https://wolfram.com/xid/0im2i3q5y30-et4
Out[62]=62
The divisibility relation between integers is reflexive, since each integer divides itself, and anti‐symmetric, since 
cannot divide 
if 
. Finally, it is transitive, as 
implies 
for some integer 
, so 
implies 
.
cannot divide if . Finally, it is transitive, as implies for some integer , so implies .In[63]:=63
✖
https://wolfram.com/xid/0im2i3q5y30-jtb
Out[63]=63
Since the divisibility relation is reflexive, transitive, and anti‐symmetric, it is a partial order.
In[64]:=64
✖
https://wolfram.com/xid/0im2i3q5y30-4a
Out[64]=64
A graph 
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 
.
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 . In[65]:=65
✖
https://wolfram.com/xid/0im2i3q5y30-c81
Out[65]=65
The Hasse diagram clearly shows the lattice structure of the Boolean algebra, the partial order defined by inclusion on the set of subsets.
In[66]:=66
✖
https://wolfram.com/xid/0im2i3q5y30-gd7
Out[66]=66
A topological sort is a permutation 
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.
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. In[67]:=67
✖
https://wolfram.com/xid/0im2i3q5y30-pd5
Out[67]=67
Any labeled graph 
can be colored in a certain number of ways with exactly 
colors 
. This number is determined by the chromatic polynomial of the graph.
can be colored in a certain number of ways with exactly colors . This number is determined by the chromatic polynomial of the graph. In[68]:=68
✖
https://wolfram.com/xid/0im2i3q5y30-zgf
Out[68]=68
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.
The shortest‐path spanning tree of a grid graph is defined in terms of Manhattan distance, where the distance between points with coordinates 
and 
is 
.
and is . In[69]:=69
✖
https://wolfram.com/xid/0im2i3q5y30-gin
Out[69]=69
In an unweighted graph, there can be many different shortest paths between any pair of vertices. This path between two opposing corners goes all the way to the right, then all the way to the top.
In[70]:=70
✖
https://wolfram.com/xid/0im2i3q5y30-s0o
Out[70]=70
A minimum spanning tree of a weighted graph is a set of 
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.
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. In[71]:=71
✖
https://wolfram.com/xid/0im2i3q5y30-sz1
Out[71]=71
In[72]:=72
✖
https://wolfram.com/xid/0im2i3q5y30-fx0
Out[72]=72
In[73]:=73
✖
https://wolfram.com/xid/0im2i3q5y30-tr3
Out[73]=73
A matching, in a graph 
, 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.
, 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. In[74]:=74
✖
https://wolfram.com/xid/0im2i3q5y30-qed
Out[74]=74
In[75]:=75
✖
https://wolfram.com/xid/0im2i3q5y30-pws
Out[75]=75
Combinatorica functions for graph algorithms.