Proving your solution when using constructive counting

How many distinct ways can the faces of a cube be painted with $6$ different colors? Two paintings are considered identical if the cube can be oriented so that the cubes look the same.

This problem can be solved in at least two ways that I know of. One of them is to fix the bottom of cube and count the number of possible distinct paintings. There are $5$ possibilities for the top of the cube and since the other $4$ sides make up a "circle" there are $3!$ unique arrangements there. In all, there are $5 \times 3!$ unique paintings.

To use this method we must be sure of three things:

1) Our method can be used to construct any element of the set we are counting.

2) The same number of options were available during any particular construction.

3) We will never construct the same object in two different ways, i.e. by making different choices during our construction.

I want to see if I understand these bullet points.

1. A unique painting of a cube is an element in the set we are counting. Each one can be constructed by fixing the bottom of a cube.

2. I think they are saying there are as many outcomes if we start by constructing the painting by fixing the red side on the bottom of the cube as there would be if we started our construction by fixing the black side of the cube first. [Black and red are just arbitrary colors here.]

3. I am not sure what this is saying.

My questions. Does my interpretation of the first two bullets make sense? Can someone please elaborate on the third one.

1) Essentially yes though I find your wording to be too close to the original formulation.

Conceptually speaking this is about the method being "surjective"; showing that it really generates all cube coloring and doesn't miss any like say always putting "red adjacent to blue" would miss out on the case where "red is opposite to blue" on the cube.

2) Sort of. The method is essentially not to vary the bottom color at all but always starting by painting the bottom side with color "A". The first step you have options in is the second one where you paint the top one in one of the colors {"B", "C", "D", "E", "F"} so you should be sure that the number of ways to paint the (non-top non-bottom) sides is independent of the color at the top. That it is always 3!.

This step need not actually be universal in counting problems if there is some branching.

3) This corresponds to the method being "injective", or in simpler terms that there is no "double-counting".

Remember why combinations are a little tricky to compute. If are to select a group of 2 objects out of a group of 10 and your counting was "first I have 10 options and then I have 9 options for the second choice and thus a total of 10*9" you'd engage in double counting because picking A first and B second is the same as picking B first and A second.

Since I coincidentally have an illustration of the result of this algorithm I'm going to append it to this post.

• Makes perfect sense! Thanks. Commented Mar 15, 2017 at 19:12