Skip to main content

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
3 votes
1 answer
133 views

Orientable necklaces and complements

I'm trying to understand the OEIS sequence A059078: Number of orientable necklaces with 2n beads and two colors which when turned over produce their own color complement. 0, 0, 0, 1, 2, 6, 12, 27, 54,...
Throckmorton's user avatar
3 votes
1 answer
88 views

Necklace with 4p beads (Burnside's lemma)

Let $p \geq 3$ be a prime number. We consider $2p$ black beads and $2p$ blue beads (both indistinguishable). How many unique necklaces of size $4p$, created from these beads, are there? (Consider only ...
Umbra's user avatar
  • 55
0 votes
0 answers
65 views

Individual contribution of string-length counts in polygons drawn on a clock face

Background In a psychology experiment we had people interact with various 5-sided polygons drawn on the face of a clock (the specifics of the experiment are not pertinent to the question at hand). For ...
Michael Seltenreich's user avatar
1 vote
1 answer
47 views

Given one has a cyclic code, how would you deduplicate the other orientations of the codeword in a systematic way?

I've been recently working with Reed-Solomon codes and wanted to make use of their cyclic properties to uniquely identify something regardless of where the reading of the code started symbol-wise. Is ...
Curtis's user avatar
  • 13
0 votes
0 answers
79 views

Simple way to approach bead necklaces problem for equal number of beads

I was recently given this question on a practice test, and it was intended to be completed in ~2-3 minutes, for someone with intermediate stats/math knowledge: For a positive integer $n$, you have $n$...
bluesquare's user avatar
3 votes
3 answers
210 views

Number of colourings of the necklace.

I want to count the number of ways to color beads of a necklace green and red, such that two adjacent beads cannot both be red. The necklace cannot be turned or reflected, the beads are labelled. ...
Michał's user avatar
  • 675
0 votes
0 answers
61 views

Counting number of bracelet configurations

Suppose we have $3$ red beads and $3$ green beads. How many different bracelets can we make from this? Initially I thought this was a standard circular permutation but I am getting a non integer ...
shrizzy's user avatar
  • 754
2 votes
1 answer
99 views

Enumerative combinatorics. Number of unique сhords

Have: Circle N * 2 equidistant points on circle N chords connecting points into pairs Exactly 1 chord connected to each points Additional conditions: Points are equivalent, so a1a2 = a2a1, aabbccdd ...
pavdan's user avatar
  • 23
0 votes
1 answer
76 views

To find the number of ways to choose $3$ vertices up to rotation from $8$ cycle.

Suppose we have a cycle graph on $8$ vertices. To find the number of ways to choose $3$ vertices up to rotation. Note that we can choose $3$ vertices from $8$ vertices in $C(8,3) = 56$ ways. But many ...
user5210's user avatar
  • 399
2 votes
1 answer
54 views

Different possibilities of arranging perls in a chain using a group action or combinatorial argument

We want to build chains of $6$ perls. The perls are provided in $n$ colors: $n_1, n_2, \dotsc, n_n$. We call two such a chains essentially different, if after a rotation by $180^°$ the chains are ...
user249018's user avatar
  • 1,490
0 votes
0 answers
87 views

Algorithm for getting all 2D necklaces

Let's assume that we work in the finite field of two elements, $\{0, 1\}$. We want for example to construct all the necklaces of length $N = 3$. Thus, from the full set of ALL PERMUTATIONS (edit:to be ...
Kostas's user avatar
  • 31
1 vote
1 answer
107 views

Bracelet enumeration

Apologies if this has been asked and answered but I can't seem to find a solution! I am looking for a way to enumerate or list all of the bracelets for a given number of beads, without repetition of ...
Rory's user avatar
  • 11
1 vote
2 answers
126 views

Arrangements of three types of beads around a circle so that no two beads of the same color are adjacent

Suppose you have beads with colors and numbers on them. There are 8 colored white, 6 colored black, and 3 colored red. The white are numbered 1 to 8, the black numbered 1 to 6, and the red numbered ...
Addem's user avatar
  • 5,706
1 vote
1 answer
314 views

Number of different necklaces with $4$ beads, s.t. W$\ge$ B$\ge $ R.

It is stated that to form a 4-beads necklace with white, black, and red beads, s.t. $W \ge B \ge R,$ where the number of white, black, and red beads is denoted by W, B, and R respectively. The text is ...
jiten's user avatar
  • 4,524
2 votes
0 answers
381 views

How many different necklaces can we construct?

Problem: We construct a necklace using 7 green and 9 red beads. How many different necklaces can we construct? Necklaces that can be rotated to each other are considered to be the same. My answer: $\...
Ungar Linski's user avatar
8 votes
2 answers
155 views

Does every sufficiently long string contain consecutive permutations of another string?

Let $\mathcal{C}$ be a finite set, let $\mathcal{F}(\mathcal{C})$ be the free (non-abelian) monoid over $\mathcal{C}$, and let $n\in\mathbb{N}$ be an integer. For every $k\in \mathbb{N}$, write $S_k$ ...
Some Math Student's user avatar
3 votes
2 answers
5k views

How many necklaces can be formed with $6$ identical diamonds and $3$ identical pearls

Find number of ways to make a necklace (or a garland) consisting of $6$ identical diamonds and $3$ identical pearls. I got the correct answer $7$ by taking different cases but when I applied the ...
Maverick's user avatar
  • 9,463
2 votes
1 answer
235 views

How many necklaces made of black and white beads (k total, x black) have at least y consecutive black beads?

Consider all necklaces consisting of black and white beads, of length k, containing x black beads. How many such necklaces contain y consecutive black beads somewhere in the necklace? (y is less than ...
kevincrawfordknight's user avatar
1 vote
3 answers
171 views

Quantifying the evenness-of-distribution of nodes within a necklace

Given a necklace with n nodes that are distributed around a circle by a set of given deltas: How would you quantify how evenly the nodes are distributed. (By "evenly" I mean that each node ...
Michael Seltenreich's user avatar
3 votes
1 answer
676 views

How many necklaces with given certain colored beads

I am interested to know if there's a way to calculate the number of (rotation agnostic) necklaces that can be produced from different colored beads, each color with its own quantity. For instance, if ...
Michael Seltenreich's user avatar
1 vote
1 answer
499 views

How many necklaces are there with a known number of beads of each color? [duplicate]

I suspect that the answer to my question might be trivially found in the Wikipedia page for the combinatorial concept of a necklace, but I'm finding that page very hard to understand. Suppose I have $...
tparker's user avatar
  • 6,239
-1 votes
1 answer
259 views

Number of different seven-bead necklaces with 4 colored beads [closed]

How many different seven-bead necklaces are possible, assuming each bead is one of four different colors and each necklace contains exactly one bead of one color and exactly two beads of the three ...
zzzzz's user avatar
  • 119
3 votes
0 answers
171 views

How many different circular necklaces containing ten beads can be made using beads of at most two colors?

How many different circular necklaces containing ten beads can be made using beads of at most two colors? I know I need calculate situation with 2 colors, 8 second color, 3 first color, 7 second ...
rrryok's user avatar
  • 51
2 votes
0 answers
175 views

Find the number of different types of circular necklaces that could be made from the sets of beads

Find the number of different types of circular necklaces that could be made from the sets of beads 7 black and 5 white beads We need to solve this by the Polya-Burnside method of enumeration: Since ...
Amir Zhang's user avatar
4 votes
2 answers
2k views

Number of ways to arrange objects in a circle, some of which may be identical

I know that the number of ways to arrange $n$ distinct objects in a circle in $(n-1)!$ from Circular Permutation. But suppose we have $n_1$ identical objects of Type $1$, $n_2$ identical objects of ...
Henry's user avatar
  • 5,599
5 votes
1 answer
150 views

Using burnside's lemma to calculate a smaller subset of unique, color-agnostic bracelets

We have a child's toy, which is a ball made of 12 colored wedges (3 Red, 3 Green, 3 Blue, 3 Yellow). Our child asked the sensible question 'how many different patterns are possible?'. In researching ...
Granny's user avatar
  • 53
4 votes
1 answer
91 views

Finding "beautiful" necklaces with regular gaps

I am looking for "beautiful" arrangements of $k$-ary necklaces of length $ak$ where each of the $k$ types of bead appears $a$ times ($a \geq 1$ a natural number). A necklace is considered ...
badroit's user avatar
  • 506
1 vote
1 answer
71 views

Interpretation of combinatorial identity involving binomial coefficients

I proved that for some positive integers $n$, $k\leq n-1$ and $l\leq k$ the following identity is satisfied. $$\binom{k-1}{l-1}\binom{n-k-1}{l-1}\dfrac{n}{l} = \binom{k}{l}\binom{n-k-1}{l-1} +\binom{k-...
Jfischer's user avatar
  • 1,271
3 votes
1 answer
266 views

Combinatorial Necklaces & Strips of $n$ Beads and $k$ Colours

Say I have $n$ indistinguishable beads and $k$ different colours. Suppose here and for the rest of the writeup that $k \mid n$ unless otherwise stated. I want to colour all the $n$ beads using exactly ...
MC From Scratch's user avatar
1 vote
1 answer
226 views

Number of necklaces given 3 beads that can take 4 colours

Find thee number of necklaces given 3 beads that can take 4 colours, two necklaces are considered the same if the colours can be matched by rotation or flipping them. My approach is by using Burnside'...
doremifa3310's user avatar
1 vote
1 answer
139 views

Burnside's Lemma necklace with a clasp

How many necklaces with clasps can be made with 6 beads in one colour, 4 in second and 3 in the third? Use Burnside's Lemma I've got: Let $X=\{\text{necklaces of length 13 beads = 6 white, 4 black and ...
Patrycja's user avatar
  • 151
3 votes
1 answer
297 views

Burnside's Lemma bracelet with beads in 2 colours (uneven cardinality)

How many bracelets can be made with 5 beads in one colour and nine in the other (rotated and flipped bracelets are considered the same). I'm trying to use Burnside's Lemma yet I'm little confused. So ...
Patrycja's user avatar
  • 151
0 votes
1 answer
41 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 ...
Subbota's user avatar
  • 368
2 votes
0 answers
121 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 $...
user avatar
3 votes
2 answers
1k 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 ...
wormname's user avatar
1 vote
1 answer
87 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 ...
atul ganju's user avatar
1 vote
2 answers
1k 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 : ...
victor's user avatar
  • 105
3 votes
3 answers
439 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 ...
DYBnor's user avatar
  • 357
0 votes
1 answer
753 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 ...
user avatar
0 votes
2 answers
1k 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 $...
SarGe's user avatar
  • 3,020
-1 votes
1 answer
161 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 ...
Kradec na kysmet's user avatar
1 vote
1 answer
355 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 ...
Ivan Ivanov's user avatar
4 votes
1 answer
695 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 ...
Mathematicha's user avatar
4 votes
0 answers
76 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)$-...
joriki's user avatar
  • 239k
4 votes
1 answer
126 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 ...
occulus's user avatar
  • 279
2 votes
1 answer
151 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 ...
QuaternionsRock's user avatar
2 votes
1 answer
346 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 ...
occulus's user avatar
  • 279
0 votes
1 answer
121 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 ...
occulus's user avatar
  • 279
2 votes
1 answer
65 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. ...
Mike Battaglia's user avatar
5 votes
0 answers
199 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$; (...
Dottard's user avatar
  • 161