# Questions tagged [necklace-and-bracelets]

In combinatorics, a *necklace* of length $n$ is an equivalence class of strings of length $n$, under rotation, so $abcde = bcdea$. A *bracelet* is an equivalence class of strings under rotation and reflection (so in addition $abcde = edcba$). [See Wikipedia](https://en.wikipedia.org/wiki/Necklace_(combinatorics)).

25 questions
89 views

### Counting Necklaces

Suppose we have a necklace with $n$ beads. Each bead is either red or blue. I'd like to ask how to count the number of necklaces $f(n,m,k)$ satisfying the following requirements: 1) There are exactly ...
31 views

### k-aray necklaces with fixed/conserved positions

I asked a question in a previous post about enumerating all possible k-ary bracelets with certain positions fixed to a specific bead/character. I asked a few mathematicians, and it seems its quite ...
Show that the number of monic irreducible polynomials of degree $n$ over a finite field of size $q$ is the same as the number of primitive necklaces of size $n$ with $q$ colors. I have the formula $$... 1answer 73 views ### Rotation of necklaces The number of fixed necklaces of length n with a types of beads is$$N(n,a)=\frac1n\sum_{d|n}\phi(d)a^{n/d}\;.$$It is clear intuitively that the number of rotational coincidences gets ... 0answers 73 views ### Approximation of products of necklaces Let's consider approximation of \prod_{p=1}^n N(p,a), n\to \infty, where the number of fixed necklaces of length n composed of a types of beads N(n,a): \frac {(a-1)^{n+1}} {(a-3) \cdot n!} \... 1answer 43 views ### unique bracelets from 6 beads, where 1 bead is a fixed color I'm trying to calculate the number of unique bracelets of length 6 that can be made from 11 differently colored beads. However there is one important key detail! Each bracelet has to contain ... 3answers 186 views ### unique necklace from 6 beads I'm trying to calculate the number of unique bracelets of length 6 that can be made from 6 differently colored beads. A same color bead can be repeated and used as many times as possible as the ... 1answer 54 views ### k-ary bracelets with conserved/fixed indexes Im using the formula from here: https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets to calculate the number of unique bracelets, accepting all rotation/mirroring as identical, ... 0answers 34 views ### Representation of limit of products of the fixed necklaces of length n composed of a types of beads I failed to find a way how to prove the limit and how to get the approximation below. Actually the formula and the comment were publised at MO with no clear explanations. In other words I'd like to ... 1answer 218 views ### Intuition Behind Necklace Formula Wikipedia and Wolfram MathWorld say that the formula for the number of distinct k-ary necklaces of length n is:$$ N_k(n) = \frac{1}{n}\sum_{d|n} {\phi(d)k^{n/d}} $$What is the intuition behind ... 1answer 19 views ### Prove that in a necklace consisting of kX blue beads and kY red beads, there exists a substring of length X + Y, with X blue beads. Prove that in a necklace consisting of kX blue beads and kY red beads, there exists a substring of length X + Y, with X blue beads and Y red beads. I found this claim while solving a ... 3answers 189 views ### Find the number of ways the 3 colored balls can be placed on vertices of a polygon without same color being adjacent and considered up to symmetry Give a generalized form [in the form of "n" i.e number of vertices of a polygon] of the number of combinations possible for 3 colored balls [infinite balls [it is not compulsory to use all the colors]]... 1answer 542 views ### Counting necklace with no adjacent beads are of the same color I've read that one can use the Polya enumeration theorem or the Burnside's lemma to count the number of necklaces using n beads from k colors. Can we then find a way to count the number of ... 0answers 51 views ### How many orientations are there of the cycle graph C_n I feel that this is a combinatorial question, I just don't know how to go about counting this. The way I'm thinking about it is you have a list of n numbers that are all 0 or 1. \{0,1,1,0,0,0...,1\... 4answers 478 views ### In how many ways can a necklace be made using 6 identical red beads and 2 identical blue beads? I got (8-1)! /2 \cdot 2! 6! But it's a decimal number… Also need to find the general formula that counts the total number of distinct necklaces made using n identical red beads and 2 identical ... 1answer 98 views ### Determining when two binary strings represent the same necklace or when one binary string is periodic An equivalence relation on binary strings calls two strings equivalent if one can be obtained from the other by a cyclic permutation of the characters. Combinatorialists call the equivalence classes ... 1answer 22 views ### Prove continuity of a function from S^n to \Bbb R^n Given an interval k-coloring of [0,1], define a function f: S^k \to \Bbb R^k as follows (S^k is the k-sphere). Let x = (x_1,x_2,...,x_{k+1}) be a point on the k-sphere S^k. Define z = ... 0answers 104 views ### Unique unclosed paths on torus grid Consider a grid of points in the shape of torus with in my case n=16 points around the toroidal direction and m=7 points around the poloidal direction. Now draw a line by starting at any grid ... 2answers 160 views ### Inequality involving number of binary Lyndon words of length n and n+1 Let f(n) be the number of binary Lyndon words of length n. This sequence is given by OEIS entry A001037. Is it true that 2f(n) \ge f(n+1) for all positive n? I have found a general formula ... 1answer 179 views ### Number of distinct necklaces using K colors I have a task to find the number of distinct necklaces using K colors. Two necklaces are considered to be distinct if one of the necklaces cannot be obtained from the second necklace by rotating ... 0answers 92 views ### Maps between combinatorial necklaces I am aware that the number of necklaces with m red beads and n white beads, where \gcd(m,n)=1, is equal to \frac{1}{m+n}\binom{m+n}{n}. For the problem I am trying to solve, I need to find a ... 1answer 278 views ### Burnside's lemma simple use Let's say that D_3 acts on a bracelet of 3 beads (Denote S), each bead can be Black or White. I want to count the number of different bracelets (4 - I believe) But using burnside's lemma I get ... 1answer 2k views ### Number of Necklaces of Beads in Two Colors I was reading this paper, and came across an equation which gives an expression for the number of necklaces of beads in two colors, with length n. Z_n = \dfrac{1}{n} \displaystyle \sum \limits_{d \... 2answers 146 views ### Lyndon Words, why isn't 00, 11 in the sequence. Im trying to understand the relationship between lyndon words and necklaces. The sequence for lyndon words is:$$ ε, 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111  ...
Six children ($a$ through $f$) are playing on a carousel with 6 seats such that $a$ is sitting in front of $d$, $b$ is sitting in front of $e$, and $c$ is sitting in front of $f$. How many ways are ...