Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

Counting patterns with a given automorphism group


Author: Dennis E. White
Journal: Proc. Amer. Math. Soc. 47 (1975), 41-44
DOI: https://doi.org/10.1090/S0002-9939-1975-0349408-9
Erratum: Proc. Amer. Math. Soc. 50 (1975), 504.
MathSciNet review: 0349408
Full-text PDF Free Access

Abstract | References | Additional Information

Abstract: A formula, analogous to the classical Burnside lemma, is developed which counts orbit representatives from a set under a group action with a given stabilizer subgroup conjugate class. This formula is applied in a manner analogous to a proof of Pólya's theorem to obtain an enumeration of patterns with a given automorphism group.


References [Enhancements On Off] (What's this?)

  • [1] W. Burnside, Theory of groups of finite order, Dover Publications, Inc., New York, 1955. 2d ed. MR 0069818
  • [2] N. G. de Bruijn, ``Pólya's theory of counting,'' in E. F. Beckenbach, Applied combinatorial mathematics, Wiley, New York, 1964. MR 30 #4687.
  • [3] H. O. Foulkes, On Redfield’s range-correspondences, Canad. J. Math. 18 (1966), 1060–1071. MR 0200188, https://doi.org/10.4153/CJM-1966-105-5
  • [4] A. Garsia, A presentation of the enumeration theory of Pólya and de Bruijn, Analysis seminar notes, University of California, San Diego, Calif., 1971.
  • [5] G. Pólya, Kombinatoris che Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145-254.
  • [6] J. Howard Redfield, The Theory of Group-Reduced Distributions, Amer. J. Math. 49 (1927), no. 3, 433–455. MR 1506633, https://doi.org/10.2307/2370675
  • [7] J. Sheehan, The number of graphs with a given automorphism group, Canad. J. Math. 20 (1968), 1068–1076. MR 0232708, https://doi.org/10.4153/CJM-1968-103-x
  • [8] P. K. Stockmeyer, Enumeration of graphs with prescribed automorphism group, Ph. D. Thesis, University of Michigan, Ann Arbor, Mich., 1971.
  • [9] D. E. White, Multilinear techniques in enumeration and list generation, Ph. D. Thesis, University of California, San Diego, Calif., 1973.
  • [10] S. G. Williamson, Isomorph rejection and a theorem of de Bruijn, SIAM J. Comput. 2 (1973), 44–59. MR 0335278, https://doi.org/10.1137/0202006


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1975-0349408-9
Keywords: Orbit, stabilizer subgroup, conjugate subgroup, mark, pattern inventory, Möbius function
Article copyright: © Copyright 1975 American Mathematical Society