Burnside's lemma is a clever tool to calculate the number of distinct configurations up to a given symmetry group.

Wikipedia's example shows that the number of rotationally distinct colourings of the faces of a cube using three colours is 57. This introduction similarly shows that there are 6 distinct squares whose vertices have one of two colours.

But what if we actually want to construct the 57 distinct-coloured cubes, or the 6 distinct-coloured squares, instead of just counting them? Is there a non-brute-force way of doing this?

  • 3
    $\begingroup$ It's unclear to me what it would mean to give a non-brute-force method of constructing a bunch of objects. The difference between constructing $n$ objects and computing $n$ is that you can write down $n$ using $\log n$ bits, but writing down $n$ objects presumably takes at least $n$ bits. Here $n$ might be e.g. the number of isomorphism classes of graphs on $10$ vertices, which you can count using Burnside's lemma and which is something like $\frac{1}{10!} 2^{{10 \choose 2}}$, which is pretty big. $\endgroup$ – Qiaochu Yuan Sep 6 '17 at 18:03

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.