A308401 Number of bracelets (turnover necklaces) of length n that have no reflection symmetry and consist of 6 white beads and n-6 black beads.

3, 6, 16, 30, 56, 91, 150, 224, 336, 477, 672, 912, 1233, 1617, 2112, 2700, 3432, 4290, 5340, 6552, 8008, 9678, 11648, 13888, 16503, 19448, 22848, 26658, 31008, 35853, 41346, 47424, 54264, 61803, 70224, 79464, 89733, 100947, 113344, 126840, 141680, 157780, 175416, 194480, 215280, 237708

Offset: 9

Author

Petros Hadjicostas, May 24 2019

Keywords

• nonn
• easy

Comments

Bracelets that have no reflection symmetry are also known as chiral bracelets.

Here, for n >= 6, a(n) is also the number of dihedral compositions of n with 6 parts that have no reflection symmetry. Taking the MacMahon conjugates of these dihedral compositions, we see that a(n) is also the number of dihedral compositions of n into n-6 parts that have no reflection symmetry.

A cyclic composition b_1 + b_2 + ... + b_k of n into k parts is an equivalent class of (linear) compositions of n into k parts (placed on a circle) such that two such (linear) compositions are equivalent iff one can be obtained from the other by a rotation. Such compositions were first studied extensively by Sommerville (1909).

A dihedral composition b_1 + b_2 + ... + b_k of n into k parts is an equivalent class of (linear) compositions of n into k parts (placed on a circle) such that two such (linear) compositions are equivalent iff one can be obtained from the other by a rotation or a reversal of order. Such compositions were studied, for example, by Knopfmacher and Robbins (2013).

Given a bracelet of length n with k white beads and n-k black beads, we may get the corresponding dihedral composition using MacMahon's correspondence: start with a white bead and count that bead and the black beads that follow (in one direction), and call that b_1; then start with the next white bead and count that one and the black beads that follow, and call that b_2; repeat this process until you reach the k-th white bead and count that one and the black beads that follow, and call that b_k. The corresponding dihedral composition is b_1 + b_2 + ... + b_k.

If in the previous paragraph (given a bracelet of length n with k white beads and n-k black beads), we replace the white beads with black beads and the black beads with white beads, we get a dihedral composition of n into n-k parts: c_1 + c_2 + ... + c_{n-k}. These two dihedral compositions (which correspond to the same bracelet) are called "conjugate" compositions. See p. 273 in Sommerville (1909) for an explanation of "conjugate" compositions in the context of cyclic compositions.

Symmetric cyclic compositions of a positive integer n were first studied by Sommerville (1909, pp. 301-304). It can be proved that the study of necklaces with reflection symmetry using beads of two colors is equivalent to the study of symmetric cyclic compositions of a positive integer. Clearly all the necklaces with reflection symmetry are all the bracelets (turnover necklaces) with reflection symmetry. See also the comments for sequences A119963, A292200, and A295925.

Examples

			Using Frank Ruskey's website (listed above) to generate bracelets of fixed content (6, 3) with string length n = 9 and alphabet size 2, we get the following A005513(n = 9) = 7 bracelets: (1) WWWWWWBBB, (2) WWWWWBWBB, (3) WWWWBWWBB, (4) WWWWBWBWB, (5) WWWBWWWBB, (6) WWWBWWBWB, and (7) WWBWWBWWB. From these, bracelets 1, 4, 5, and 7 have reflection symmetry, while bracelets 2, 3 and 6 have no reflection symmetry (and thus, a(9) = 3).
