Balancing the $n$-cube: A census of colorings

Palmer, E.M. ; Read, R.C. ; Robinson, R.W.

Journal of Algebraic Combinatorics, Tome 1 (1992) no. 3, pp. 257-273.

Résumé

Summary: Weights of 1 or 0 are assigned to the vertices of the $n$-cube in $n$-dimensional Euclidean space. Such an $n$-cube is called $balanced$ if its center of mass coincides precisely with its geometric center. The seldom-used $n$-variable form of Pólya's enumeration theorem is applied to express the number $N _{ n, 2 k }$ of balanced configurations with $2 k$ vertices of weight 1 in terms of certain partitions of $2 k$. A system of linear equations of Vandermonde type is obtained, from which recurrence relations are derived which are computationally efficient for fixed $k$. It is shown how the numbers $N _{ n, 2 k }$ depend on the numbers $A _{ n, 2 k }$ of specially restricted configurations. A table of values of $N _{ n, 2 k }$ and $A _{ n, 2 k }$ is provided for $n = 3, 4, 5$, and 6. The case in which arbitrary, nonnegative, integral weights are allowed is also treated. Finally, alternative derivations of the main results are developed from the perspective of superposition.

Détail

Keywords: $n$-cube, Boolean function, Pólya enumeration, superposition