login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A203399 T(n, k), a triangular array read by rows, is the number of classes of equivalent 2-color n-bead necklaces (turning over is allowed) that contain k necklaces. 3
2, 0, 2, 1, 0, 0, 2, 0, 2, 0, 0, 0, 2, 1, 0, 3, 0, 0, 0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 0, 0, 2, 1, 2, 0, 0, 7, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 2, 2, 1, 0, 3, 0, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0, 6, 2, 0, 2, 0, 0, 0, 0, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 14, 2, 1, 0, 0, 6, 0, 0, 0, 0, 39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Equivalently, the dihedral group of order n acts on the set of length n binary sequences. T(n,k) is the number of orbits that contain k elements.

By "n-bead necklaces (turning over is allowed)" the author means "bracelets". By saying that the classes of these n-bead bracelets (turnover necklaces) "contain k necklaces" the author means that the classes "contain k marked necklaces". - Petros Hadjicostas, Jun 06 2019

LINKS

Petros Hadjicostas, Table of n, a(n) for n = 1..210, flattened.

Petros Hadjicostas, Formulas for chiral bracelets, 2019.

S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, Generating bracelets with fixed content, 2011.

S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

Frank Ruskey, Combinatorial Generation Algorithm Algorithm 4.24, p. 95.

Joe Sawada, Generating bracelets in constant amortized time, SIAM J. Comput. 31 (2001), 259-268.

R. M. Thompson and R. T. Downs, Systematic generation of all nonequivalent closest packed stacking sequences of length Nusing group theory, Acta Cryst. B57 (2001), 766-771; B58 (2002), 153.

FORMULA

From Petros Hadjicostas, Jun 06 2019:

Conjectures: For n >= 1, let b(n) be the number of bracelets of two colors with n beads that are either periodic (period >= 2), or have reflection symmetry (achiral), or both. Then b(n) = A000029(n) - A032239(n) for n >= 3 with b(n) = A000029(n) for n = 1, 2. We have A000029(n) = 2^floor(-3 + n/2) * (7 - (-1)^n) + (1/(2*n)) * Sum_{d|n} phi(d) * 2^(n/d) for n >= 1 and A032239(n) = (1/2) * Sum_{d|n} mu(d) * (-2^floor(-2 + (n/(2*d))) * (7 - (-1)^(n/d)) + 2^(n/d)/n) for n >= 3.

For 1 <= k <= n, we conjecture that T(n, k) = Sum_{d|k} mu(d)*b(k/d) for k|n, and = 0 otherwise. Note that, if 3 <= n <= 11, we have T(n, k) = A056493(k) when k|n, but this is not true (for example) for n = 12 and n = 14. We have T(12, 12) = 82 <> 81 = A056493(12) and T(14, 14) = 177 <> 175 = A056493(14).

Apparently, T(n, 2*n) =  A032239(n) for all n >= 3, and T(n, k) = 0 for n < k < 2*n.

(End)

From Petros Hadjicostas, Jun 16 2019: (Start)

I ran the author's Mathematica program for n = 1..21 and I saw that the conjecture is OK except for n = 18 and n = 21. The program gives T(n=18, k=12) = 1 and T(n=18, k=18) = 742 while my conjecture implies that T(n=18, k=12) = 0 (since k = 12 does not divide n = 18) and T(n=18, k=18) = 743. In addition, the program gives T(n=21, k=14) = 2 and T(n=21, k=21) = 2030, while my conjecture implies that T(n=21, k=14) = 0 (since k = 14 does not divide n = 21) and T(n=21, k=21) = 2032. Apparently, my conjecture needs to be refined.

For n = 18, the single bracelet whose equivalence class has 12 marked necklaces is (BBWBWW)^3 (with period 3).

For n = 21, the two bracelets whose equivalence classes have 14 marked necklaces each are (BBWBWWW)^3 and (WWBWBBB)^3 (each with period 3).

(End)

EXAMPLE

Triangle begins (with rows n >= 1 and columns k >= 1):

  2  0

  2  1  0  0

  2  0  2  0  0  0

  2  1  0  3  0  0  0  0

  2  0  0  0  6  0  0  0  0  0

  2  1  2  0  0  7  0  0  0  0  0  1

  2  0  0  0  0  0 14  0  0  0  0  0  0  2

  2  1  0  3  0  0  0 18  0  0  0  0  0  0  0  6

  2  0  2  0  0  0  0  0 28  0  0  0  0  0  0  0  0 14

From Petros Hadjicostas, Jun 07 2019: (Start)

Consider all bracelets (turnover necklaces) of two colors (B and W) that can be generated using one of Ruskey's websites above. We keep his numbering, declare whether it has reflexive symmetry or not (achiral or chiral, resp.), and find its value of k (= number of different marked necklaces belonging to its equivalence class).

We have: (1) BBBBBB (k=1, achiral), (2) BBBBBW (k=6, achiral), (3) BBBBWW (k=6, achiral), (4) BBBWBW (k=6, achiral), (5) BBBWWW (k=6, achiral), (6) BBWBBW (k=3, achiral), (7) BBWBWW (k=12, chiral), (8) BBWWWW (k=6, achiral), (9) BWBWBW (k=2, achiral), (10) BWBWWWW (k=6, achiral), (11) BWWBWW (k=3, achiral), (12) BWWWWW (k=6, achiral), (13) WWWWWW (k=1, achiral).

Hence, only bracelet (7) has no reflection symmetry, and thus it is chiral. The k=12 marked necklaces of its equivalence class are as follows:

BBWBWW, WBBWBW, WWBBWB, BWWBBW, WBWWBB, BWBWWB, and their mirror images BWWBWB, BBWWBW, WBBWWB, BWBBWW, WBWBBW, WWBWBB.

We see that T(n=6, k=1) = 2, T(n=6, k=2) = 1, T(n=6, k=3) = 2, T(n=6, k=6) = 7, and T(n=6, k=12) = 1, which agree with line n=6 in the triangle above.

(End)

MATHEMATICA

Needs["Combinatorica`"];

f[list_]:= Sort[NestList[RotateLeft, list, Length[list]-1] ~Join~NestList[RotateLeft, Reverse[list], Length[list]-1]]; Flatten[Table[Distribution[Map[Length, Map[Union, Union[Map[f, Strings[{0, 1}, n]]]]], Range[2 n]], {n, 1, 10}]]

CROSSREFS

Cf. A000029 (row sums), A032239 (T(n, 2n) for n >= 3), A056493, A203398.

Sequence in context: A321430 A262774 A112604 * A323068 A072627 A277144

Adjacent sequences:  A203396 A203397 A203398 * A203400 A203401 A203402

KEYWORD

nonn,tabf

AUTHOR

Geoffrey Critzer, Jan 01 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 23:01 EST 2019. Contains 329106 sequences. (Running on oeis4.)