Enumeration of integer k-gons with perimeter n

K. Atanassov, S. Dantchev and A. Shannon
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 6, 2000, Number 3, Pages 88–99
Full paper (PDF, 593 Kb)

Details

Authors and affiliations

K. Atanassov
Centre for Biomedical Engineering – Bulgarian Academy of Sciences,
Acad. G. Bonchev Str., Bl. 105, Sofia-1113, Bulgaria

S. Dantchev
BRICS – Basic Research in Computer Science, Centre of the Danish National Research
Foundation, Department of Computer Science, University of Aarhus, Ny Munkegade, building
540, DK – 8000 Arhus C, Denmark

A. Shannon
Warrane College, The University of New South Wales, 1465, & KvB Institute of Technology, North Sydney, 2060, Australia

Abstract

We consider the following enumeration problem: how many are there “distinct” k-gons with integer sides and perimeter n. A solution is known for k = 3 when “distinct” means “non-congruent”. This does not hold in the general case since for k > 3 a k-gon is not uniquely determined by its side lengths. We define the concept “distinct” in an appropriate way and reduce the problem to an enumeration of all distinct integer labels on the sides of a fixed regular k-gone satisfying a given condition. This enumeration can be done by the well known Polya’s Theory of Counting. The simple structure of the considered objects (a regular k-gon and the dihedral group of order k) allows us to prove our results in an alternative way using only elementary concepts and techniques from Group Theory and Number Theory.

References

  1. N. G. DE BRUJN, survey of yen eraliztio ns of Polya’s enumeration theorem, Nieuv Archief voor Wiskunde, (2), 19 (1971), pp.89-112.
  2. N. G. DE BRUJN, Polya’s Theory of Counting, ch. 5 in Applied Combinatorial Mathematics, E. F. Beckenbach, ed. (1964), pp. 144-184.
  3. P. J. CAMERON, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.
  4. C. W. CURTIS and I. REINER, Representation theory of finite groups and associative algebras, Interscience Publishers, a division of John Wiley & Sons, New York, London, 1962.
  5. J. JORDAN, R. WALCH and W. WISNER, Triangles with integer sides, Amer. Math. Monthly, (8), 86 (1979), pp. 686-689.
  6. G. POLYA, Kombinatorishe Anzahlbestimmugen fur Gruppen, Graphen und chemische Verbindungen, Acta Mathematica, 68 (1937), pp. 145-254.

Related papers

Cite this paper

Atanassov, K., Dantchev, S. & Shannon, A. (2000). Enumeration of integer k-gons with perimeter n. Notes on Number Theory and Discrete Mathematics, 6(3), 88-99.

Comments are closed.