Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
1answer
30 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
35 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
68 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 ...
2
votes
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!} \...
1
vote
1answer
38 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 ...
4
votes
3answers
155 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
52 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
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 ...
6
votes
1answer
200 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
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 ...
2
votes
3answers
178 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]]...
3
votes
1answer
501 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
49 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
449 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
91 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
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 = ...
1
vote
0answers
103 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 ...
5
votes
2answers
153 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
172 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 ...
1
vote
0answers
88 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
269 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 ...
3
votes
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 \...
3
votes
2answers
142 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 $$ ...
0
votes
1answer
231 views

Combinatorics question - How many different ways to change sitting order

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