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

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
2
votes
0answers
26 views

How many distinctively different necklaces are possible if you use 0 to 3 beads out of 5 different beads given? [closed]

Today in my IB Math II HL/AP Calculus BC class we were going over IB Math I topics and did the given problem. So you would calculate the number of necklaces for a 0, 1, 2, and 3 bead necklace. I used $...
2
votes
2answers
105 views

Necklace problem with Burnside Lemma

How many necklaces can be made with two red beads, two green beads, and four violet beads?(8 total) Using Burnside lemma is complicated for me due to my lack of understanding of the lemma. I want to ...
1
vote
1answer
50 views

Circular and Reflectional Symmetry

If you have two types of objects, $a$, and $b$. You have $n_1$ of the first object, $n_2$ of the second object. How many distinct ways can you rearrange these objects on a ring. Arrangements are only ...
0
votes
2answers
85 views

A necklace is made up of 3 beads of one color and 6 beads of another color

A necklace is made up of 3 beads of one color and 6 beads of another color beads of same color are identical the number of necklace that are possible ? I have attempted the question in this way : ...
3
votes
3answers
80 views

$n-$circular arrangement problem

Find the number of ways to arrange $n$ people in a circle so that $3$ people are separated. My approach: The number of ways to arrange $n$ people in a circle is $(n - 1)!$. If the $3$ people are ...
0
votes
1answer
68 views

“bracelet type” Combinatorics

This question seems ok but I'm having real difficultly working out the answer using the method they provided. It's so hard to keep track of all the options. Does anyone know of a better more algebraic ...
0
votes
2answers
126 views

Circular permutations of identical objects of two kinds.

A necklace is made up of $3$ beads of one sort and $6n$ of another, those of each sort being similar. Show that the number of arrangement of the beads is $3n^2+3n +1$. My attempt: There are total $...
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
4
votes
1answer
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 ...
0
votes
0answers
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 ...
4
votes
0answers
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)$-...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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. ...
4
votes
0answers
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$; (...
2
votes
0answers
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 "...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
2answers
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 ...
5
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
0answers
72 views

Show COMBINATORIALLY the number of irreducible monic polynomials is the number of primitive necklaces

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 $$...
3
votes
1answer
131 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 ...
1
vote
3answers
225 views

(Music) List of all possible “types of set” of 12 musical notes

I have looked into trying to figure what are all the possible "types" of note set combinations there are and how I would go by listing them if possible. It turns out this is harder than I thought. The ...
2
votes
0answers
96 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!} \...
1
vote
1answer
67 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 ...
3
votes
3answers
943 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 ...
2
votes
1answer
90 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, ...
1
vote
0answers
39 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 ...
4
votes
1answer
284 views

How many number of bracelets of length $n$ with black-white beads?

How many number of bracelets of length $n$ with black-white beads? I'm trying to find a formula for counting the number of such bracelets. What i've done so far is to think of the bracelets as binary ...
6
votes
1answer
350 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 ...
0
votes
1answer
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 ...
2
votes
3answers
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]]...
4
votes
1answer
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 ...
1
vote
0answers
58 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\...
0
votes
4answers
948 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 ...
0
votes
1answer
162 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 ...
1
vote
1answer
26 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 = ...
1
vote
0answers
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 ...
6
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
2
votes
1answer
343 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 ...
4
votes
1answer
4k 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 \...