I have this combinatorial exercise which I think should be solved using Burnside's lemma. I used this link as a reference to study: https://brilliant.org/wiki/burnsides-lemma/ It sounds pretty simple but I can't make it work.
I have an R×C grid in which each of the cells can take value 0 or 1. I am asked to calculate the number of possible orbits. Equivalency is defined as: any two grids with each cell in the same state where the actual order of the rows and columns do not matter (and can thus be freely swapped around).
An orbit is defined as the set of equivalent grids.
Having said that, I'm trying to start with a simple grid, a 2x2. Ignoring Burnside for the moment, and taking all the combinations, I get 2^4 = 16 grids. I wrote the 16 possibilities and I could see that from these I get 7 orbits.
Burnside say that the number of Orbits equals the sum of Fixed Points divided by the number of Symmetries (transformations) of the grid. I wish I could get 7 orbits by applying Burnside to the 2x2 grid but I can't figure out.
In fact at the moment I found 3 possible Symmetries, based on the equivalency provided by the text
- The identity, for which I do not apply any transformation
- Exchange of columns
- Exchange of rows
For each of these I also check the number of fixed points by hand:
- Identity -> 16
- Column -> 4
- Row -> 4
I apply Burnside: Orb = (16 + 4 + 4) / 3 = 8 while it should be 7.
Thanks