Balancing the n-Cube: A Census of Colorings
E.M. Palmer
, R.C. Read
and R.W. Robinson
DOI: 10.1023/A:1022487918212
Abstract
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.
Pages: 257–273
Keywords: $n$-cube; Boolean function; Pólya enumeration; superposition
Full Text: PDF
References
1. W.K. Clifford, "On the types of compound statement involving four classes," Mem. Lit. Philos. Soc. Manchester 16 (1877), 88-101.
2. F. Harary and E.M. Palmer, Graphical Enumeration, Academic Press, New York, 1973.
3. M.A. Harrison, "The number of transitivity sets of Boolean functions," SIAM J. Appl. Math. 11 (1963), 806-828.
4. M.A. Harrison and R.G. High, "On the cycle index of a product of permutation groups," J. Combin. Theory 4 (1968), 277-299.
5. W.S. Jevons, The Principles of Science, 2nd ed., Macmillan, London, 1877; reprinted, Dover, New York, 1958.
6. E.M. Palmer and R.W. Robinson, "Enumeration under two representations of the wreath product," Acta Math. 131 (1973), 123-143.
7. E.M. Palmer and R.W. Robinson, "Enumeration of self-dual configurations," Pacific J. Math. 110 (1984), 203-221.
8. G. P61ya, "Sur les types des propositions composees,"
7. Symbolic Logic 5 (1940), 98-103.
9. R.C. Read, "The enumeration of locally restricted graphs I,"
7. London Math. Soc. 34 (1959), 417.-436; "The enumeration of locally restricted graphs II," 35 (1960), 334-351.
10. J.H. Redfield, "The theory of group-reduced distributions," Amer. J. Math. 49 (1927), 433-455.
11. D. Slepian, "On the number of symmetry types of Boolean functions of n variables," Canad. J. Math. S (1953), 185-193.
2. F. Harary and E.M. Palmer, Graphical Enumeration, Academic Press, New York, 1973.
3. M.A. Harrison, "The number of transitivity sets of Boolean functions," SIAM J. Appl. Math. 11 (1963), 806-828.
4. M.A. Harrison and R.G. High, "On the cycle index of a product of permutation groups," J. Combin. Theory 4 (1968), 277-299.
5. W.S. Jevons, The Principles of Science, 2nd ed., Macmillan, London, 1877; reprinted, Dover, New York, 1958.
6. E.M. Palmer and R.W. Robinson, "Enumeration under two representations of the wreath product," Acta Math. 131 (1973), 123-143.
7. E.M. Palmer and R.W. Robinson, "Enumeration of self-dual configurations," Pacific J. Math. 110 (1984), 203-221.
8. G. P61ya, "Sur les types des propositions composees,"
7. Symbolic Logic 5 (1940), 98-103.
9. R.C. Read, "The enumeration of locally restricted graphs I,"
7. London Math. Soc. 34 (1959), 417.-436; "The enumeration of locally restricted graphs II," 35 (1960), 334-351.
10. J.H. Redfield, "The theory of group-reduced distributions," Amer. J. Math. 49 (1927), 433-455.
11. D. Slepian, "On the number of symmetry types of Boolean functions of n variables," Canad. J. Math. S (1953), 185-193.