Last edited May 12, 2003 by wtbaker@uiuc.edu
Find this document at http://www.ncsa.uiuc.edu/Classes/MATH198/wtbaker/opinstruct.html
Back Home
Back To Project Page

Research/Mathematics of the Permutahedron and Associahedron:



Permutations:

Permutations represent the number of ways of obtaining an ordered subset of r elements from a set of n elements (written as P(n,r)). The number of total possible permutations can be obtained from the following recursive equation and explicit solution.

P(n,r) = n*P(n-1, r-1), P(n,0)=1

P(n,r) = n!/(n-r)!

One way of visualizing permutations is through the use of a zero-one matrix. This is a matrix which contains exactly one "1" in each row and column. The example below represents 543621

Number1Number 2Number 3Number 4Number 5Number 6
Position 1000010
Position 2000100
Position 3001000
Position 4000001
Position 5010000
Position 6100000


Permutations can be generated in two different orders. In lexicographic order permutations are listed in numeric order, so that they go from the least to the greatest number (i.e. for {1,2,3} permutations are 123, 132, 213, 231, 312, 321). The other ordering used when listing permutations called the transposition order. In transposition order, two successive permutations differ by the transposition of two adjacent elements (i.e. 123, 132, 312, 321, 231, 213). It is interesting to note that in the permutahedron, following the edges without jumping results in a transposition ordering of permutations.

Permutations are used in a variety of mathematical areas, especially probability. One example would be determining the likelihood of drawing a specific ordering of chips from an urn containing numbered chips. We would simply divide 1 by all possible permutations of the desired length. Permutations are also used in Tableau tables, specifically every permutation corresponds in a natural way to a pair of tableau of the same shape.

Finally, permutations are the basis of the permutahedron. A permutahedron is a polyhedron in which each vertex represents a possible permutation. Therefore, for any order n of permutation, there are a total n! vertices, each representing a permutation of length n from n distinct objects. Two vertices are connected by an edge only if they differ by one transposition of adjacent elements (i.e. for n=4, 1234 would have an edge only to 1324, 1243, and 2134). This property is demonstrated in the CAVE permutahedron through the use of colored balls. For each vertex, 4 colored balls are arranged in an order, and this order represents the permutation for that vertex.

Combinations:

Combinations represent the number of ways to pick an unordered set of elements. They are related to permutations, which can be seen in the formula below for choosing r elements from a set of size n:

C(n,r) = P(n,r)/r! = n!/((n-r)!r!)

A quick explanation is easy to give. There are P(n,r) possible ways to make sets of size r from n items where order matters. How many possible orderings are there of the r unique items? There are r! Hence, each combination corresponds to r! of the permutations, so the number of combinations of size r from a set of size n is P(n,r)/r!


C(n,n)=1 There is one way of picking all the items
C(n,0)=1 There is one way of picking no items
C(n,1)=n There are n ways to pick one object from n
C(n,n-1)=n Think of this as choosing the one item to be left behind from the subset and you then have the same as C(n,1).

C(n,r) = C(n,n-r) The number of r-combinations is equal to the number of n-r combinations because choosing n-r items is the same as choosing r and taking the n-r items left over. Another way of saying this is every subset of size r has a one-to-one correspondence with a subset of size n-r, namely its complement.

C(n,m)C(m,k) = C(n,k)C(n-k,m-k)

What this is saying is from a set of n, choose m elements, and then from those m choose k elements. Another way of doing this is what appears on the right side of the identity. That is choose the small subset first C(n,k) and then choose the rest of size m with leftovers (there are m-k items in that subset to choose and n-k items to choose from).

C(n,r) = C(n,n-r) The number of r-combinations is equal to the number of n-r combinations because choosing n-r items is the same as choosing r and taking the n-r items left over. Another way of saying this is every subset of size r has a one-to-one correspondence with a subset of size n-r, namely its complement.

C(n,m)C(m,k) = C(n,k)C(n-k,m-k)

What this is saying is from a set of n, choose m elements, and then from those m choose k elements. Another way of doing this is what appears on the right side of the identity. That is choose the small subset first C(n,k) and then choose the rest of size m with leftovers (there are m-k items in that subset to choose and n-k items to choose from).

C(n,r) = C(n-1,r-1) + C(n-1,r) with C(n,0)=1 and C(n,n)=1 base cases

This is Pascal's identity.

