Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-17T14:18:21.014Z Has data issue: false hasContentIssue false
  • English
  • Français

COUNTING SYMMETRIC BRACELETS

Part of: Elementary number theory Graph theory Combinatorics

Published online by Cambridge University Press:  22 August 2013

YEVHEN ZELENYUK  and
YULIYA ZELENYUK
YEVHEN ZELENYUK*
Affiliation:
School of Mathematics, University of the Witwatersrand, Private Bag 3, Wits, 2050, Johannesburg, South Africa email [email protected]
YULIYA ZELENYUK
Affiliation:
School of Mathematics, University of the Witwatersrand, Private Bag 3, Wits, 2050, Johannesburg, South Africa email [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

An $r$-ary necklace (bracelet) of length $n$ is an equivalence class of $r$-colourings of vertices of a regular $n$-gon, taking all rotations (rotations and reflections) as equivalent. A necklace (bracelet) is symmetric if a corresponding colouring is invariant under some reflection. We show that the number of symmetric $r$-ary necklaces (bracelets) of length $n$ is $\frac{1}{2} (r+ 1){r}^{n/ 2} $ if $n$ is even, and ${r}^{(n+ 1)/ 2} $ if $n$ is odd.

Keywords

necklacebraceletsymmetrycolouringfinite cyclic groupdihedral group

MSC classification

Secondary: 05A15: Exact enumeration problems, generating functions 05C15: Coloring of graphs and hypergraphs 05C25: Graphs and abstract algebra (groups, rings, fields, etc.) 11A25: Arithmetic functions; related numbers; inversion formulas
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 89 , Issue 3 , June 2014 , pp. 431 - 436
Copyright
Copyright ©2013 Australian Mathematical Publishing Association Inc. 

References

Aigner, M., Combinatorial Theory (Springer, Berlin–Heidelberg–New York, 1979).Google Scholar
Bender, E. and Goldman, J., ‘On the applications of Möbius inversion in combinatorial analysis’, Amer. Math. Monthly 82 (1975), 789–803.Google Scholar
Gryshko, Y., ‘Symmetric colourings of regular polygons’, Ars Combin. 78 (2006), 277–281.Google Scholar
Gryshko, Y. and Protasov, I., ‘Symmetric colourings of finite Abelian groups’, Dopov. Akad. Nauk Ukr. (2000), 32–33.Google Scholar