Starting with a black bead, we count that bead and how many white beads follow (in one direction), and continue this process until we count all beads around the circle. We thus use MacMahon's correspondence to get the following dihedral compositions of n = 9 into 3 parts: (1) 1 + 7 + 1, (2) 1 + 2 + 6, (3) 1 + 3 + 5, (4) 2 + 5 + 2, (5) 4 + 1 + 4, (6) 2 + 3 + 4, and (7) 3 + 3 + 3. Again, dihedral compositions 1, 4, 5, and 7 are symmetric (have reflection symmetry), while dihedral compositions 2, 3, and 6 are not symmetric (and thus, a(9) = 3).
We may also start with a white bead and count that bead and how many black beads follow (in one direction), and continue this process until we count all beads around the circle. We thus use MacMahon's correspondence again to get the following (conjugate) dihedral compositions of n = 9 into 6 parts: (1) 1 + 1 + 1 + 1 + 1 + 4, (2) 1 + 1 + 1 + 1 + 2 + 3, (3) 1 + 1 + 1 + 2 + 1 + 3, (4) 1 + 1 + 1 + 2 + 2 + 2, (5) 1 + 1 + 2 + 1 + 1 + 3, (6) 1 + 1 + 2 + 1 + 2 + 2, and (7) 1 + 2 + 1 + 2 + 1 + 2. Again, dihedral compositions 1, 4, 5, and 7 have reflection symmetries, while dihedral compositions 2, 3, and 6 do not have reflection symmetries (and thus, a(9) = 3). For example, dihedral composition 1 is symmetric because we can draw an axis of symmetry through one of the 1s and 4. In addition, dihedral composition 5 is symmetric because we may draw an axis of symmetry through the numbers 2 and 3.
		

Links

• Colin Barker, Table of n, a(n) for n = 9..1000
• Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
• Petros Hadjicostas, The aperiodic version of Herbert Kociemba's formula for bracelets with no reflection symmetry, 2019.
• Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
• Richard H. Reis, A formula for C(T) in Gupta's paper, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 1000-1001.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• Vladimir S. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
• Vladimir S. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
• Duncan M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.
• Index entries for linear recurrences with constant coefficients, signature (2,1,-3,-1,1,4,-3,-3,4,1,-1,-3,1,2,-1).

Crossrefs

Cf. A005513, A008804, A032246, A032247, A032248, A032249, A058187, A119963, A292200, A295925. Column k = 6 of A180472.

Programs

PARI

a(n) = (1/12)* (sumdiv(gcd(n, 6), d,  eulerphi(d)*binomial((n/d) - 1, (6/d) - 1))) - (1/2)*binomial(floor(n/2), 3); \\ Michel Marcus, May 28 2019

PARI

Vec(x^9*(3 + x^2 + x^3 + x^4) / ((1 - x)^6*(1 + x)^3*(1 - x + x^2)*(1 + x + x^2)^2) + O(x^50)) \\ Colin Barker, Jun 02 2019

Formula

G.f.: (x^k/2) * (-(1 + x)/(1 - x^2)^floor((k/2) + 1) + (1/k) * Sum_{m|k} phi(m)/(1 - x^m)^(k/m)) with k = 6. (This formula is due to Herbert Kociemba.)

a(n) = A005513(n) - A058187(n-6) = A005513(n) - binomial(floor(n/2), 3) for n >= 6.

a(n) = -(1/2)*binomial(floor(n/2), 3) + (1/12)* Sum_{d|gcd(n, 6)} phi(d)*binomial((n/d) - 1, (6/d) - 1) for n >= 6. (This is a modification of formulas found in Gupta (1979) and Shevelev (2004).)

From Colin Barker, May 26 2019: (Start)

G.f.: x^9*(3 + x^2 + x^3 + x^4) / ((1 - x)^6*(1 + x)^3*(1 - x + x^2)*(1 + x + x^2)^2).

a(n) = 2*a(n-1) + a(n-2) - 3*a(n-3) - a(n-4) + a(n-5) + 4*a(n-6) - 3*a(n-7) - 3*a(n-8) + 4*a(n-9) + a(n-10) - a(n-11) - 3*a(n-12) + a(n-13) + 2*a(n-14) - a(n-15) for n > 23. (End)