Meeting Number Three, March 9th: 

We applied Burnside's Theorem to some more exciting cases:

1.  The number of distinct ways to 2-color a 4 by 4 checkerboard.  We used the full group of symmetries of the square, although in a given application that might not be the right group!  For each kind of symmetry, we considered it as acting on the set of all 16 cells.  We then analyzed the cycle structure for each symmetry; this gave us the count of colorings fixed by the symmetry.

90 degree rotation:  This has 4 4-cycles, giving 2^4 fixed colorings.

180 degree rotation:  This has 8 2-cycles, giving 2^8 fixed colorings.

horizontal or vertical flips:  These have 8 2- cycles, giving 2^8 fixed colorings.

diagonal flips:  These have 6 2-cycles and 4 1-cycles.  This gives 2^10 colorings.

identity:  16 1-cycles, giving all 2^16 colorings.

By Burnside, we get that the number of orbits is 

(1/8)(2*2^4+2^8+2*2^8+2*2^10+2^16).

2.  We then considered the number of two-colorings of the same board, for which 8 are white and 8 are black.  Here the computations were a bit more interesting. Would somebody like to write up our solution?? 

Last but not least:  We considered Josh's question regarding 2 colorings of the 4 by 4 square (and larger ...) where each row and each column has half white and half black squares.  We didn't complete a count of the all configurations X.  Josh's research class is working on this.  This makes it difficult to apply Burnside!  Let's work on this before our next meeting.

Also:  What group do you want to use?? Josh proposed the group consisting of permutations of rows, or of columns, rather than the symmetries of the square.  There are lots of interesting counts to explore!! 

Meeting Number Two, March 2nd:  

We found that the formula we got last time for the number of orbits does indeed work for the three-coloring of the faces of a cube.  In that example, |G|=24 (the group is really the permutations of the diagonals).  Meanwhile, the size of the set X is 60.  But in this example, most of the stabilizer subgroups are trivial, and 12 of them have size two.  We then get 72/24=3, which is the number of orbits, which we of course already knew.

We then finally arrived at something exciting:  By building a rectangular array (rows corresponding to elements of G and columns to elements of X), we discovered that we could sum row by row, instead of column by column.

To do this, for any group element g we had to define the set Fix(g), which is exactly the set of elements of X that are left fixed by g.  We then got Burnside's Theorem:

The number of distinct orbits of G acting on X is precisely

1/|G|(Sum(|Fix(g)|).  

We applied this easily to the two by two checkerboard two-coloring problem.

Question for next time:  can we apply this to counting the number of 2-colorings of an n by n checkerboard?

Meeting Number One, February 24th:  

Here was my proposal for what we could do:

We have conjectured the following.  Suppose that G is a finite group acting on a set X.  Given an element x of X, let Ox be the orbit of x under the group G.  Let Sx be the stabilizer subgroup of G;  that is, it is the set of group elements leaving x fixed.  Our examples suggest that |Ox||Sx|=|G|. 

Now at our last meeting, we proved LaGrange's Theorem.  This says in particular that |Sx| divides |G|.  In fact, it asserts that |Sx|[G:Sx]=|G|, where [G:Sx] is the set of distinct cosets of Sx in G.  

Comparing what we want with what we have proved, it clearly remains to show that |Ox|=[G:Sx].  That is, the number of elements of the orbit of x should equal the number of cosets of Sx in G.  

Confession time:  in my proof of LaGrange's theorem, I used right cosets (sets of the form Ha, where H is a subgroup of G).  For the most efficient proof of what we want, I should have used left cosets.  Then aH=bH if and only if b^{-1}a is an element of H.  

Before our meeting, try to prove that |Ox|=[G:Sx].  My hint is this:  for any left coset a(Sx), assign the orbit element ax.  Is this a one-to-one correspondence???

Another thing we can try:  what does this mean in light of the cube-coloring problem?  

We actually managed to accomplish most of this.  We proved the orbit stabilizer theorem, and we started thinking about the cube-coloring example.

From the orbit-stabilizer theorem, we then managed to obtain an actual formula for the number of orbits for a group G acting on a set X. This formula is this.  Form the sum of the sizes of all the stabilizers Sx, over all x in X.  Then divide by the size of the group |G|.  We observed that this is not necessarily a very useful formula, because typically we have to sum over all elements in X, which might be a big set.