A000543 Number of inequivalent ways to color vertices of a cube using at most n colors.

0, 1, 23, 333, 2916, 16725, 70911, 241913, 701968, 1798281, 4173775, 8942021, 17930628, 34009053, 61518471, 106823025, 179003456, 290715793, 459239463, 707740861, 1066780100, 1576090341, 2286660783, 3263156073, 4586706576

Offset: 0

Author

Clint. C. Williams (Clintwill(AT)aol.com)

Keywords

• nonn
• easy

Comments

Here inequivalent means under the action of the rotation group of the cube, of order 24, which in its action on the vertices has cycle index (x1^8 + 9*x2^4 + 6*x4^2 + 8*x1^2*x3^2)/24.

Also the number of ways to color the faces of a regular octahedron with n colors, counting mirror images separately.

From Robert A. Russell, Oct 08 2020: (Start)

Each chiral pair is counted as two when enumerating oriented arrangements. The Schläfli symbols for the regular octahedron and cube are {3,4} and {4,3} respectively. They are mutually dual.

There are 24 elements in the rotation group of the regular octahedron/cube. They divide into five conjugacy classes. The first formula is obtained by averaging the cube vertex (octahedron face) cycle indices after replacing x_i^j with n^j according to the Pólya enumeration theorem.

Conjugacy Class Count Even Cycle Indices

Identity 1 x_1^8

Vertex rotation 8 x_1^2x_3^2

Edge rotation 6 x_2^4

Small face rotation 6 x_4^2

Large face rotation 3 x_2^4 (End)

References

• N. G. De Bruijn, Polya's theory of counting, in E. F. Beckenbach, ed., Applied Combinatorial Mathematics, Wiley, 1964, pp. 144-184 (see p. 147).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, Polyhedron Coloring
• Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Crossrefs

Cf. A128766 (unoriented), A337896 (chiral), A337897 (achiral).

Other elements: A060530 (edges), A047780 (cube faces, octahedron vertices).

Cf. A006008 (tetrahedron), A000545 (dodecahedron faces, icosahedron vertices), A054472 (icosahedron faces, dodecahedron vertices).

Row 3 of A325012 (orthotope vertices, orthoplex facets) and A337891 (orthoplex faces, orthotope peaks).

Programs

Magma

[(1/24)*n^2*(n^6+17*n^2+6): n in [0..30]]; // Vincenzo Librandi, Apr 15 2012

Maple

f:= n->(1/24)*n^2*(n^6+17*n^2+6); seq(f(n), n=0..40);

Mathematica

CoefficientList[Series[x*(1+x)*(1+13*x+149*x^2+514*x^3+149*x^4+13*x^5+x^6)/(1-x)^9,{x,0,30}],x] (* Vincenzo Librandi, Apr 15 2012 *)
Table[(n^8+17n^4+6n^2)/24,{n,0,30}] (* Robert A. Russell, Oct 08 2020 *)

Formula

a(n) = (1/24)*n^2*(n^6+17*n^2+6). (Replace all x_i's in the cycle index with n.)

G.f.: x*(1+x)*(1+13*x+149*x^2+514*x^3+149*x^4+13*x^5+x^6)/(1-x)^9. - Colin Barker, Jan 29 2012

a(n) = 1*C(n,1) + 21*C(n,2) + 267*C(n,3) + 1718*C(n,4) + 5250*C(n,5) + 7980*C(n,6) + 5880*C(n,7) + 1680*C(n,8), where the coefficient of C(n,k) is the number of oriented colorings using exactly k colors.

a(n) = A128766(n) + A337896(n) = 2*A128766(n) - A337897(n) = 2*A337896(n) + A337897(n). - Robert A. Russell, Oct 08 2020

Extensions

Entry revised by N. J. A. Sloane, Jan 03 2005