# 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$).

53 questions
Filter by
Sorted by
Tagged with
18 views

### Beads on a necklace but they’re all the same colour

Okay, so I know that if 15 beads, 5 red, 5 yellow, 5 blue, the number of possible combinations is: 14! / 2*5!*5!*5! But say all 15 were of the same colour. (the answer is obviously 1). But wouldn’t ...
26 views

66 views

### Burnside Lemma Necklace

I'm trying to solve this problem for 4-6-8 necklace. So far I am at the following: $\frac{18!}{4!6!8!}$ (different arrangements) + $\frac{9!}{2!3!4!}$ (rotating through 180 degrees). Now I consider ...
89 views

### How many different circular bracelets can be formed from 8 red, 6 blue and 4 yellow beads, always using all available beads?

How many different bracelets can be made from 8 red, 6 blue and 4 yellow beads, always using all available beads? Two bracelets are different when we cannot get the color scheme of the beads of one ...
204 views

### Necklace combinations with three group of beads

I have a hard question about a way how many different necklaces can be made. Suppose that we have the following restrictions: We have 3 groups of beads: 4 triangle beads 6 square beads 8 circle ...
53 views

### Consider all necklaces that you can create using 17 beads, where the beads are colored red or blue.

Let us represent the color pattern as a string of 17 Rs and Bs; for example, RBRRBBBRBRRBRBBBR Now, if we rotate the necklace “one to the right”, we get the color pattern BRRBBBRBRRBRBBBRR, which ...
47 views

### Correspondence between $k$-ary Lyndon words and $(k-1)$-ary Lyndon words without repetitions

At Counting Lyndon words with no adjacent character repeats, it turned out that for $n\ge3$ the number of $k$-ary Lyndon words of length $n$ without adjacent identical letters is the number of $(k-1)$-...
51 views

### Counting Lyndon words with no adjacent character repeats

I'm interested in counting aperiodic words in bracelets. I know that corresponds to Lyndon words, and I know how to count the number of Lyndon words for an $(n, k)$ bracelet using Moreau's necklace ...
45 views

### How to count necklaces with this additional requirement?

I've recently dug into the idea of necklaces for a project I'm working on, and it's almost exactly what I'm looking for. The way I understand it, the general necklace-counting function is essentially ...
54 views

### Count of bracelets with no adjacent colours the same

I already know how to calculate the amount of bracelets of length $n$ and $k$ colours. I'd like to add a condition: only count bracelets with no adjacent colours the same. For context, this is a ...
43 views

### Count distinct possible words without rotations or reflections

Suppose I have an alphabet ${\{A, B, C, D\}}$ and I want to count all possible words of length $n$. Easy: it's $4^n$. What should I do if I want to count all possible words that: a) are unique given ...
26 views

### Terminology of an equivalence class of necklaces given by permuting the alphabet (or “colors”)

A necklace is the rotationally-equivalent version of a word on an alphabet. As an example, the two words "$aabaaab$" and "$abaaaba$" are rotations of one another, and represent the same necklace. ...
74 views

### Necklace infinte sum

Consider the function: $$S(n)=\sum_{j=1}^{\infty}\frac{j^n}{2^j}=\frac1 2+\frac{2^n}{4}+\frac{3^n}{8}+\frac{4^n}{16}+\frac{5^n}{32}+...$$ Euler found the sum of the first few of these as: $S(0)=1$; (...
61 views

### Longest run of heads if coins are arranged in a circle?

There are many questions and answers throughout concerning longest run of heads after $n$ flips of a fair coin. For example, this question has multiple detailed answers. A good reference listed was "...
36 views

### On the co-primality of bracelet-type numbers

Doing some related research (more info in a past question), I've stumbled upon this interesting problem which I cannot seem to solve myself: Let an integer $N$ be the number of digits imprinted on a ...
38 views

### On the co-primality of bracelet-type binary numbers

Let an integer N be the number of digits imprinted on a bracelet, which can come in two values, 1 and 0. You can produce a binary number by writing down the 1's and 0's on the bracelet from left to ...
189 views

### Number of $n$-bead binary necklaces [OEIS-A000013]

I tried to obtain the number of $n$-bead binary necklaces from my program written in C++. Then, one formula came up when I looked up the number to see if my thought is correct. Number of $n$-bead ...
162 views

### Number of Bracelets with 6 white, 3 blue, and 5 red beads

Six identical white beads, three identical blue beads, and five identical red beads are to be strung together to create a bracelet. If the beads are free to move all the way around the bracelet, how ...
674 views

### Number of different necklaces with $2$ black and $6$ white beads

This is not a home work question, I'm preparing for an entrance test. The number of different necklaces you can form with $2$ black and $6$ white beads is? My approach: We can place the white ...
270 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 ...
53 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 ...
72 views

22 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 ...
456 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]]...
1k 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 ...
58 views

139 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 ...
169 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 ...
311 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 ...
123 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 ...
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 ...