SELF-REVERSED CONFIGURATIONS ON CUBE
Y. TESHIMA, K. KASE, S. Usami,
1 ENUMERATION IN COMBINATORIAL MATHEMATICS
Enumeration in combinatorial mathematics is important in modern science and technology. For example, it was applied in physics (Mayer and Mayer 1940), chemistry (Pólya 1937), information science (Harrison 1965), computer graphics (Lorensen and Cline 1987), etc. .
Recently, the authors investigated the enumeration of cutting point configurations in cube cutting (Teshima et al. 2004), which provided the mathematical foundation of Volume CAD (VCAD) as a next generation computer-aided design (CAD) tool (Kase et al. 2003). The enumeration process involved was equivalent to finding the distinct ways of painting the twelve edges of a cube with two colors.
In this short paper, enumerations for painting six faces, eight vertices, and 12 edges of a cube with two colors are described in Section 1.1, and "self-reversed configuration" is discussed in Section 2.
1.1 Painting cube with two colors
We summarized how many equivalent classes (= patterns) there are when we paint six faces, eight vertices, and 12 edges of a cube using two colors black and white. If the symmetry of the cube were not taken into account, there were 26=64 different configurations altogether for face coloring, 28=256 different configurations altogether for vertex coloring, and 212=4096 different configurations altogether for edge coloring. We considered both symmetric group the rotation group and reflection group of a cube. We calculated the number of patterns in all configurations using the Pólya's theory of counting (Redfield 1927 and Pólya 1937), which is useful for enumeration under group action. In most applications of the Pólya theory, only the rotation group is considered and then enantiomorphous pairs which are mirror images of each other are counted individually. However, from the standpoint of pure geometry or pure group theory, such distinction is superfluous and it is proper to add the reflection group for reducing them (Coxeter 1989).
Enumeration results are shown in Table 1, 2, and 3. The second row in the tables shows the number of patterns under the rotation group only, and the third row shows the number of patterns under both the rotation and reflection groups. On face coloring, all 64 configurations are classified into 10 patterns, all 256 configurations are classified into 23 or 22 patterns on vertices coloring, and all 4096 configurations are classified into 218 or 144 patterns on edge coloring.
Table 1: Number of patterns for painting six faces of cube using black
Table 2: Number of patterns for painting eight vertices of cube using black and white
Table 3: Number of patterns for painting 12 edges of cube using black and white
2 SELF-REVERSED CONFIGURATION
When interested only in the contrast patterns in Table 1, 2, and 3, we further reduce the total number of patterns. In face coloring, for example, in the case of (number of black faces, number of white faces) = (0, 6), (1, 5), and (2, 4), their contrast patterns are the same as the cases: (6, 0), (5, 1), and (4, 2). Thus, the former patterns can be reversed into the latter patterns. Here, "reverse" means the interchange of the two colors black and white. We need careful judgment for two patterns in the case of (3, 3) in Table 1. The same situation occurs in vertex coloring and edge coloring. We must judge six patterns in the case of (number of black vertices, number of white vertices) = (4, 4) in Table 2, and 30 patterns in the case of (number of black edges, number of white edges) = (6, 6) in Table 3.
As a result, each of the two patterns of (3, 3) in face coloring is self-reversed configuration, and each of the six patterns of (4, 4) in vertex coloring is also self-reversed configuration. Concerning the 30 patterns of (6, 6) in edge coloring, only eight patterns are self-reversed configurations and the other 11 patterns are reversed into the remaining 11 patterns. Figure 1, 2, and 3 show these results. The index with an underline shows that the figure is self-reversed. (And the index with an asterisk in the figures shows that the figure is one of the enantiomorphous pairs.)
Figure 1(above): Two contrast patterns of (3,3) in face coloring
Figure 2(right): Six contrast patterns of (4,4) in vertex coloring
Figure 3: Nineteen contrast patterns of (6,6) in edge coloring.
Coxeter, H. S. M. (1989) Introduction to Geometry, Second edition, Section 15.6, New York: Wiley.
Kase, K., Teshima, Y., Usami, S., Ohmori, H., Teodosiu, C., and Makinouchi, A. (2003) Volume CAD, Proceedings of the 3rd International Workshop on Volume Graphics (VG03), 145-150 and 173.
Lorensen, W. E. and Cline, H. E., (1987) Marching cubes: A high resolution 3D surface construction algorithm, Computer Graphics (SIGGRAPH 87 Conference Proceedings), 21(4), 163-169.
Mayer, J. E. and Mayer, M. G. (1940) Statistical Mechanics, New York: Wiley.
Pólya, G. (1937) Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen, und chemische Verbindungen, Acta Math., 68,145-254.
Redfield, J. H. (1927) The theory of group reduced distributions, Amer. J. Math.,49, 433-455.
Teshima, Y., Kase, K., Usami, S., Kato, M., Ikeda, N.,
and Makinouchi, A. (2004) Enumeration of Cutting Points Configuration in
Cube Cutting, to appear in proceedings of HART2004, Univ. of Fukui, Japan.