Sum of C(n,k) from (k=0 to n) = 2n

This gives the number of all possible subsets on a set of size n.

Sum of (-1)k*C(n,k) from (k=0 to n) = 0, n>=0

This sum shows that the number of subsets of even size equals the number of sets of odd size from a set of n elements.

Combinations are used in a variety of areas in mathematics. One obvious use is with the binomial theorem, which gives the coefficients of the terms in the expansion of (x+y)n. Its form is Sum of C(n,k)*x(n-k)*yk from (k=0 to n). Combinations are also used in calculating probabilities. For example if we have an urn with chips labeled 1 to 8, and we choose 3, the probability that the largest number we choose is 5 is given by C(1,1)*C(4,2)/C(8,3). This is because one chip must be 5 (C(1,1)), and then there are 4 numbers with values less than 5 to choose the other two chips from (C(4,2)). We then divide by the total possible sets of 3 chips possible (C(8,3)). Another use of combinations is in the hypergeometric distribution. Suppose an urn has r red chips and w white chips, and suppose that n chips are chosen from a total of N chips (N=r+w), and X is the number of red chips selected, then the probability of X equaling k is given by the following: P(X=k) = C(r,k)*C(w,n-k)/C(N,n). Finally, combinations form the basis of the last topic to be discussed, the Catalan numbers, which directly relate to the associahedron.

Catalan Numbers:

Catalan numbers are an integer sequence given by the recurrence:

Cn = Sum of Ck* Cn-k-1 from (k=0 to n-1) with C0 =1

The solution to this recurrence is the following:

Cn=1/(n+1) * C(2n,n)

To understand how this solution comes about, it is important to first discuss a few situations in which Catalan numbers appear.

1) Bit strings: How many bit strings of length 2n are possible when the number of ones equals the number of zeros, and from left to right the number of zeros never exceeds the number of ones.

For n=3: The answer is the third Catalan number C3 =5. The admissible bit strings are: 111000, 110010, 110100, 101100, 101010

2) Admissible lattice paths: How many paths on an integer lattice from (0,0) to (n,n) are possible only allowing moves that go to the right or up, and that never cross the diagonal?

There is a direct correspondence between this question and our bit string question, a move to the right is the same as a 1 in the bit string and a move up is a 0, and hence our answer is the Catalan number for n.

We can use this example to prove our explicit solution. We know all possible paths on the lattice to be C(2n,n) (imagine that each space is labeled, and we are choosing half of them to be ones, then there are 2n choose n possibilities). We will take this and subtract the number of paths from this set that must cross the diagonal. Those are the ones that must touch the line from (0,1) to (n-1,n). This is the same as the number of all possible paths from (0,0) to (n-1,n+1) (everyone of these paths must cross the diagonal of our original path, and hence these are all inadmissible lattice paths. The number of these paths is C(n-1+n+1,n-1)=C(2n,n-1). When we subtract that from all possible paths of the original lattice we get the following:

Cn  =  C(2n,n)-C(2n,n-1)
   =  C(2n,n)-C(2n,n)*n/(n+1)
   =  (1-n/(n+1))*C(2n,n)
Cn  =   1/(n+1) * C(2n,n)

Catalan numbers also are used to answer the following additional questions:

3) How many ways can a regular n-gon be divided into n-2 triangles?

4) How many possible ordered rooted trees with n edges (n+1 nodes) are possible?

5) How many full binary ordered rooted trees (every internal vertex has 2 children) with n+1 leaf nodes are possible?

6) How many ways can parenthesis be placed in a sequence of n+1 numbers to be multiplied two at a time?

These questions link directly to the associahedron. The associahedron is a polyhedron with vertices that represent each of these possible parentheses. Vertices are linked by edges when the parenthesis differ by one set (i.e. for n+1=4, ((ab)c)d would have an edge to (a(bc))d and (ab)(cd) ). The Catalan number relate because an associahedron representing the possible multiplications of n+1 numbers has a number of vertices equal to the nth Catalan number (so that if there are 4 numbers, the number of vertices equals C3 =5). This property is demonstrated in the cave through the use of rectangular boxes and vertex balls. For this associahedron, there are 5 vertex balls, and the order of the colors is the same for each vertex. Each of these balls represents a number, and rectangular boxes surround them to represent how the numbers are being multiplied together. In this manner, two vertices are connected when two of the three boxes they share are the same.