*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.

In[1]:= |

### 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.

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

In[11]:= |

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 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]:= |

Out[12]= |

In[13]:= |

Out[13]= |

In[14]:= |

Out[14]= |

In[15]:= |

Out[15]= |

In[16]:= |

Out[16]= |

*distinct*parts of the partition.

In[17]:= |

Out[17]= |

In[18]:= |

Out[18]= |

In[19]:= |

Out[19]= |

In[20]:= |

Out[20]//TableForm= | |

In[21]:= |

Out[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[22]:= |

Out[22]= |

In[23]:= |

Out[23]= |

In[24]:= |

Out[24]//TableForm= | |

In[25]:= |

Out[25]= |

In[26]:= |

Out[26]= |

In[27]:= |

Out[27]= |

In[28]:= |

Out[28]= |

In[29]:= |

Out[29]= |

In[30]:= |

Out[30]= |

In[31]:= |

Out[31]= |

In[32]:= |

Out[32]//TableForm= | |

In[33]:= |

Out[33]= |

In[34]:= |

Out[34]= |

In[35]:= |

Out[35]= |

In[36]:= |

Out[36]= |

In[37]:= |

Out[37]= |

In[38]:= |

Out[38]= |

In[39]:= |

Out[39]= |

In[40]:= |

Out[40]= |

In[41]:= |

Out[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]:= |

Out[42]= |

In[43]:= |

Out[43]= |

In[44]:= |

Out[44]= |

In[45]:= |

Out[45]= |

*de Bruijn*or

*shift register*graph encoding all length-5 substrings of a binary alphabet.

In[46]:= |

Out[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.

In[47]:= |

Out[47]= |

In[48]:= |

Out[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.

In[49]:= |

Out[49]= |

In[50]:= |

Out[50]= |

In[51]:= |

Out[51]= |

In[52]:= |

Out[52]= |

In[53]:= |

Out[53]= |

In[54]:= |

Out[54]= |

In[55]:= |

Out[55]= |

In[56]:= |

Out[56]= |

In[57]:= |

Out[57]= |

In[58]:= |

Out[58]= |

In[59]:= |

Out[59]= |

In[60]:= |

Out[60]= |

In[61]:= |

Out[61]= |

*Combinatorica* functions for graph predicates.

In[62]:= |

Out[62]= |

In[63]:= |

Out[63]= |

In[64]:= |

Out[64]= |

In[65]:= |

Out[65]= |

In[66]:= |

Out[66]= |

In[67]:= |

Out[67]= |

In[68]:= |

Out[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.

In[69]:= |

Out[69]= |

In[70]:= |

Out[70]= |

In[71]:= |

Out[71]= |

In[72]:= |

Out[72]= |

In[73]:= |

Out[73]= |

In[74]:= |

Out[74]= |

In[75]:= |

Out[75]= |

*Combinatorica* functions for graph algorithms.