Balancing the \(n\)-cube: A census of colorings (Q686003): Difference between revisions

Let \(V=\bigl\{ (\alpha_ 1,\ldots,\alpha_ n): \alpha_ i \in\{- 1,1\}\), \(i=1,\ldots,n \bigr\}\) be the set of vertices of the geometric \(n\)-cube in \(n\)-dimensional Euclidean space. Two vertices are adjacent if they differ in exactly one coordinate (thus the distance between them is 2). A 2-coloring of \(V\) is a function \(f\) from \(V\) into the set \(\{0,1\}\) (0=white, 1=black). The center of mass of a coloring \(f\) \((f\neq 0)\) is the point whose coordinates are given by \({1 \over w(f)} \sum (\alpha_ 1,\ldots,\alpha_ n)\), where the sum is over all black vertices, \(w(f)\) is the number of black vertices for coloring \(f\). A coloring is balanced if its center of mass is the origin. So no coloring \(f\) with \(w(f)\) an odd number can be balanced. Two vertices \(v\) and \(-v\) are said to be antipodal. A coloring is antipodal if every two antipodal vertices are assigned the same color; so the antipodal colorings are balanced. A coloring is antiantipodal (with respect to black) if it is balanced and contains no antipodal pair of black vertices. Let \(N_{n,2k}\) be the number of balanced colorings of \(n\)-cube with exactly \(2k\) black vertices and \(A_{n,2k}\) be the number of balanced colorings with \(2k\) black vertices but no antipodal pair of black (i.e. antiantipodal colorings). Some \(n\)-variable form of Pólya's enumeration theorem is applied to express \(N_{n,2k}\) in terms of certain partitions of \(2k\). Also the authors proved: \(A_{n,2k}=0\) for \(n \geq 3\) and \(k=1\) or \(k=2^{n-2}- 1\), and \(A_{n,2k}=N_{n-1,k}\) for \(n \geq 2\) and \(k=2^{n-2}\). A table of values of \(N_{n,2k}\) and \(A_{n,2k}\) is provided for \(n=3,4,5,6\).