Abstract:
This project is centered on the permutahedron and associahedron. The
permutahedron and associahedron are geometric shapes that represent
several concepts of combinatorial mathematics, the details of which can be
found in the research section below. Specifically for this project, the
permutahedron for n=4 and the associahedron for n=5 (five factors) have
been created, and there has been an emphasis on designing ways to
represent their combinatorial properties visually (i.e. how do we
represent the information that is represented by each of the vertices of
these two polyhedrons without the use of text, or other text based
guides). These two objects correspond to polyhedrons that contain 24 and
14 vertices respectively. Using illiSkel and CAVEskel as a guide, both of
these objects can be created and can be viewed on either a regular
monitor, or in the CAVE. However, the code attached is the version that
does not run in the CAVE (the CAVE code was made by moving the attached
code into CAVEskel, but the ways in which the objects are drawn is the
same in both versions).
Permutahedron and Associahedron Operating Instructions:
Desktop Version:
After opening either the associahedron or permutahedron, the controls are
the same as those of illiSkel, with the following additions:
Press 'b': Pressing 'b' will cause colored balls to appear at the
vertices. In the associahedron, pressing the 'b' button again
will then cause rectangular boxes to appear around the
balls. Continuing to press 'b' will cause the balls to
disappear, and then the boxes to disappear (associahedron
only). If the "shift" key is held down, this cycle runs in
the opposite manner (first boxes appear, then balls).
Press 'f': Pressing 'f' will cause the polyhedrons to have color
filled sides in place of the standard wire-frame images.
When sides are turned on, pressing 'b' will function as
normal, however, in the associahedron, users are unable to
see boxes being generated from the center of the polyhedron
(but they will eventually appear).
CAVE Version:
The CAVE versions of these objects operate exactly like CAVEskel, with the
following changes:
Left Button (in TURNMODE):
In place of the standard morphing, the left button on the
wand will now act in a manner identical to pressing 'b' in
the desktop version. It is important to note that TURNMODE
is the mode that the CAVE version permutahedrons and
associahedrons open in by default.
Left Button (not in TURNMODE):
When the user leaves TURNMODE by pressing the middle button
on the wand, the functionality of the left button changes and
is no longer the same as pressing 'b'. Instead, pressing the
left button will now be the same as pressing 'f' on the
keyboard as explained above.
Permutation and Associahedron Code Explanation:
All the attached code has been annotated using C style commenting, and
these comments are very self-explanatory. However, the functions of
illiSkel that have been drastically altered, and those new ones that have
been added deserve a bit of explanation. In the creation of both of these
objects, there are three main stages. First, the object (wire-frame or
solid) must be drawn. Second, the balls at each vertex must be drawn.
Finally, the wire-frame rectangular boxes must be drawn around the balls
at the vertices (this step only applies to the associahedron). Below is a
brief overview of how each of these steps is accomplished in the attached
code.
Creating the Polyhedron:
The first step as mentioned before is drawing the polyhedron itself. This
is done by the functions drawash() and drawpermut(). The way in which
these functions accomplish their tasks is relatively simple. There are
two global arrays, one named vertices[] and one named path[]. Vertices[]
is an array that holds the 3D Cartesian coordinates of each vertex, and
these are hard-coded into the array by the programmer at its declaration.
The path[] array is also hard coded, and it contains the path from vertex
to vertex to follow in order to complete the polyhedron. It is important
to note that this is not a minimum path, it is a path that traverses the
object one side at a time, so that if the users desires that the sides
have color and not simply be wire-frame, that task is easy to accomplish.
The way in which these draw functions use the arrays is very simple.
Path[] is looped through until its end, and on each loop a line segment is
drawn from one vertex to another until the object is complete. These
lines are drawn one side at a time, so that in the event solid sides are
requested, a color will be assigned and then GL_POLYGON can be used in
place of a line strip.
Creating the Vertex Balls:
The drawing of the shiny spheres that appear at the vertices involves
three functions, drawballs(), sballs(), and drawvert(). Of these,
drawballs() is the function most responsible for the creation and
placement of the spheres, and it is the function that is called
specifically in drawall(). Drawballs() moves and creates the spheres by
repeatedly doing the following for each vertex. First, drawballs() finds
a vector from the center of the polyhedron to a vertex. Next, the unit
vector on the same path is found, and this will be used in determining how
to move the balls. Finally, drawballs() takes the original length of the
vector, and adds a small amount to place a sphere outside the vertex, and
then the color of the sphere currently being drawn is sent into sballs()
and it creates a shiny sphere of the correct color. In the associahedron
the color order will always be the same, however, in the permutahedron
drawballs() makes use of the ballorder[] array to determine which color
the next ball should be. Sballs() and drawvert() work together to draw
the shiny spheres in almost the same exact way as drawtor() and drawvert()
do in the illiSkel, in fact, sballs() is near identical to drawtor() and
drawvert() is also virtually unchanged. The few changes that were made is
that now a sphere is drawn instead of a torus, and illiPaint is no longer
used, instead the color is determined by the parameter sent in by
drawballs().
Creating the Wire-frame Vertex Boxes (Associahedron Only):
The boxes are drawn and moved into place in the function drawrects().
Similar to drawballs(), this is done through the use of vectors. First, a
unit vector is calculated from the center of the associahedron to a
vertex. Then drawrects() finds one of the infinitely many vectors
perpendicular to the unit vector we found earlier. Finally, a third
perpendicular vector is found using the cross-product of the two vectors
found earlier. These three vectors are then used together to draw the
boxes around the spheres. A brief explanation of how the boxes know where
to go should be given. There is an array parens[] that stores how the
boxes should be arranged for each vertex. Each row of parens[] represents
one long string of 1's, 2's and 3's. The 1 represents a ball, a 2
represents the start of a box and the 3 represents the close of a box.
For example 12211321133 would equate to O((OO)(OO)), where O is a ball.
Drawrects() reads the values from the right to the left, when a 3 is
encountered, its position (in terms of which ball is before or after) is
pushed onto a stack. Then drawrects() continues to the left until it
finds a 2, when it does it pops a position of the stack, and then draws a
box from its current position to the position that was just popped off the
stack.
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
-----------------------------------------------------------------
|Number 1|Number 2|Number 3|Number 4|Number 5|Number 6
-----------------------------------------------------------------
Position 1 | 0 | 0 | 0 | 0 | 1 | 0 |
-----------------------------------------------------------------
Position 2 | 0 | 0 | 0 | 1 | 0 | 0 |
-----------------------------------------------------------------
Position 3 | 0 | 0 | 1 | 0 | 0 | 0 |
-----------------------------------------------------------------
Position 4 | 0 | 0 | 0 | 0 | 0 | 1 |
-----------------------------------------------------------------
Position 5 | 0 | 1 | 0 | 0 | 0 | 0 |
-----------------------------------------------------------------
Position 6 | 1 | 0 | 0 | 0 | 0 | 0 |
-----------------------------------------------------------------
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-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) = 2^n
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)*y^k
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:
C[n] = Sum of C[k]* C[n-k-1] from (k=0 to n-1) with C[0] =1
The solution to this recurrence is the following:
C[n]=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 C[3] =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:
C[n] = C(2n,n)-C(2n,n-1)
= C(2n,n)-C(2n,n)*n/(n+1)
= (1-n/(n+1))*C(2n,n)
C[n] = 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 C[3] =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.
References:
Research References:
Baez, John. "This Week's Finds in Mathematical Physics (Week 144)."
INFOMAG Russian Ministry of Sciences. January 21, 2000.
http://www.infomag.ru:8082/dbase/B003E/000126-082.txt
Bogomolny, Alexander. "Permutations" www.cut-the-knot.com. Bogomolny is
a former Associate Professor of Mathematics at the University of Iowa.
http://www.cut-the-knot.com/do_you_know/permutation.shtml
"Catalan Number" MathWorld. Wolfram Research.
http://mathworld.wolfram.com/CatalanNumber.html
"Catalan numbers." University of Illinois Champaign-Urbana. CS273:
Introduction to Theoretical Computer Science Spring 2003 Class Notes.
Prepared by: Ari Trachtenberg, Ed Reingold, Tanya Berger-Wolf, David
Bunde, Jeff Erikson, Mitch Harris, Cinda Heeren, and Shripad Thite.
http://www-courses.cs.uiuc.edu/~cs273/notes/catalan.pdf
"Counting Sets." University of Illinois Champaign-Urbana. CS273:
Introduction to Theoretical Computer Science Spring 2003 Class Notes.
Prepared by: Ari Trachtenberg, Ed Reingold, Tanya Berger-Wolf, David
Bunde, Jeff Erikson, Mitch Harris, Cinda Heeren, and Shripad Thite.
http://www-courses.cs.uiuc.edu/~cs273/notes/combos.pdf
Dickau, Robert M. "Catalan numbers." Drexel University.
http://mathforum.org/advanced/robertd/catalan.html
Eppstein, David. "The Geometry Junkyard." University of California,
Irvine.
http://www.ics.uci.edu/~eppstein/junkyard/3d.html
Fischer, Hanspeter. "The 3-Dimensional Associahedron." Ball State
University.
http://www.cs.bsu.edu/~fischer/math215/associahedron.html
Hwa, Theodore. "Counting Nodes in Planar Rooted Trees." Stanford
University.
http://www.stanford.edu/~hwatheod/prt.html
"Information of Permutations." The (Combinatorial) Object Server.
University of Victoria, British Columbia Canada.
http://www.theory.csc.uvic.ca/~cos/inf/perm/PermInfo.html
"Permutation" MathWorld. Wolfram Research.
http://mathworld.wolfram.com/Permutation.html
Rote, Günter. "Binary trees having a given number of nodes with 0, 1, and
2 children." Graz University of Technology.
http://www.mat.univie.ac.at/~slc/wpapers/s38pr_rote.pdf
Whitley, Darrel. "C1.4 Permuatations." Handbook of Evolutionary
Computation. IOP Publishing Ltd. And Oxford University Press. 1997.
http://www.iop.org/Books/CIL/HEC/abs/ecc1_4.htm
Zabrocki, Mike. "The permutahedron for n=4." York University.
http://garsia.math.yorku.ca/~zabrocki/posets/phedron4/
Code References:
illiSkel and CAVEskel acted as the framework for the associahedron and the
permutahedron in this project. As part of illiSkel, the lighted vertex
balls make use of the illiLight lighting model.
illiSkel:
skel.c = OpenSkelGlut.c = Noosh97 with CAVE removed
(C) 1994--2002 Board of Trustees University of Illinois
A Model Real-Time Interactive C/OpenGL/GLUT Animator
George Francis, Stuart Levy, Glenn Chappell, Chris Hartman
e-mail gfrancis@math.uiuc.edu
CAVEskel:
skel.c = OpenSkelGlut.c = Noosh97 with CAVE removed and put back
(C) 1994 Board of Trustees University of Illinois
A Model Real-Time Interactive OpenGL Application
George Francis, Glenn Chappell, Chris Hartman
e-mail gfrancis@math.uiuc.edu
illiLight:
illiLight by Ray Idaszak 1989