2
$\begingroup$

So recently, I have been working on a problem for a code challenge. This problem, stated here: http://pastebin.com/DxQssyKd Involved complex math that i could not figure out. Knowing this, I went to stack overflow(question there: https://stackoverflow.com/questions/42655813/algorithm-to-find-unique-non-equivalent-configurations-given-the-height-the-wi) to get an answer to what I needed to use and got this answer:

The key weapon is Burnside's lemma, which equates the number of orbits of the symmetry group G = Sw × Sh acting on the set of configurations X = ([w] × [h] → [s]) (i.e., the answer) to the sum 1/|G| ∑g∈G |Xg|, where Xg = {x | g.x = x} is the set of elements fixed by g.

Given g, it's straightforward to compute |Xg|: use g to construct a graph on vertices [w] × [h] where there is an edge between (i, j) and g(i, j) for all (i, j). Count c, the number of connected components, and return sc. The reasoning is that every vertex in a connected component must have the same state, but vertices in different components are unrelated.

Now, for 12 × 12 grids, there are far too many values of g to do this calculation on. Fortunately, when g and g' are conjugate (i.e., there exists some h such that h.g.h-1 = g') we find that |Xg'| = |{x | g'.x = x}| = |{x | h.g.h-1.x = x}| = |{x | g.h-1.x = h-1.x}| = |{h.y | g.y = y}| = |{y | g.y = y}| = |Xg|. We can thus sum over conjugacy classes and multiply each term by the number of group elements in the class.

The last piece is the conjugacy class structure of G = Sw × Sh. The conjugacy class structure of this direct product is really just the direct product of the conjugacy classes of Sw and Sh. The conjugacy classes of Sn are in one-to-one correspondence with integer partitions of n, enumerable by standard recursive methods. To compute the size of the class, you'll divide n! by the product of the partition terms (because circular permutations of the cycles are equivalent) and also by the product of the number of symmetries between cycles of the same size (product of the factorials of the multiplicities). See https://groupprops.subwiki.org/wiki/Conjugacy_class_size_formula_in_symmetric_group.

Being completely honest, I have no idea what this stuff means. I have tried looking at the linked articles and other related material, but none of it makes sense. I understand the logic behind it, I just don't know what to do with the numbers.

This answer is using the variables given from the original question, h, w, and s, being height, width, and number of states each element can have, respectively.

So how would this be done, mathematically, on a level that I, a student taking AP calc AB, could understand?

Sorry if this isn't really the site for this type of question, if not, could someone point me in the right direction?

$\endgroup$
  • $\begingroup$ Just curious: Did you provide context when you asked at SO to indicate that you were currently in AP calc AB (i.e., not in college yet)? How much abstract-algebra/ group-theory have you studies or been exposed to? $\endgroup$ – Namaste Mar 15 '17 at 16:02
  • $\begingroup$ @amWhy no I did not, thinking back, I should have. I didn't think the solution would be too advanced. I haven't really studied any of this before this, but in the past week I have really dived straight into it $\endgroup$ – beanjo55 Mar 15 '17 at 16:03
  • $\begingroup$ One tip: when on math.se, find a synonym to replace "complex" (in the sense of: Not easy to analyse or understand; complicated or intricate.), and reserve "complex" to refer to when we talk about complex numbers (e.g., $ z = a+bi$) of the set $\mathbb C$ of all complex numbers. $\endgroup$ – Namaste Mar 15 '17 at 16:07
  • $\begingroup$ Well, go back and edit your question there, adding that important piece of context. Unfortunately, since you accepted an answer you don't understand, other potential answerers are likely to assume you know group theory. Why not let the answerer of the answer you accepted know your level of study, (comment below the answer), and whether he/she can break it down a little bit so you can better understand his/her answer. $\endgroup$ – Namaste Mar 15 '17 at 16:16
  • $\begingroup$ This might refer to the problem at this MSE link. $\endgroup$ – Marko Riedel Mar 15 '17 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.